Appearance
冒泡、插入和选择排序
冒泡排序
冒泡排序之后操作相邻的两个数据,每次冒泡都会依次对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足,就将它们交换。一次冒泡至少让一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序。
看一个例子
对一组数据 4, 5, 6, 3, 2, 1,从小到大排序。第一次冒泡的过程是这样的:
值得注意的是,冒泡算法是可以优化的。当某次冒泡操作已经没有数据交换了,说明已经达到完全有序,不用再继续执行后续的冒泡操作了。
代码实现
结合上面的冒泡过程,实现一下冒泡
js
function bubbleSort(arr) {
if (arr.length <= 1) return;
for (let i = 0; i < arr.length; i++) {
// 是否有数据交换
let flag = false
// -i:通过 i 区分已排序区间和未排序区间,每次将一个元素移动
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
flag = true
}
}
// 如果没有数据交换,说明已经有序
if (!flag) break
}
console.log(arr)
}
分析冒泡排序
结合之前分析排序算法的三个方面,现在看看冒泡排序。
冒泡排序是原地排序算法吗?
冒泡的过程只涉及相邻的数据的交换操作,是需要常量级的临时空间,所以它的空间复杂度是 O(1),是一种原地排序。
冒泡排序是稳定的排序算法吗?
在冒泡排序中,只要交换才可以改变两个元素的前后顺序。为了保证排序算法的稳定性,当相邻两个元素大小相等时,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。
冒泡排序的时间复杂度是多少?
- 最好情况时间复杂度
最好情况下,数据已经是有序的了,只需要一次冒泡操作,就可以结束,所以最好情况时间复杂度是 O(n)。
- 最坏情况时间复杂度
最坏情况复杂度是,要排序的数据是倒序的,我们需要进行 n 次冒泡操作,所以最坏情况时间复杂度是 O(n^2)。
- 冒泡排序的时间复杂度是多少?
包含 n 个数据的数组,这 n 个数据有 n! 中排列方式,用概率论方法定量分析平均复杂度太麻烦了。这里通过有序度和逆序度两个概念分析。
有序度是指数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是:a[i] < a[j],(i<j)。
例如数组 [1, 2, 3] 的有序元素对有:(1, 2)、(1, 3)、(2, 3),所有有序度是 3。
同理,对于一个倒序排列的数组,比如 6,5,4,3,2,1,有序度是 0;对于一个完全有序的数组,比如 1,2,3,4,5,6,有序度就是 n * (n-1)/2,也就是 15。我们把这种完全有序的数组的有序度叫作满有序度。
逆序度的定义正好和有序度相反,就是指数组中不具有有序关系的元素对的个数。用数学表达式表示就是:a[i] > a[j],(i<j)。
冒泡包含两个操作,比较和交换。每交换一次,有序度就加 1。不管算法怎么改进,交换的次数总是确定的,即为逆序度,也就是 n * (n-1)/2 - 初始有序度。
所以包含 n 个数据的数组进行排序,最好情况下,初始有序度为 n*(n-1)/2,不需要进行交换;最坏情况下,初始有序度为 0,所以需要进行 n*(n-1)/2 次交换。
取一个中间值 n*(n-1)/4 来表示平均情况,也就是说平均情况下,需要 n*(n-1)/4 次交换,比较操作肯定比交换操作多,而复杂度的上限是 O(n^2),所以平均情况下的时间复杂度就是 O(n^2)。
插入排序
我们将数组的数据分成两个区间,已排序区间和未排序区间。初始时,已排序区间只有一个元素,就是数组的第一个元素。
插入排序算法的核心就是取未排序区间中的元素,在已排序的区间中找到合适的位置将其插入,并保证已排序区间数据一直有序。重复这个过程,知道未排序的区间中元素为空,排序结束。
看一个例子
对一组数据 4, 5, 6, 1, 3, 2,从小到大排序。
插入排序也包含两个操作,比较和移动。将一个数据 a 插入到已排序区间时,需要将 a 与已排序区间的元素依次比较大小,找到合适的插入位置。找到插入位置之后,还需要先将插入点之后的元素顺序往后移动一位,这样才能腾出位置给元素 a 插入。
对于一个给定的初始序列,移动操作次数总是固定的,就是等于逆序度。
上面的这种数据,有序度为 5,所以逆序度 6*(6-1)/2 - 5 = 10。插入排序中,数据移动的个数总和也等于 3 + 3 + 4 = 10。
代码实现
结合插入排序的过程,用代码实现以下
js
function insertionSort(arr) {
if (arr.length <= 1) return;
for (let i = 1; i < arr.length; i++) {
// 从未排序区间取出一个元素
let cur = arr[i];
let j = i - 1;
for (; j >= 0; j--) {
if (arr[j] > cur) {
// 如果大于 cur ,则将 arr[j] 向后移动
arr[j + 1] = arr[j];
} else {
break;
}
}
// 插入数据
// j+1:for 循环最后 j--,实际上就是插入 arr[j] 的位置
arr[j+1] = cur;
}
console.log(arr);
}
var arr = [4, 5, 6, 1, 3, 2]
insertionSort(arr);
分析插入排序
和冒泡排序的分析一样
插入排序是原地排序算法吗?
从实现代码来看,很明显,插入排序也不需要额外的存储空间,所以空间复杂度是 O(1),所以也是一个原地排序算法。
插入排序是稳定的排序算法吗?
在插入排序中,对于值相同的元素,可以将后面出现的元素插入到前端出现的元素之后,所以插入排序是稳定的排序算法。
插入排序的时间复杂度是多少?
- 最好情况时间复杂度
最好的情况下,数据是有序的,在有序区间里,每次从尾到位查找插入位置,只需要比较一个数据就能确定插入位置,所以,最好情况时间复杂度是 O(n)。
- 最坏情况时间复杂度
如果数据是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据,最坏时间复杂度为 O(n^2)。
- 平均情况时间复杂度
在数组插入一个数据的平均时间复杂度是 O(n)。对于插入排序来说,每次插入操作度相当于在数组中插入一个数据,循环执行 n 次插入操作,所以平均时间复杂度 O(n^2)。
选择排序
选择排序的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次从未排序区间中找到最小的元素,将其放到已排序区间的末尾。初始已排序区间为空。
看看一个例子
对一组数据 4, 5, 6, 3, 2, 1,从小到大排序。
代码实现
根据插入排序的过程,用代码实现一下
js
function selectionSort(arr) {
if (arr.length <= 1) return;
for (let i = 0; i < arr.length; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
// 找到最小的元素位置!
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
// 将最小元素插入到已排序区间的末尾
let temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
console.log(arr);
}
var arr = [4, 5, 6, 3, 2, 1];
selectionSort(arr);
选择排序的空间复杂度是 O(1),是一种原地排序算法。
不是一种稳定的排序算法。选择排序每次都要找到剩余未排序元素中最小值,并和前面的元素交换位置,这样就破坏了稳定性。例如 5, 8, 5, 2, 9 这组数据,第一次找到最小值 2,然后和第一个 5 交换位置,第一个 5 和第二个 5 的位置就变了,所以就不稳定了。
最好情况、最坏情况、平均情况时间复杂度都是 O(n^2)。
相比于冒泡排序和插入排序,选择排序就稍微逊色了。
那是选择冒泡还是插入排序呢
冒泡和插入的时间复杂度是一样,那为什么插入要比冒泡排序更受欢迎呢?
从代码的实现上,冒泡的交换数据要比插入排序的数据移动要复杂,冒泡需要 3 个赋值操作,而插入只需要 1 个。
js
// 冒泡排序
if (arr[j] > arr[j + 1]) {
const temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
flag = true
}
// 插入排序
if (arr[j] > cur) {
arr[j + 1] = arr[j];
} else {
break;
}
把一个赋值语句的执行时间粗略的记为单位时间(unit_time),然后分别用冒泡排序和插入排序对同一个逆序度是 K 的数组进行排序。
冒泡需要 K 次交换,每次需要 3*K 的单位时间。插入需要 K 次移动,每次需要 K 的单位时间。
可以造一下数据来测试一下,做个性能对比。随机生成了包含 10000 个元素的数组,冒泡排序需要 247ms,而插入排序只需要 65ms。
所以虽然冒泡排序和选择排序的时间复杂度都是 O(n^2),但是考虑到性能的话,肯定优先选择插入排序。
js
let arr = [];
for (let i = 0; i < 10000; i++) {
arr.push(Math.random() * 10000);
}
let a = arr.slice();
let b = arr.slice();
var begin, end;
begin = Date.now();
bubbleSort(a);
end = Date.now();
console.log(end - begin); // 247ms
begin = Date.now();
insertionSort(b);
end = Date.now();
console.log(end - begin); // 65ms
总结
分析、评价一个算法,需要从执行效率、内存消耗和稳定性三个方面来看。
算法 | 空间复杂度 | 稳定性 | 时间复杂度(最好、最坏、平均) |
---|---|---|---|
冒泡排序 | O(1) | 稳定 | O(n)、O(n^2)、O(n^2) |
冒泡排序 | O(1) | 稳定 | O(n)、O(n^2)、O(n^2) |
冒泡排序 | O(1) | 不稳定 | O(n^2)、O(n^2)、O(n^2) |
相比之下,插入排序是最有用的。对于小规模的数据,这三种算法用起来非常高效,但是在大规模数据排序的时候,这个时间复杂度还是比较高,这个时候应该选用 O(nlogn) 的算法。