抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

常见排序算法

A9ia
数据结构和算法

发布于：2023年2月17日
次浏览

排序算法

每次循环和递归都要额外注意终止条件

排序算法基本模板

排序算法的复杂度不会低于lg(N!)，可以通过构造一棵这样的树证明：叶子节点是元素所有的排序方式（N!个叶子节点)，内部节点是进行的两两比较，树的高度h即需要进行的最少比较次数。叶子节点最多为2^h，最少为n!个，所以可以得到2^h >= N!，从而得到h>=lg(N!)，根据斯特林公式，可以得到h>= lg(N!) ~lg(NlogN)

假定升序排列

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
36
37
38
39
40
41
42
class SortExample {
  constructor(a) {
    this.arr = Array.isArray(a) ? a : a.split('');
    this.len = a.length;
    this.ascendingOrder = true;
  };

  less(a, b) {
    const { len, arr } = this;
    if(a >= len || a < 0) { console.log("less funciton a out of length, a = " + a);}
    if(b >= len || b < 0) { console.log("less function b out of length, b = " + b);}
    return !!(arr[a] <= arr[b]);
  }

  exch(a, b) {
    const arr = this.arr;
    let temp = arr[a];
    this.arr[a] = arr[b];
    this.arr[b] = temp;
  }

  show() {
    const { arr, len } = this;
    for (let i = 0; i < len; i++) {
      console.log("index: " + i + ", value: " + arr[i]);
    }
  }

  sort(sortMethod, ascendingOrder = true) {
    this.ascendingOrder = ascendingOrder;
    sortMethod(ascendingOrder);
  }

  isSorted() {
    const { len, ascendingOrder } = this;
    if (len == 1) { return true; }
    for (let i = 0; i < len - 1; i++) {
      if (!(ascendingOrder ^ !this.less(i, i + 1))) return false;
    }
    return true;
  }
}

初级排序算法

  • 冒泡排序 O(n^2)：从第一个元素依次与邻近的元素进行比较，如果前者大那么进行调换。进行该过程n - 1次则能将n-1个更大的元素放到后面。共 n^2/2 次比较和最多 n^2/2 次，最少 0 次交换
  • 选择排序 O(n^2)：选择当前数组中最小的元素与数组中第一个进行调换，然后对除了第一个元素之外的元素进行该过程，需要进行n-1次。共 n^2/2 次比较和 n - 1 次交换
  • 插入排序 O(n^2)：分为已排序好的一侧和未排序一侧，依次从未排序一侧获取元素插入到已排序好的一侧中。平均需要 n^2/4 次比较和 n^2/4 次交换。在面对相对有序和较少的数组时性能较好。
  • 希尔排序 O(n^(3/2))：用 step 将数组划分为 step 份，然后通过插入排序使其 step 份内有序。选择step为 3x + 1的形式，完成一轮则 step / 3，直到 step 为 1 时有序。借助了相对有序和较少时插入排序性能好的优点，能使得排序时间复杂度质数减少。是初级排序算法中最快处理中等长度数组的算法。、
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 冒泡排序 [(n - 1) + (n - 2) +... + 1] = n*n/2 次比较运算 O(n^2)的时间复杂度
function boobMethod (ascendingOrder) {
  let { len } = this;
  for(let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if(!(ascendingOrder ^ !this.less(j, j + 1))) { this.exch(j, j + 1); }
    }
  }
}

// 选择排序
function selectMethod (ascendingOrder) {
  let { len } = this;
  for (let i = 0; i < len - 1; i++) {
    let min = i;
    for (let j = i + 1; j < len; j++) {
      if(this.less(j, min)) { min = j };
    }
    this.exch(i, min);
  } 
}

// 插入排序
function insertMethod (ascendingOrder) {
  let { len } = this;
  for (let i = 1; i < len; i++) {
    for (let j = i; j > 0; j--) {
      if (!(ascendingOrder ^ this.less(j - 1, j))) { break; }
      else { this.exch(j - 1, j); }
    }
  }
}

// 希尔排序
function shellMethod (ascendingOrder) {
  let { len } = this;
  let step = 1;
  while (step < len / 3) { step = step * 3 + 1; }
  while (step >= 1) {
    for (let i = step; i < len; i++) {
      for (let j = i; j >= step && !(ascendingOrder ^ (!this.less(j - step, j))); j = j - step) {
        this.exch(j, j - step);
      }
    }
    step = Math.floor(step / 3);
  }
}

const exam = new SortExample([2,1,3,5,11,4,13,22,21,7,10,18,2222,3123213,432545,12312]);
// exam.sort(boobMethod.bind(exam), false);
// exam.sort(selectMethod.bind(exam), false);
// exam.sort(insertMethod.bind(exam), false);
// exam.sort(shellMethod.bind(exam), false);
exam.isSorted() ? exam.show() : console.log("wrong result");

高级排序算法(2023.2.22更新)

  • 归并排序：将数组平均分为两列分别排序，直到某一列只有两个元素，然后对这两个元素进行按序merge，然后对两组两个元素进行merge，依次类推。时间复杂度能达到 O( n log n )
  • 快速排序：选择一个元素，从前向后找比该元素小的，从后往前找比该元素大的，若能找到则将两者对调位置，直到两个指针相遇，将最初选择的元素放到对应的位置。相对于归并排序，每次比较时只比较相同的一个元素，所以能更快，原地排序，所以空间占用更少。快排的最好情况就是每次选定的值都能把数组对半分。
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// 归并排序
class MergeSort extends SortExample {
  constructor(a, b = true) {
    super(a);
    this.ascendingOrder = b;
    this.aux = [];
  }

  merge(lo, mid, fi) {
    const { arr, aux } = this;
    for (let i = lo; i <= fi; i++) {
      aux[i] = arr[i];
    }
    let i = lo;
    let j = mid + 1;
    // let index = lo;
    // while (index <= fi) {
    //   if (i > mid) {
    //     arr[index++] = aux[j++];
    //   } else if (j > fi) {
    //     arr[index++] = aux[i++];
    //   } else {
    //     if(this.less(i, j)) {
    //       arr[index++] = aux[i++];
    //     } else {
    //       arr[index++] = aux[j++];}
    //   }
    // }
    for (let index = lo; index <= fi; index++) {
      if (i > mid) { arr[index] = aux[j++]; }
      else if (j > fi) { arr[index] = aux[i++]; }
      else if (!(this.ascendingOrder^(aux[i] < aux[j]))) { arr[index] = aux[i++]; }
      else { arr[index] = aux[j++]; }
    }
  }
  // 自顶而下的
  sort(lo = 0, fi = this.len - 1) {
    console.log("lo: " + lo + "fi : " + fi)
    if (lo >= fi) {
      return;
    }
    const mid = Math.floor((lo + fi) / 2);
    this.sort(lo, mid);
    this.sort(mid + 1, fi);
    this.merge(lo, mid, fi);
  }
  
  // 自下而上的
  Upsort() {
    let fi = this.len - 1;
    for (let sz = 1; sz <= fi; sz = sz + sz) {
      for (let lo = 0; lo <= fi - sz + 1; lo = lo + 2 * sz) {
        this.merge(lo, lo + sz - 1, Math.min(lo + 2 * sz - 1, fi));
      }
    }
  }
}

// 最基础的快速排序
class QuickSort extends SortExample {
  constructor(a, b = true) {
    super(a);
    this.ascendingOrder = b;
    this.sort(0, this.len - 1);
  }

  sort(lo, fi) {
    if (lo >= fi) {
      return;
    }
    const p = this.partition(lo, fi);
    this.sort(lo, p - 1);
    this.sort(p+1, fi);
  }

  partition(lo, fi) {
    // const { arr, len } = this;
    // const value = arr[lo];
    let i = 0;
    let j = fi + 1;
    while (true) {
      while(!this.less(lo, ++i)) {
        if (i == fi) {
          break;
        }
      }
      while(!this.less(--j, lo)) {
        if (j == lo) {
          break;
        }
      }
      if (i>=j) {
        break;
      }
      this.exch(i, j);
    }
    this.exch(j, lo);
    return j;
  }
}

const exam = new MergeSort([2,1,3,5,11,4,13,22,21,7,10,18], false);
exam.sort();
exam.isSorted() ? exam.show() : console.log("wrong result");

const quickExam = new QuickSort([2,1,3,5,11,4,13,22,21,7,10,18]);
quickExam.isSorted() ? exam.show() : console.log("wrong result");

快速排序的进阶版本
  1. 快排依赖于partition找到合适的切分点，当数组最坏情况时可能会一直选到偏大或偏小的切分点, 一般情况需要打乱数组后进行快排。
  2. 对于小数组而言，快排速度很慢，所以可以跟插入排序互补。
1
2
3
4
5
6
7
8
9
10
sort(lo, fi) {
  if (lo + M >= fi) {
    // 在面对M的小数组时，进行插入排序
    insertSort(lo, fi);
    return;
  }
  const p = this.partition(lo, fi);
  this.sort(lo, p - 1);
  this.sort(p+1, fi);
}
  1. 可以优化掉判断 j == lo 时的大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
partition(lo, fi) {
  // const { arr, len } = this;
  // const value = arr[lo];
  let i = 0;
  let j = fi + 1;
  while (true) {
    while(!this.less(lo, ++i) && i < j);
    while(!this.less(--j, lo));
    if (i>=j) {
      break;
    }
    this.exch(i, j);
  }
  this.exch(j, lo);
  return j;
}

  1. 可以使用取样大小为3的样本中位数来代替随机获取一个数字，这样更容易取到合适的切分点

  2. 当包含大量相同元素时，我们目前的排序算法可以用三切分的方式进行改进（2023.2.23）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function exch (arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
// 三向切分的快速排序
const triDivideQS = (arr, st, gt) => {
  if (gt <= st) {return;}
  // const len = arr.length;
  let lo = st;
  const value = arr[lo];
  let fi = gt;
  let i = lo + 1;
  while(fi - i >= 0) {  // 关键等号，保证fi能被遍历到
    const differ = arr[i] - value;
    if (differ < 0) {exch(arr, i, fi--);}
    else if (differ > 0) {exch(arr, lo++, i++);}
    else {i++;}
  }
  triDivideQS(arr, st, lo - 1);
  triDivideQS(arr, fi + 1, gt);
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://www.a9ia.top/sort-algorithms/

更新于：2023年2月23日

算法

评论