八大排序大合集

只要有坚强的意志力,就自然而然地会有能耐、机灵和知识。

它们,频繁出现在期末考题、竞赛赛场、面试题目、日常考核等场合;它们,让无数学子一夜白头;即使有现成标准库也不能忘记它们的实现思想;它们就是传说中的,八  大  排  序  !


前言

本文假设读者:

  • 具有一定的分析 复杂度 的基本功(文中不会过多介绍什么是复杂度);
  • 具有一定弱类型语言开发经验(全部算法实现使用 JavaScript)
本文出现的顺序并不代表该算法的优劣级别,这八种算法都是非常巧妙的(因为我自己发明不出来,所以这些算法及其发明者都很厉害)

本文所有的排序结果都是从小到大排序

关于 swap 方法

本文中所有出现 swap 方法的地方,代表将 array 数组中的两个下标上的数互换,其定义如下:

1
2
3
4
5
6
const swap = (a, b, array) => {
if (a === b) return;
array[b] ^= array[a];
array[a] ^= array[b];
array[b] ^= array[a];
};

冒泡排序

很可爱的名字,也是众多程序员第一个接触到的排序算法。

冒泡排序

算法思想

比较两个相邻的元素,将值大的元素交换到右边。当每一轮比较结束时,最大的数就会被放到 最后一个

不断轮循比较,最小的那个数就会像水中的泡泡一样浮到第一个位置,故名 冒泡排序

思路

  • 遍历当前数组中的每一个数;
  • 如果当前下标的数,大于下一个数,则将两个数交换位置(注意下标越界);
  • 这样,经过上面的一次遍历,就会将最大的数放到了最后一个;
  • 那么重复上面的遍历,每遍历一次,都会有一个数被放到相对最后的位置(因为已经排好序的已经是相对较大了,它们的位置不会再发生变化);
  • 即,第一次排序对比下标在 [0, n) 的数,并将最大的数放到了 (n - 1) 的位置上;
  • 第二次排序对比下标在 [0, n - 1) 的数,将次大的数放到了 (n - 2) 的位置上;
  • 将循环重复 n - 1 次(因为最后一个数一定是最小的,没必要排序了);

代码实现

1
2
3
4
5
6
7
8
9
10
const bubbleSort = array => {
for (let i = 0; i < array.length - 1; i++) {
for (let j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(j, j + 1, array);
}
}
}
console.log(array);
};

性能分析

若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数 C 和记录移动次数 M 均达到最小值:Cmin = n - 1Mmin = 0

若初始文件是反序的,需要进行 n - 1 趟排序。每趟排序要进行 n - i 次关键字的比较 (1 ≤ i ≤ n - 1),且每次比较都必须移动记录三次来达到交换记录位置。

在这种情况下,比较和移动次数均达到最大值,时间复杂度为 O(n2)


选择排序

选择排序

算法思想

每一次循环都找出来本轮最小的元素,将本轮最小的移动至最前方(尚未排序序列的最前方)。

思路

  • 遍历当前数组中的每一个数,找到最小的那个数;
  • 与尚未排序好的最前方的数进行交换,即第一次排序就将最小的数和下标为 0 的数交换;
  • 重复上述过程 (n - 1) 遍,因为最后一个元素一定是最大的,没有必要再排序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
const 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;
}
}
swap(i, minIndex, array);
}
console.log(array);
};

性能分析

比较次数 O(n2),比较次数与关键字的初始状态无关,总的比较次数 N = (n - 1) + (n - 2) + … + 1 = n * (n - 1) / 2。交换次数 O(n)

最好情况是,已经有序,交换 0 次;最坏情况交换 n - 1 次,逆序交换 n / 2 次。交换次数比冒泡排序少多了,由于交换所需 CPU 时间比比较所需的 CPU 时间多,n 值较小时,选择排序比冒泡排序快。


插入排序

插入排序

算法思想

对于每个当前处理的数,就像整理发到手中的扑克牌那样,将其插入到已经排序好的队列中。

思路

  • 从左至右遍历当前数组;
  • 将当前的数取出(做标记,并不是真的令数组长度 -1),设当前这个数下标为 A
  • 匹配已经排序好的队列(这个队列的长度就等于当前这个数的下标);
  • 如果这个队列中找到了比当前这个数还大的数,假设下标为 X,那么就从 X 开始,到 A - 1 结束,将中间的所有元素向右移动一个位置;
  • 这样 X 那个位置就空出来了,将标记值放入 X;
  • 重复上述流程,直至排序完毕。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
const insertSort = array => {
for (let i = 0; i < array.length; i++) {
let key = array[i];
for (let j = i - 1; j >= 0; j--) {
if (key > array[j]) {
break;
}
swap(j, j + 1, array);
}
}
console.log(array);
};

性能分析

如果目标是把 n 个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。

最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需 (n - 1) 次即可。

最坏情况就是,序列是降序排列,那么此时需要进行的比较共有 n (n - 1) / 2 次。

插入排序的赋值操作是比较操作的次数加上 (n - 1) 次。平均来说插入排序算法的时间复杂度为 O(n^2^)

因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。


希尔排序

希尔排序

算法思想

希尔排序是对插入排序的改进,使得其对较大规模且无序的数据排序会有效率。

首先它把较大的数据集合分割成若干个小组(逻辑上分组),然后对每一个小组分别进行插入排序,此时,插入排序所作用的数据量比较小(每一个小组),插入的效率比较高。

可以看出,他是按下标相隔距离为 4 分的组,也就是说把下标相差 4 的分到一组,比如这个例子中 a[0] 与 a[4] 是一组、a[1] 与 a[5] 是一组…,这里的差值(距离)被称为增量。

每个分组进行插入排序后,各个分组就变成了有序的了(整体不一定有序)

此时,整个数组变的部分有序了(有序程度可能不是很高)

然后缩小增量为上个增量的一半,继续划分分组,此时,每个分组元素个数多了,但是,数组变的部分有序了,插入排序效率同样比高。

同理对每个分组进行排序(插入排序),使其每个分组各自有序。

最后设置增量为上一个增量的一半,则整个数组被分为一组,此时,整个数组已经接近有序了,插入排序效率高。

同理,对这仅有的一组数据进行排序,排序完成。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const shellSort = array => {
let gap = Math.floor(array.length / 2) - 1;
while (gap >= 1) {
// 按组进行插入排序
for (let i = gap; i < array.length; i++) {
for (let j = i - gap; j >= 0; j -= gap) {
// 这里就是纯插入排序的思想了
if (array[j] > array[j + gap]) {
swap(j, j + gap, array);
}
}
}
gap = Math.floor(gap / 2);
}
console.log(array);
};

性能分析

希尔排序的复杂度和 增量序列是相关的{1, 2, 4, 8, ...} 这种序列并不是很好的增量序列,使用这个增量序列的时间复杂度(最坏情形)是 O(n^2^)

Hibbard 提出了另一个增量序列 {1, 3, 7,..., 2k - 1},这种序列的时间复杂度(最坏情形)为 O(n^1.5^)

Sedgewick 提出了几种增量序列,其最坏情形运行时间为 O(n^1.3^),其中最好的一个序列是 {1, 5, 19, 41, 109, ...}


快速排序

快速排序

算法思想

递归与分治,通过一趟排序将序列分成左右两部分,其中左半部分的的值均比右半部分的值小,
然后再分别对左右部分的记录进行排序,直到整个序列有序。

思路

  • 从当前序列中找出一个关键值 key,一般取数组的第一个元素;
  • 然后遍历当前数组,如果当前值比 key 要小,则放到其左侧;
  • 反之,如果当前的值比 key 大,则放到其右侧;
  • 当遍历完一次数组后,key 的位置就已经确定了;
  • 此时,递归去位于 key 的两侧的子集,重复上述过程,直到子集中元素只有一个为止。
是的,快排的思想就是这样。但是根据编程语言的不同,实现则不同。这里使用,下面的代码实现会使用到 JavaScript 中的数组拼接(解构运算符)去拼接多个数组。当然,Python 也可以很方便的完成。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const quickSort = array => {
if (array.length <= 1) return array;
let smaller = [];
let bigger = [];
let equal = [array[0]];
for (let i = 1; i < array.length; i++) {
if (array[i] > array[0]) bigger.push(array[i]);
else if (array[i] < array[0]) smaller.push(array[i]);
else equal.push(array[i]);
}
return [...quickSort(smaller), ...equal, ...quickSort(bigger)];
// 因为 quickSort 函数会返回一个数组,... 是解构运算符
// ...[1, 2, 3] 会变成 1, 2, 3
// [...[1, 2, 3], ...[4, 5, 6]] 就是 [1, 2, 3, 4, 5, 6]
};
第一次看见这样去写快排是用 Python 写的,当时给我整蒙了。

性能分析

快速排序的 一次划分算法 从两头交替搜索,直到 low 和 high 重合(这种说法是用指针去原地调换数组中元素的值,其实就是搜索完一遍当前的数组),因此其时间复杂度是 O(n) ;而整个快速排序算法的时间复杂度与划分的趟数有关。

理想的情况是:每次划分所选择的中间数 恰好将当前序列几乎等分,经过 log2n 趟划分,便可得到长度为 1 的子表。这样,整个算法的时间复杂度为 O(n log2n)

最坏的情况是:每次所选的中间数是当前序列中的最大或最小元素,这使得每次划分所得的子表中一个为空表,另一子表的长度为原表的长度 -1。这样,长度为 n 的数据表的快速排序需要经过 n 趟划分,使得整个排序算法的时间复杂度为 O(n2)

为改善最坏情况下的时间性能,可采用其他方法选取中间数。通常采用“三者值取中”方法,即比较 H->r[low].keyH->r[high].keyH->r[(10w + high) / 2].key,取三者中关键字为中值的元素为中间数。

可以证明,快速排序的 平均时间复杂度O(n log2n)。因此,该排序方法被认为是目前最好的一种内部排序方法


堆排序

什么是堆

堆是一种非线性结构,可以把堆看作一个数组,也可以被看作一个完全二叉树,通俗来讲堆其实就是 利用完全二叉树的结构来维护的一维数组

按照堆的特点可以把堆分为大顶堆和小顶堆:

  • 大顶堆:每个结点的值都大于或等于其左右孩子结点的值
  • 小顶堆:每个结点的值都小于或等于其左右孩子结点的值
大小顶堆

上面的“大顶堆”所对应的数组就是:

大顶堆数组

我们用简单的公式来描述一下堆的定义就是:

  • 大顶堆:arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2 * i + 2]
  • 小顶堆:arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 2]

堆的这种特性非常的有用,堆常常被当做优先队列使用,因为可以快速的访问到“最重要”的元素。

算法思想

不断地构建大、小顶堆,这样根元素(即数组下标为 0 的元素)就是尚未排序的最大、最小值。

即,通过不断维护堆的解构去依次地找到按照大小顺序所排序的元素,从而实现排序。

思路

上面提到过大顶堆的特点:每个结点的值都大于或等于其左右孩子结点的值。我们把大顶堆构建完毕后根节点的值一定是最大的,然后把根节点的和最后一个元素(也可以说最后一个节点)交换位置,那么末尾元素此时就是最大元素了。

  1. 先将 n 个元素的无序序列,构建成大顶堆;
  2. 将根节点与最后一个元素交换位置,(将最大元素”沉”到数组末端);
  3. 交换过后可能不再满足大顶堆的条件,所以需要将剩下的 n - 1 个元素重新构建成大顶堆;
  4. 重复第二步、第三步直到整个数组排序完成。

构建大顶堆的方法

假设我们将要被排序的数组为 [7, 3, 8, 5, 1, 2],这个二叉树必须要会画出来。

  • 7 就是根节点,其左、右孩子分别为 3 和 8;
  • 3 的左、右孩子分别是 5 和 1;
  • 8 的左孩子是 2;

先要找到最后一个非叶子节点,数组的长度为 6,那么最后一个非叶子节点就是:长度 / 2 - 1,也就是 6 / 2 - 1 = 2,即下标为 2 的元素,就是 8

然后下一步就是比较该节点值和它的子树值,如果该节点小于其左 \ 右子树的值就交换(意思就是将最大的值放到该节点)。

  • 8 只有一个左子树,左子树的值为 2,8 > 2 不需要调整;
  • 然后再找下一个非叶子节点,就是把刚刚算出来的 2 减去 1 就好,得到 3 这个节点;
  • 3 的直接子节点中,左孩子 5 比 3 大,所以要把 3 和 5 交换;
  • 交换后,再找下一个非叶子节点,就是根元素 7 了;
  • 7 的左子树为 5(刚刚换的),右子树为 8,所以 7 要和 8 交换位置;

现在,这颗二叉树是这样的:

  • 8 是根节点,其左、右孩子分别为 5 和 7;
  • 5 的左、右孩子分别是 3 和 1;
  • 7 的左孩子是 2;

此时,这个大顶堆就好了,其根元素是 8,也就是序列中最大的元素,对应的数组是 [8, 5, 7, 3, 1, 2]

现在需要将根元素与最后一个元素交换位置,即将 82 交换,即数组变为了:[2, 5, 7, 3, 1, 8]

此时,8 这个数值就排序完毕了,我们假设数组的长度减少了 1,因为不需要再去计算 8 了,将其从 逻辑上 移出这个堆。

随后不断重复上述方法,直到只剩最后一个根元素位置,即,不存在任何的非叶子节点了。此时,因为每次构建一次大顶堆都会把最大的元素先移动到根节点,再与 当前堆 中最后一个元素交换位置,所以在堆中只剩一个节点时,排序就已经完成了

代码实现

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
const heapSort = array => {
let logicArrayLength = array.length; // 逻辑上的数组长度
while (logicArrayLength > 1) {
let lastNotLeafNodeIndex = Math.floor(logicArrayLength / 2) - 1;
// 获得最后一个非叶子节点的下标
for (let i = lastNotLeafNodeIndex; i >= 0; i--) {
// 不断向前遍历所有的非叶子节点
let leftChildIndex = 2 * i + 1; // 左儿子
let rightChildIndex = 2 * i + 2; // 右儿子
if (leftChildIndex < logicArrayLength) {
// 防止下标越界
if (array[leftChildIndex] > array[i]) {
// 如果左儿子比当前节点大,就交换两数
swap(leftChildIndex, i, array);
}
}
if (rightChildIndex < logicArrayLength) {
// 如果右儿子小于被当前这个非叶子节点(可能此时已经和左孩子交换过了)
if (array[rightChildIndex] > array[i]) {
// 如果右儿子比当前节点大,就交换两数
swap(rightChildIndex, i, array);
}
}
}
// 此时,大顶堆已经构建完成了,需要交换数据
swap(0, logicArrayLength - 1, array);
logicArrayLength--; // 逻辑长度--,即堆中的大小减一
}
console.log(array);
};

性能分析

堆排序是一种选择排序,整体主要由构建初始堆 + 交换堆顶元素和末尾元素并重建堆两部分组成。

其中构建初始堆经推导复杂度为 O(n),在交换并重建堆的过程中,需交换 n - 1 次,而重建堆的过程中,根据完全二叉树的性质,[log2(n - 1), log2(n - 2)…1] 逐步递减,近似为 n * log2n

所以堆排序时间复杂度一般认为就是 O(n log2n) 级。


基数排序

(这是我个人觉得最神奇的一个排序了)

基数排序

算法思想(思路)

通过序列中各个元素的值,对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。

  • 分配:我们将 array[i] 中的元素取出,首先确定其个位上的数字,根据该数字分配到与之序号相同的桶中;
  • 收集:当序列中所有的元素都分配到对应的桶中,再按照顺序依次将桶中的元素收集形成新的一个待排序列 array[]

对新形成的序列 array[] 重复执行分配和收集元素中的十位、百位…直到分配完该序列中的最高位,则排序结束。

代码实现

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
const radixSort = array => {
let bucket = [[], [], [], [], [], [], [], [], [], []];
// 分别代表 0~9 这十个数
let nowRadix = 0; // 0 代表个位数
let maxRadix = -1; // 通过第一遍轮询,可以找到最大的基数是多少
let first = true; // 第一次轮询标记
while (maxRadix === -1 || nowRadix < maxRadix) {
array.forEach(value => {
let radix = Math.floor(value / Math.pow(10, nowRadix)) % 10;
// 这样就可以拿到每个数当前的基数了
bucket[radix].push(value);
if (first) maxRadix = Math.max(maxRadix, (value + '').length);
// 第一次轮询需要取得最大的数的位数,以便基数排序
});
if (first) first = false;
array = []; // 清空原来的数据
bucket.forEach(value => {
while (value.length !== 0) {
array.push(value.shift());
// 按顺序将数据从桶中拿出
}
});
nowRadix++; // 基数增加一位
}
console.log(array);
};

性能分析

时间效率:设待排序列为 n 个记录,d 个关键码,关键码的取值范围为 radix,则进行链式基数排序的时间复杂度为 O(d(n + radix))。其中,一趟分配时间复杂度为 O(n),一趟收集时间复杂度为 O(radix),共进行 d 趟分配和收集。

空间效率:需要 2 * radix 个指向队列的辅助空间,以及用于静态链表的 n 个指针。


归并排序

归并排序

算法思想

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。

分治

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为 log2n

代码实现

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
const mergeSort = array => {
if (array.length <= 1) return array; // 递归出口

// 求出划分边界
const middle = Math.floor(array.length / 2);

// 拿到左侧和右侧的数组
let left = array.splice(0, middle);
let right = array;

// 分
left = mergeSort(left);
right = mergeSort(right);

// 治
let temp = [];
let cLeft = 0;
let cRight = 0;
while (cLeft < left.length && cRight < right.length) {
left[cLeft] < right[cRight] ? temp.push(left[cLeft++]) : temp.push(right[cRight++]);
// 这里就是合并两个有序数组的方法
}
if (cLeft !== left.length) {
temp.push(...left.splice(cLeft));
}
if (cRight !== right.length) {
temp.push(...right.splice(cRight));
}

return temp; // 返回结果
};

性能分析

归并排序比较占用内存,但却是一种效率高且稳定的算法。

在传统的归并排序中,其时间复杂度为 O(log2n)


总结

一图胜千言部分来了。

害,归并的实现其实写起来也并不难
-------------本文结束 Euphoria 在此感谢您的阅读-------------

本文标题:八大排序大合集

文章作者:王钦弘

发布时间:2020年02月21日 - 15:41

最后更新:2020年02月21日 - 21:43

原始链接:https://www.wqh4u.cn/2020/02/21/%E5%85%AB%E5%A4%A7%E6%8E%92%E5%BA%8F%E5%A4%A7%E5%90%88%E9%9B%86/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

您的支持将鼓励 Euphoria 继续创作!
(如果你还是学生请千万不要打赏!留点钱在学习上啊!)