数组结构 - 排序算法

快速排序

从给定的数据中，随机抽出一项，这项的左边放所有比它小的，右边放比它大的，然后再分别这两边执行上述操作，采用的是递归的思想，总结出来就是 实现一层，分别给两边递归，设置好出口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function fastSort(array, head, tail) {
  //考虑到给每个分区操作的时候都是在原有的数组中进行操作的，所以这里head,tail来确定分片的位置
  /*生成随机项*/
  var randomnum = Math.floor(ranDom(head, tail));
  var random = array[randomnum];
  /*将小于random的项放置在其左边  策略就是通过一个临时的数组来储存分好区的结果，再到原数组中替换*/
  var arrayTemp = [];
  var unshiftHead = 0;
  for (var i = head; i <= tail; i++) {
    if (array[i] < random) {
      arrayTemp.unshift(array[i]);
      unshiftHead++;
    } else if (array[i] > random) {
      arrayTemp.push(array[i]);
    }
    /*当它等于的时候放哪，这里我想选择放到队列的前面，也就是从unshift后的第一个位置放置*/
    if (array[i] === random) {
      arrayTemp.splice(unshiftHead, 0, array[i]);
    }
  }
  /*将对应项覆盖原来的记录*/
  for (var j = head, u = 0; j <= tail; j++, u++) {
    array.splice(j, 1, arrayTemp[u]);
  }
  /*寻找中间项所在的index*/
  var nowIndex = array.indexOf(random);

  /*设置出口，当要放进去的片段只有2项的时候就可以收工了*/
  if (arrayTemp.length <= 2) {
    return;
  }
  /*递归，同时应用其左右两个区域*/
  fastSort(array, head, nowIndex);
  fastSort(array, nowIndex + 1, tail);
}

插入排序

思想就是在已经排好序的数组中插入到相应的位置，以从小到大排序为例，扫描已经排好序的片段的每一项，如大于，则继续往后，直到他小于一项时，将其插入到这项的前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function insertSort(array) {
  /*start根据已排列好的项数决定*/
  var start = 1;
  /*按顺序，每一项检查已排列好的序列*/
  for (var i = start; i < array.length; start++, i++) {
    /*跟已排好序的序列做对比，并插入到合适的位置*/
    for (var j = 0; j < start; j++) {
      /*小于或者等于时（我们是升序）插入到该项前面*/
      if (array[i] <= array[j]) {
        console.log(array[i] + " " + array[j]);
        array.splice(j, 0, array[i]);
        /*删除原有项*/
        array.splice(i + 1, 1);
        break;
      }
    }
  }
}

冒泡排序

故名思意 ，就是一个个冒泡到最前端或者最后端，主要是通过两两依次比较，以升序为例，如果前一项比后一项大则交换顺序，一直比到最后一对

1
2
3
4
5
6
7
8
9
10
11
12
Array.prototype.bubbleSort = function () {
  for (var i = 0; i < this.length; i++) {
    for (var k = i + 1; k < this.length; k++) {
      if (this[i] > this[k]) {
        var temp = this[i];
        this[i] = this[k];
        this[k] = temp;
      }
    }
  }
  return this;
};

​

选择排序

将当前未确定块的 min 或者 max 取出来插到最前面或者后面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Array.prototype.chooseSort = function () {
  for (var i = 0; i < this.length; i++) {
    var min = i;
    for (var k = i + 1; k < this.length; k++) {
      if (this[k] < this[min]) {
        min = k;
      }
    }
    var temp = this[i];
    this[i] = this[min];
    this[min] = temp;
  }
  return this;
};