logo

排序算法之选择排序,堆排序,归并排序

选择排序(Selection Sort)

选择排序,首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序

步骤(升序)

  1. 找寻未排序元素中的最小值
  2. 将最小值元素位置与第 1 个未排序元素交换,最小值视为已排序元素
  3. 重复步骤 1~2 直到所有元素有序。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function selectionSort(arr) {
let len = arr.length;
let min;
for (let i = 0; i < len; i++) {
min = i;
/* 遍历查找最小值 */
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
/* 交换最小值 */
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
return arr;
}

分析

排序方式为 In-Place(原地)排序,因此空间复杂度为 $O(1)$

  • 最佳情况:序列升序,长度为 $n$ 的序列比较 $\sum_{i=1}^{n-1}{i}\Longrightarrow\frac{n(n-1)}{2}$ 次,交换 $0$ 次,时间复杂度为 $O(n^2)$
  • 最差情况:序列倒序,长度为 $n$ 的序列比较 $\sum_{i=1}^{n-1}{i}\Longrightarrow\frac{n(n-1)}{2}$ 次,交换 $n-1$ 次,时间复杂度为 $O(n^2)$

平均时间复杂度为$O(n^2)$,元素位置每次遍历发生变动,不稳定排序,相对冒泡排序,插入排序有更少的交换次数。

堆排序(Heap Sort)

推排序可以看作采用堆的方法进行选择排序。
堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。

步骤(升序)

  1. 在数组中递归实现 In-Place 建立最大堆(Max Heap)
  2. 取出最大堆堆顶元素与最后一个未排序元素交换,对剩下的元素继续构建最大堆。
  3. 重复步骤 2 直到只剩堆中只剩下一个元素,停止排序。

实现

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
function heapSort(arr) {
function swap(i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/* 构建最大堆,父节点的值不小于子节点 */
function maxHeapify(start, heapSize) {
/*父节点*/
let dad = start;
/* 左子子节点 */
let son = start * 2 + 1;
/* 如果超出堆范围停止执行 */
if (son >= heapSize) {
return;
}
/* 从左右子节点中,选出最大的子节点索引 */
if (son + 1 < heapSize && arr[son] < arr[son + 1]) {
son++;
}
/* 如果父节点小于子节点,交换父子节点,重新构建被交换子节点下的堆 */
if (arr[dad] < arr[son]) {
swap(dad, son);
maxHeapify(son, heapSize);
}
}
let len = arr.length;
/* 从最后一个父节点开始构建最大堆 */
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
maxHeapify(i, len);
}
/* 遍历数组,每次找出最大的元素 */
for (let j = len - 1; j > 0; j--) {
swap(0, j);
maxHeapify(0, j);
}
return arr;
}

分析

排序方式为 In-Place(原地)排序,无递归调用栈,空间复杂度为 $O(1)$ 。
平均时间复杂度为$O(n\log{n})$,元素位置根据堆的结构调整,因此是不稳定排序。相对于选择排序有更高的查找最大元素的效率。

归并排序(Merge Sort)

归并排序采用分治法进行排序:
分割:递归地把当前序列平均分割成两半。
归并:在保持元素顺序的同时将上一步得到的子序列归并到一起。

递归法步骤(Top-Down/升序)

  1. 将目标数组分递归为 left,right 两组,对 left,right 继续分组直到有一组长度为 0 为止。
  2. 递归合并数组,依次比较 left,right 数组,从下到上依次归并为一个升序的序列,直到所有元素归并完毕。

实现

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
function mergeSort(arr) {
/* 归并 */
function merge(left, right) {
let res = [];
/* 归并两个序列,从小到大依次排列,确保归并后的每个子序列都是升序 */
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
res.push(left.shift());
} else {
res.push(right.shift());
}
}
/* 返回归并结果 */
return [...res, ...left, ...right];
}
/* 递归停止条件 */
if (arr.length <= 1) {
return arr;
}
/* 分割 */
let middle = Math.floor(arr.length / 2);
let left = arr.slice(0, middle);
let right = arr.slice(middle);
/* 递归分割归并 */
return merge(mergeSort(left), mergeSort(right));
}

迭代法步骤(Bottom-Up/升序)

对 $n$ 个元素的序列排序:

  1. 对序列相邻的元素进行归并并排序,生成 $\lceil{n/2}\rceil$ 个子序列,每个序列包含 1~2 个元素
  2. 如果子序列数不为 $1$,则对相邻的子序列进行归并并排序,生成 $\lceil{n/4}\rceil$ 个子序列,每个序列包含 1~4 个元素
  3. 重复步骤 2,直到子序列数为 $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
function mergeSort(arr) {
let len = arr.length;
/* 从每个子序列2个元素开始,直到子序列长度大于等于总长度*/
for (let i = 2; i < len * 2; i *= 2) {
/* 遍历每个子序列序列排序 */
for (let j = 0; j <= Math.floor((len - 1) / i); j++) {
/* 归并操作,并将结果存储到res中 */
let start = i * j;
let middle = Math.min(start + Math.floor(i / 2), len - 1);
let end = Math.min(i * (j + 1) - 1, len - 1);
let s = start;
let m = middle;
let res = [];
while (s < middle && m <= end) {
if (arr[s] < arr[m]) {
res.push(arr[s++]);
} else {
res.push(arr[m++]);
}
}
while (s < middle) {
res.push(arr[s++]);
}

while (m <= end) {
res.push(arr[m++]);
}
/* 将排序结果替换arr中对应的部分 */
arr.splice(start, res.length, ...res);
}
}
return arr;
}

分析

排序方式都为为 Out-Place 排序,平均空间复杂度都为 $O(n)$
平均时间复杂度都为$O(\log{n})$,相等元素排序位置固定,稳定排序。

总结

Chorme72 性能测试

10000 个数测试代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function test(time) {
let tempTime = time;
let result = [];
while (time > 0) {
var n = 10000;
var arr = Array.from({
length: n
}).map(() => Math.round(Math.random() * n));

var start, end;
start = performance.now();

SortMethod();

end = performance.now();
result.push(end - start);
time--;
}
return result.reduce((a, b) => a + b) / tempTime;
}
test(10);
排序方法10 次平均时间(ms)
选择排序60.561ms
堆排序4.824ms
归并排序递归11.068ms
归并排序迭代5.743ms

综合比较

排序方法平均时间复杂度最佳时间复杂度最差时间复杂度空间复杂度稳定性排序方式
选择排序$O(n^2)$$O(n^2)$$O(n^2)$$O(1)$不稳定In-Place
堆排序$O(n\log{n})$$O(n\log{n})$$O(n\log{n})$$O(1)$不稳定In-Place
归并排序$O(n\log{n})$$O(n\log{n})$$O(n\log{n})$$O(n)$稳定Out-Place

参考链接