备注

  • 语法为 ES6
  • 以下排序默认按升序排序
  • 测试案例均为自然数

前言

排序作为十分经典的算法之一。是每一个软件工程师的必备技能,学好排序算法,可以提高软件的运行效率,最重要的是掌握其算法设计思想,才能举一反三应用到实际的实践中,为己所用。

排序算法简介

  1. 按照数据的大小,排序算法可以分为内部排序和外部排序(数据较大,需要借助外存)
  2. 内部排序,又可以细分为 交换排序、插入排序、选择排序

1. 冒泡排序

简介:两两元素进行比较,较大者放置后头,类似水中的气泡较大者浮在水的上端

性能

平均时间复杂度 O(n^2)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubble(arr) {
let len = arr.length,
i = 0,
j = 0;
// 循环 n-1 趟
for (i = 0; i < len; i++) {
// 每趟 需比较 n-i-1 次
for (j = 0; j < len - 1 - i; j++) {
// 如果后面的元素较大,则交换两者顺序
if (arr[j + 1] < arr[j]) {
arr[j] = [arr[j + 1], arr[j + 1] = arr[j]][0];
}
}
}
return arr;
}

2. 快速排序

简介:取一个元素为基准,把序列分成两部分,小于基准的放到它的左面,大于等于的放到它的右面,然后在把左面和右面的子序列再进行上述的拆分,直到子序列不可再分割(小于2个元素),最终达到整个序列有序

性能

平均时间复杂度 O(n*logn)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function quick(arr) {
// 不可再分割,直接退出
if (arr.length <= 1) return arr;
let len = arr.length,
middle = len >> 1,
pivot = (len--) && arr.splice(middle, 1)[0], // 取中间为基准数,并从数组中移除
left = [],
right = [],
i = 0;

for (i = 0; i < len; i++) {
// 分组 小于基准的放到左边,反之
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quick(left), pivot, ...quick(right)]; // 合并
}

3. 简单选择排序

简介:假设一个有序序列,然后由剩余的元素中选出最小的(最大的)扔到有序序列,直到无序序列元素为空,从而达到整个序列有序

性能

平均时间复杂度 O(n^2)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function selection(arr) {
let len = arr.length,
i = 0,
j = 0,
min = i;
// 循环 n-1 趟
for (i = 0; i < len - 1; i++) {
min = i; // 假设每趟的第一个数为最小值
for (j = i + 1; j < len; j++) {
// 如果后面的树大于最小数(min对应的数),则重新对最小值的索引赋值
if (arr[j] < arr[min]) {
min = j;
}
}
// 将最小数置于该趟排序的第一个位置
arr[i] = [arr[min], arr[min] = arr[i]][0];
}
return arr;
}

4. 堆排序

简介:是简单选择排序的改进版,利用堆结构

性能

平均时间复杂度 O(n*logn)

代码

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
// 堆排序
function heapSort(arr) {
var n = arr.length,
i, j;

// 筛选
var sift = (k, m, r) => {
var p = k, // 父结点
c = p * 2 + 1; // 左结点(默认最大)

while (c <= m) { // 左结点(c=m)和左右结点(c<m)
if (c < m && r[c + 1] > r[c]) c++; // 选出左右结点中的最大者,指向左结点
if (r[p] > r[c]) break; // 父结点大于左结点 顺序正确,退出循环
else {
r[p] = [r[c], r[c] = r[p]][0]; // 将大的一方置于顶部(父结点)
p = c; // 向下重新指向父结点
c = p * 2 + 1; // 向下重新指向左结点
}
}
};

// 构建堆
for (i = (n / 2 | 0) - 1; i >= 0; i--) { // 从最后一个分支结点开始向上逆序遍历
sift(i, n - 1, arr);
}
// 排序
for (j = n - 1; j >= 0; j--) {
arr[0] = [arr[j], arr[j] = arr[0]][0]; // 将最大的结点存于数组的最后一位
n--; // 减少数组长度,排除有序序列
sift(0, n - 1, arr, true);
}

return arr;
}

5. 直接插入排序

简介:假设数组的一有序序列,从后面的无序序列中,扫描,与有序序列比较,插入到合适位置

性能

平均时间复杂度 O(n^2)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function insertion(arr) {
let len = arr.length,
i = 0,
j = 0,
temp;

// [7,6,2,5,4,3,1]
// 从第二个元素开始循环
for (i = 1; i < len; i++) {
temp = arr[i]; // 存储当前元素
j = i - 1; // 待插入队列的序号
while (j >= 0 && temp < arr[j]) { // 当没有出界 且 当前元素比待插序列元素小时,进行待插序列的元素向后移动一位
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp; // 将当前元素插入到待插序列的下一位
}
return arr;
}

6. 希尔排序

简介:一种改进版的插入排序,每次比较的是用增量分割的序列,达到部分有序,随着增量依次递减,序列逐渐达到完全有序

性能

平均时间复杂度 O(n*logn)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function shell(arr) {
let len = arr.length,
i = 0,
j = 0,
temp,
gap = 1;

gap = len / 3 | 0; // 计算增量

while (gap >= 1) { // 增量大于2时,进行简单插入排序
for (i = gap; i < len; i++) {
temp = arr[i];
j = i - gap;
while (j >= 0 && temp < arr[j]) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
}
gap = gap / 3 | 0; // 增量减少
}

return arr;
}

7. 归并排序

简介:利用分治法,将序列分为许多小子序列,然后每个子序列进行排序,然后逐次合并,最后达到整体有序,这里用的是二路归并排序(归并排序中最简单的一种)

性能

平均时间复杂度 O(n*logn)

代码

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
function merge(arr) {
return ({
sortArr(leftArr, rightArr) { // 排序
let res = [];
// 合并
while (leftArr.length * rightArr.length !== 0) {
if (leftArr[0] < rightArr[0]) {
res.push(leftArr.shift());
} else {
res.push(rightArr.shift());
}
}
leftArr.length > 0 && (res = [...res, ...leftArr]);
rightArr.length > 0 && (res = [...res, ...rightArr]);
return res;
},
mergeArr(brr) { // 合并
if (brr.length <= 1) return brr;
let len = brr.length,
left = [],
right = [],
middle;
middle = len >> 1;
// 分组
left = brr.slice(0, middle);
right = brr.slice(middle);
return this.sortArr(this.mergeArr(left), this.mergeArr(right));
}
}).mergeArr(arr)
}

8. 计数排序

简介:利用分配概念,将元素一一映射到桶中,每个桶只存储单一值

性能

平均时间复杂度 O(n+m)

代码

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 countingSort(arr) {
var max = Math.max(...arr),
min = Math.min(...arr),
len = arr.length,
i,
bucket = [],
result = [];

// 入桶
for (i = 0; i < len; i++) {
var item = arr[i];
bucket[item] = bucket[item] || 0; // 建立映射表
bucket[item]++; // 相同元素对应到同一映射表中,映射表增加1
}

// 出桶
for (i = min; i <= max; i++) {
var count = bucket[i]; // 取每个映射表的元素数量
while (count > 0) { // 如果数量大于0 ,重复输出该元素
result.push(i);
count--;
}
}

return result;
}

9. 桶排序

简介:利用分配概念,每个桶存储一定范围的数值,然后桶内在进行排序,最后所有桶的元素出桶达到完全有序

性能

平均时间复杂度 O(n+m)

代码

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
function bucketSort(arr, num) {
var len = arr.length,
max = Math.max(...arr),
min = Math.min(...arr),
result = [],
bucket = [],
space,
i;
// 至少2个桶
num = num > 2 ? num : 2;
// 计算每个桶的容量
space = ((max - min) / num | 0) + 1;

// 入桶
for (i = 0; i < len; i++) {
var item = arr[i];
var index = (item - min) / space | 0; // 计算元素入桶的位置,要放入哪个桶

bucket[index] = bucket[index] || [];
bucket[index].push(item);
if (bucket[index].length > 1) {
// 桶里的元素再进行排序(这里使用的是简单插入排序)
bucket[index] = insertion(bucket[index]);
}
}

// 出桶
for (i = 0; i < num; i++) {
var list = bucket[i] || [];
if (list.length > 0) {
result = result.concat(list);
}
}

return result;
}

10. 基数排序

简介:利用分配概念,根据元素的基数来分配桶

  • 最低位优先法,简称LSD法:先从最低位开始排序,再对次低位排序,直到对最高位排序后得到一个有序序列

  • 最高位优先法,简称MSD法:先从最高位开始排序,再逐个对各分组按次高位进行子排序,循环直到最低位

性能

平均时间复杂度 O(n*m)

代码

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
function radixSort(arr) {
var len = arr.length,
max = Math.max(...arr),
bucket = [],
result = [],
i,
j,
k,
hight = String(max).length; // 计算最大数的位数

for (i = 1; i <= hight; i++) { // 其实就是循环hight次的计数排序
result = [];
bucket = [];
// 入桶
for (j = 0; j < len; j++) {
var item = arr[j] + ""; // 这里转换为string 类型,方便取具体位数的值,当然mod10也可以
var index = item.length - i < 0 ? 0 : item.substr(item.length - i, 1); // 取第(item.len-i+1)位的数
bucket[index] = bucket[index] || []; // 这里就和计数排序一样了
bucket[index].push(+item);
}
// 出桶
for (k = 0; k < bucket.length; k++) {
if (bucket[k] && bucket[k].length > 0) {
result = result.concat(bucket[k]);
}
}

arr = result;
}

return result;
}

性能比较

sort
sort

参考

  1. 《十大经典排序算法》