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

本页面需要浏览器支持(启用)JavaScript


了解详情 >

排序算法

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

排序算法基本模板

排序算法的复杂度不会低于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);
}

评论