算法：排序算法

发表于 | 分类于

排序算法

快速排序

排序方法

选择一个目标值，比目标值小的放在左边，比目标值大的放在右边，目标值的位置已经排好，将左右两侧再进行排序

实现思路
  1. 记录一个索引l从数组最左侧开始，记录一个索引r从数组最右侧开始，记录一个target（选第一位为目标值）
  2. while循环：在l<r的条件下，找到右侧小于target的值array[r]，并将其赋值到array[l]
    在l<r的条件下，找到左侧大于target的值array[l]，并将其赋值到array[r]
  3. 这样当l=r时，左侧的值全部小于target，右侧的值全部大于target，将target放到该位置
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function quickSort(array,start=0,end=array.length-1){
  if ( start >= end ) {
    return;
  }
  let l = start;
  let r = end;
  let target = array[start];
  while ( l < r ) {
    while (l < r && array[r] >= target) {
      r--;
    }
    array[l] = array[r];
    while (l < r && array[l] < target) {
      l++;
    }
    array[r] = array[l];
  }
  array[l] = target;
  quickSort(array, start, l-1);
  quickSort(array, l+1, end);
  return array;
}
复杂度

平均时间复杂度： O(nlogn)
最坏时间复杂度： O(n^2)
空间复杂度：O(logn)

选择排序

排序方法

每次给一个数排序，前面的已经排好了，在后面选取一个最大或者最小的数字放到前面的有序序列中。

实现思路
  1. for循环，对每一项i，记录它的位置minIndex
  2. 在i以后的每一项循环，如果它比array[minIndex]小，就把这个位置记为minIndex
  3. 交换i和minIndex处的数
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
function selectionSort(array){
  for (let i=0; i<array.length-1; i++) {
    let minIndex = i;
    for (let j=i+1; j<array.length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }
      [array[i], array[minIndex]] = [array[minIndex], array[i]];
    }
  }
  return array;
}
复杂度

平均时间复杂度： O(n^2)
最坏时间复杂度： O(n^2)
空间复杂度：O(1)

插入排序

排序方法

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

实现思路
  1. for循环：对每一项i，记录它的位置target
  2. i前面的序列循环（从右到左），如果array[target]比这一项小，就互相交换，让target等于这一项的位置，直到小于等于某一项停止
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertSort(array){
  for (let i=0; i<array.length; i++) {
    let target = i;
    for (let j=i-1; j>=0; j--) {
      if (array[target] < array[j]) {
        [array[j], array[target]] = [array[target], array[j]];
        target = j;
      }
      else {
        break;
      }
    }
  }
  return array;
}
复杂度

平均时间复杂度： O(n^2)
最坏时间复杂度： O(n^2)
空间复杂度：O(1)

冒泡排序

排序方法

每次两两比较，一次循环后最后一个数是本轮最大数。循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。下一次循环继续上面的操作，不循环已经排序好的数。

实现思路
  1. 外层for循环
  2. 内层for循环：两两比较，如果后面比前面大，则交换
  3. 优化：如果一次循环没有冒泡，说明已经排好序，可以加一个判断boolean
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function bubbleSort(array){
  for (let i=0; i<array.length; i++) {
    let complete = true;
    for (let j=0; i<array.length - 1; j++) {
      if(array[j+1] < array[j]){
        [array[j], array[j+1]] = [array[j+1], array[j]];
        complete = false;
      }
    }
    if (complete) {
      break;
    }
  }
  return array;
}
复杂度

平均时间复杂度： O(n^2)
最坏时间复杂度： O(n^2)
空间复杂度：O(1)

排序算法的稳定性

  • 有两个相同的A和B，在排序之前A在B的前面，而经过排序后，B跑到了A的前面，这种情况成为排序的不稳定性。
  • 对于前端的意义：比如虚拟DOM的比较，对一个<ul>列表进行渲染，当数据改变以后余姚比较变化时候，不稳定性会使本身不需要变化的项发生变化，导致重新渲染，带来性能的损耗。

比较一下

排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性
快速排序 O(nlogn) O(n^2) O(logn) no
归并排序 O(nlogn) O(nlogn) O(n) yes
选择排序 O(n^2) O(n^2) O(1) no
插入排序 O(n^2) O(n^2) O(1) yes
冒泡排序 O(n^2) O(n^2) O(1) yes