排序算法分析总结(附js实现)
本文对一些排序算法进行了简单分析,并给出了 javascript 的代码实现。因为本文包含了大量的排序算法,所以分析不会非常详细,适合有对排序算法有一定了解的同学。
本文内容其实不是很多,就是代码占了很多行。
总览
默认需要排序的数据结构为数组,时间复杂度为平均时间复杂度。
排序算法 | 时间复杂度 | 空间复杂度 | 是否稳定 |
---|---|---|---|
冒泡排序 | O(n^2) | O(1) | 稳定 |
插入排序 | O(n^2) | O(1) | 稳定 |
选择排序 | O(n^2) | O(1) | 不稳定 |
归并排序 | O(nlogn) | O(n) | 稳定 |
快速排序 | O(nlogn) | O(1) | 不稳定 |
下面代码实现,排序默认都是 从小到大 排序。
所有代码
我的 js 代码实现都放在 github:https://github.com/F-star/js-Data-Structures-and-Algorithms/tree/master/sort
代码仅供参考。
冒泡排序(Bubble Sort)
假设要进行冒泡排序的数据长度为 n。
冒泡排序会进行多次的冒泡操作,每次都会相邻数据比较,如果前一个数据比后一个数据大,就交换它们的位置(即让大的数据放在后面)。这样每次交换,至少有一个元素会移动到排序后应该在的位置。重复冒泡 n(或者说 n-1) 次,就完成了排序。
详细来说,第 i
(i 从 0 开始) 趟冒泡会对数组的前 n - i
个元素进行比较和交换操作,要对比的次数是 size - i - 1
。
冒泡排序总共要进行 n-1 次冒泡(当然你可以说是 n 次冒泡,不过最后一次冒泡只有一个元素,不用进行比较)。
优化
有时候,可能只进行了 n 次冒泡,数组就已经是有序的了,甚至数组本来就是有序的。这时候我们希望:当发现一次冒泡后,数组有序,就停止下一次的冒泡,返回当前的数组。
这时候我们可以在每一趟的冒泡前,声明一个变量 exchangeFlag,将其设置为 false。冒泡过程中,如果发生了数据交换,就将 exchangeFlag 设置为 true。结束一趟冒泡后,我们就可以通过 exchangeFlag 知道 数据是否发生过交换。如果没有发生交换,就说明数组有序,直接返回该数组即可;否则说明还没有排好序,继续下一趟冒泡。
代码实现
const bubbleSort = (a) => {
// 每次遍历找到最大(小)的数放到最后面的位置。
// 优化:如果某次冒泡操作没有数据交换,说明已经有序了。
// 双重循环。
if (a.length <= 1) return a;
// 这里的 i < len 改成 i < len - 1 也是正确的,因为最后第 len - 1次并不会执行。
for (let i = 0, len = a.length; i < len; i++) {
let exchangeFlag = false; // 是否发生过换
for (let j = 0; j < len - i - 1; j++) {
if (a[j] > a[j + 1]) {
[a[j], a[j + 1]] = [a[j + 1], a[j]];
exchangeFlag = true;
}
}
console.log(a)
if (exchangeFlag == false) return a;
}
}
// 测试
let array = [199, 3, 1, 2, 8, 21,4, 100, 8];
console.log (bubbleSort(array));
分析
1. 冒泡排序的时间复杂度是 O(n^2)
。
最好时间复杂度是 O(n)
,即第一趟进行 n-1
次比较后,发现原数组是有序的,结束冒泡。
最坏时间复杂度是 O(n^2)
,当原数组刚好是倒序排列时,即需要进行 n 次冒泡,要进行 (n-1) + (n-2) ... + 1 次比较后,用等比数列求和公式求和后并化简,即可求出最坏时间复杂度。
平均时间复杂度不好分析,它是 O(n^2)
2. 冒泡排序是 稳定 的排序算法。
这里的“稳定”指的是:排序后,值相等的数据的前后顺序保持不变。
相邻数据如果相等,不交换位置即可。
3. 冒泡排序是原地排序算法
原地排序指的是空间复杂度是 O(1) 的排序算法。
冒泡排序只做了相邻数据交换,另外有两个临时变量(交换时的临时变量、flag),只需要常量级的临时空间,空间复杂度为 O(1)
插入排序(Insertion Sort)
插入排序。本质是从 未排序的区域 内取出数据,放到 已排序区域 内,这个取出的数据会和已排序的区间内数据一一对比,找到正确的位置插入。
我们直接将数组分为 已排序区域 和 未排序区域。刚开始开始,已排序区域只有一个元素,即数组的第一个元素。插入的方式有两种:从前往后查找插入 和 从后往前查找插入。这里我选择 从后往前查找插入。
代码实现
const insertionSort = a => {
for (let i = 0, len = a.length; i < len; i++) {
let curr = a[i]; // 存储当前值,排序的时候,它对应的索引指向的值可能会在排序时被覆盖
for (let j = i - 1; j >= 0;j--) {
if (curr < a[j]) {
a[j + 1] = a[j];
} else {
break;
}
// 找到位置(0 或 curr >= a[j]时)
a[j] = curr;
}
}
return a;
}
分析
1. 插入排序的时间复杂度是:O(n^2)
当要排序的数据是有序的,我们每次插入已排序的区域,只需要比较一次,一共比较 n-1 次就结束了(注意这里是从后往前遍历已排序区域)。所以最好时间复杂度为 O(n)。
最坏时间复杂度是 O(n^2),是数据刚好是倒序的情况,每次都要遍历完 已排序区域的所有数据。
2. 插入排序是稳定排序
遍历已排序区域时,值相同的时候,放到最后的位置即可。
3. 插入排序是原地排序算法
不需要额外空间,是在数组上进行数据交换,所以插入排序是原地排序算法。
选择排序(Selection Sort)
选择排序也有一个 已排序区域 和一个 未排序区域。它和插入排序不同的地方在于:选择排序是从 未排序区域 中找出最小的值,放到 已排序区域的末尾。
为了减少内存消耗,我们也是直接在数组上进行数据的交换。
插入排序比冒泡排序优秀的原因
插入排序和冒泡排序的时间复杂度都是 O(n^2),元素交换次数也相同,但插入排序更优秀。原因是冒泡排序的交换,需要一个 tmp 的中间变量,来进行两个元素交换,这就变成了 3 个赋值操作。而插入排序(从后往前遍历已排序区域),不需要中间遍历,它是直接一些元素后移覆盖,只要1个赋值操作。
冒泡排序中数据的交换操作:
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
插入排序中数据的移动操作:
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
此外,插入排序还可以进行优化,变成 希尔排序。这里不具体说。
代码实现
const selectionSort = a => {
let tmp;
for (let i = 0, len = a.length; i < len; i++) {
let min = a[i], // 保存最小值,用于比较大小。
minIndex = i; // 保存未排序区间中,最小值对应的索引(方便进行元素交换)
for (let j = i; j < len; j++) {
if (a[j] < min) {
minIndex = j;
min =a[j]
}
}
tmp = a[minIndex];
a[minIndex] = a[i];
a[i] = tmp;
}
return a;
}
分析
1. 选择排序的时间复杂度是 O(n^2)
最好时间复杂度是 O(n^2)。因为每次从未排序区域内找出最小值,都要遍历未排序区域内的所有元素,一共要查找 n-1 次,所以时间复杂度是 O(n^2)。
最坏时间复杂度也是 O(n^2),理由同上。
2. 选择排序是原地排序算法
我们找到为排序区域的最小元素,会交换该元素和 排序区域的下一个位置的元素(即排序区域的第一个元素),然后 i 后移。只做了元素的交换,且只用到了常数级的内存空间(交换两个数据需要的一个临时遍历),因此选择排序是原地排序算法。
3. 选择排序是不稳定的排序算法
不稳定,是因为每次都要找最小值和前面的元素进行交换,这样会破坏稳定性。举个反例来证明:3 3 2, 第一次交换后,为 2 3 3,此时两个 3 的相对顺序就改变了。
当然你可以额外的创建一个大小为数组长度的空数组,来作为 已排序区域。这样做就不需要交换元素,可以做到排序稳定,但这样做耗费了额外的内存,变成了非原地排序算法。
归并排序
归并排序用到了 分治思想。分治思想的核心是:将一个大问题分解成多个小的问题,解决后合并为原问题。分治通常用递归来实现。分治和递归的区别是,分治是一种解决问题的处理思想,递归是一种编程技巧。
归并排序,会将数组从中间分成左右两部分。然后对这两个部分各自继续从中间分成两部分,直到无法再分。然后将分开的两部分进行排序合并(合并后数组有序),不停地往上排序合并,最终合并成一个有序数组。
说明下 merge 函数。它是将两个有序数组合并为一个有序数组,做法是创建一个空数组,长度为两个有序数组的大的一个。设置指针 i 和 j 分指向两个数组的第一个元素,取其中小的加入数组,对应的数组的指针后移。重复上面这个过程,直到一个数组为空,就将另一个数组的剩余元素都推入新数组。
另外,merge() 函数可以借助 哨兵 进行优化处理。具体我没研究,有空再考虑实现。
代码实现
归并的代码实现用到了递归,所以代码不是很好看懂。
const mergeSort = a => {
mergeSortC(a, 0, a.length - 1)
return a;
}
const mergeSortC = (a, p, r) => {
if (p >= r) return
let q = Math.floor( (p + r) / 2 ); // 这样取中间值,right.length >= left.length
mergeSortC(a, p, q);
mergeSortC(a, q+1, r);
merge(a, p, q, r) // p->q (q+1)->r 区域的两个数组合并。
}
/**
* merge方法(将两个有序数组合并成一个有序数组)
*/
function merge(a, p, q, r) {
let i = p,
j = q+1,
m = new Array(r - q); // 保存合并数据的数组
let k = 0;
while (i <= q && j <= r) {
if (a[i] <= a[j]) {
m[k] = a[i];
i++;
} else {
m[k] = a[j]
j++;
}
k++;
}
// 首先找出两个数组中,有剩余的元素的数组。
// 然后将剩余元素依次放入数组 m。
let start = i,
end = q;
if (j <= r) {
start = j;
end = r;
}
while (start <= end) {
m[k] = a[start];
start++;
k++;
}
// m的数据拷贝到 a。
for(let i = p; i <= r; i++) {
a[i] = m[i-p];
}
}
性能分析
归并排序的时间复杂度是 O(nlogn)
以下为简单推导过程,摘自 专栏-「数据结构与算法之美」。
问题a分解为子问题 b 和 c,设求解 a、b、c 的时间为 T(a)、T(b)、Y(c),则有
T(a) = T(b) + T(c) + K
而合并两个有序子数组的时间复杂度是 O(n),于是有
T(1) = C; n=1 时,只需要常量级的执行时间,所以表示为 C。
T(n) = 2*T(n/2) + n; n>1
化简后,得到 T(n)=Cn+nlog2n
。所以归并排序的时间复杂度是 O(nlogn)。
归并排序是稳定的排序
归并交换元素的情况发生在 合并 过程,只要让比较左右两个子数组时发现相等时,取左边数组的元素,就可以保证有序了。
归并排序 不是 原地排序
依然归并排序非常优秀(指时间复杂度),但,它的空间复杂度是 O(n)。因为进行合并操作时,需要申请一个临时数组,该数组的长度最大不会超过 n。
快速排序
快速排序,简称 “快排”。快排使用的是分区思想。
快排会取数组中的一个元素作为 pivot(分区点),将数组分为三部分:
- 小于 pivot 的部分
- pivot
- 大于或等于 pivot 的部分。
我们取左右两边的子数组,执行和上面所说的操作,直到区间缩小为0,此时整个数组就变成有序的了。
在归并排序中,我们用到一个 merge() 合并函数,而在快排中,我们也有一个 partition() 分区方法。该方法的作用是根据提供的区间范围,随机取一个 pivot,将该区间的数组的数据进行交换,最终将小于 pivot 的放左边,大于 pivot 的放右边,然后返回此时 pivot 的下标,作为下一次 递归 的参考点。
partition() 分区函数有一种巧妙的实现方式,可以实现原地排序。处理方式有点类似 选择排序。首先我们选一个 pivot,pivot 后的元素全都往前移动一个单位,然后pivot 放到末尾。接着我们将从左往右遍历数组,如果元素小于 pivot,就放入 “已处理区域”,具体操作就是类似插入操作那种,进行直接地交换;如果没有就不做操作,继续下一个元素,直到结束。最后将 pivot 也放 “已处理区间”。这样就实现了原地排序了。
另外,对 partition 进行适当的改造,就可以实现 “查找无序数组内第k大元素” 的算法。
代码实现
const quickSort = a => {
quickSortC(a, 0, a.length - 1)
return a;
}
/**
* 递归函数
* 参数意义同 partition 方法。
*/
function quickSortC(a, q, r) {
if (q >= r) {
// 提供的数组长度为1时,结束迭代。
return a;
}
let p = partition(a, q, r);
quickSortC(a, q, p - 1);
quickSortC(a, p + 1, r);
}
/**
* 随机选择一个元素作为 pivot,进行原地分区,最后返回其下标
*
* @param {Array} a 要排序的数组
* @param {number} p 起始索引
* @param {number} r 结束索引
* @return 基准的索引值,用于后续的递归。
*/
export function partition(a, p, r) {
// pivot 默认取最后一个,如果取得不是最后一个,就和最后一个交换位置。
let pivot = a[r],
tmp,
i = p; // 已排序区间的末尾索引。
// 类似选择排序,把小于 pivot 的元素,放到 已处理区间
for (; p < r; p++) {
if (a[p] < pivot) {
// 将 a[i] 放到 已处理区间。
tmp = a[p];
a[p] = a[i];
a[i] = tmp; // 这里可以简写为 [x, y] = [y, x]
i++;
}
}
// 将 pivot(即a[r])也放进 已处理区间
tmp = a[i];
a[i] = a[r];
a[r] = tmp;
return i;
}
快速排序和归并排序都用到了分治思想,递推公式和递归代码很很相似。它们的区别在于:归并排序是 由下而上 的,排序的过程发生在子数组合并过程。而快速排序是 由上而下 的,分区的时候,数组就开始趋向于有序,直到最后区间长度为1,数组就变得有序。
性能分析
1. 快速排序的时间复杂度是 O(nlogn)
快排的时间复杂度递推求解公式跟归并是相同的。所以,快排的时间复杂度也是 O(nlogn)。但这个公式成立的前提是每次分区都能正好将区间平分(即最好时间复杂度)。
当然平均复杂度也是 O(nlongn),不过不好推导,就不分析。
极端情况下,数组的数据已经有序,且取最后一个元素为 pivot,这样的分区是及其不均等的,共需要做大约 n 次的分区操作,才能完成快排。每次分区平均要扫描约 n/2 个元素。所以,快排的最坏时间复杂度是 O(n^2)
2. 快速排序是不稳定的排序
快速排序的分区过程,涉及到了交换操作,该交换操作类似 选择排序,是不稳定的排序。
3. 快速排序是原地排序
为了实现原地排序,我们前面对 parition 分区函数进行了巧妙的处理。
结尾
大概就是这样,做了简单的总结。如果文章有错误的地方,请给我留言。
还有一些排序打算下次再更新,可能会新开一篇文章,也可能直接修改这篇文章。