前端常见排序方式及其性能比较
前端常见排序方式及其性能比较
这是笔者正在进行中的前端基础项目的实验性探究之一。
实验方法：随机生成1000条（0-999）整数数据。分别对其在不同数据量进行排序10次。统计平均时间。
1. 冒泡排序
无论学习什么编程语言，接触到的第一种排序算法应该就是冒泡排序。这里借用了一张动画进行说明。
1.相邻两个数两两相比，n[i]跟n[j+1]比，如果n[i]>n[j+1]，则将两个数进行交换，2.j++, 重复以上步骤，第一趟结束后，最大数就会被确定在最后一位，这就是冒泡排序又称大（小）数沉底，3.i++,重复以上步骤，直到结束，排序完成。
由此可写出排序的js代码：
const sort = (function () { return { // 冒泡排序 buble(data) { for (let i = 0; i < data.length; i++) { for (let j = 0; j < data.length - i; j++) { if (data[j] > data[j + 1]) { let tmp = data[j]; data[j] = data[j + 1]; data[j + 1] = tmp; } } }
return data; }}网上还有采用es6解构来表达交换位置的写法，看起来很优雅：
// 冒泡排序2 buble2(data) { for (let i = 0; i < data.length ; i++) { for (let j = 0; j < data.length - i; j++) { if (data[j] > data[j + 1]) { [data[j], data[j + 1]] = [data[j + 1], data[j]] /*交换元素*/ } //console.log(data) } }
return data; },那我们也把它纳入到sort类中，计算一下：
数据量 | buble排序用时（ms） | buble2排序用时（ms） |
|---|---|---|
1000 | 7.9 | 15.8 |
5000 | 77.3 | 90.1 |
10000 | 321.4 | 342.1 |
25000 | 2097.7 | 2118.1 |
100000 | 34270.6 | 未测 |
125000 | 54216.5 | 未测 |
625000 | 爆栈 | 未测 |
可见buble2中es6+ 的写法，在耗时方面的性能表现稍差。接下来涉及数组互换的内容将采用传统的写法。
buble排序与数据量自然对数（lnN）与时间做拟合：
也就说 冒泡排序 平均耗费时间 t 与 数据量 N 关系大致为
【注】此处拟合仅代表基本趋势分析，难以体现时间复杂度的准确关系。下同。
2. 选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
•初始状态：无序区为R[1..n]，有序区为空；•第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；•n-1趟结束，数组有序化了。
javascript 的实现如下：
// 选择排序select(data) { for (let i = 0; i < data.length; i++) { for (let j = i; j < data.length; j++) { if (data[i] > data[j]) { let tmp = data[i]; data[i] = data[j]; data[j] = tmp; } } }
return data;}数据量 | select排序用时（ms） |
|---|---|
1000 | 7.2 |
5000 | 47.0 |
10000 | 148.3 |
25000 | 786.8 |
100000 | 11480.8 |
125000 | 17882.6 |
625000 | 未全测 440s左右 |
也就说 因此选择排序 耗费时间 t 与 数据量 N 关系大致为
选择排序也是表现最稳定的排序算法之一，无论什么数据进去都是O(n2)的时间复杂度，不占用额外的内存空间，适用较小规模的数据排序。
3. 插入排序
插入排序核心--扑克牌思想：就想着自己在打扑克牌，接起来一张，放哪里无所谓，再接起来一张，比第一张小，放左边，继续接，可能是中间数，就插在中间....
简单来讲就是以第一个插入的数为基数，小的往左放大的往右放，然后不断循环基数如果第一个最小，那么就从第二个开始比较，依次循环。
在这里，有序区范围不断扩大。等“完全占领”无序区，就排好了。
JavaScript实现方案如下
// 插入排序(扑克牌法)insert(data) { for (let i = 1; i < data.length; i++) { for (let j = i; j > 0; j--) { if (data[j] < data[j - 1]) { let tmp = data[j]; data[j] = data[j - 1]; data[j - 1] = tmp; }else{ break; } } }
return data;},运行测试结果
数据量 | insert排序用时（ms） |
|---|---|
1000 | 6.1 |
5000 | 28.6 |
10000 | 97.5 |
25000 | 587.3 |
100000 | 9291.7 |
125000 | 14520.5 |
625000 | 未测 |
也就说 因此插入排序 平均耗费时间 t 与 数据量 N 关系大致为
4. 快速排序
前面的比较在快速排序面前看来，就显得是菜鸡互啄了。
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
从数列中挑出一个元素，称为 “基准”（pivot）；重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
// 快速排序quick(arr) { if(arr.length <= 1) { return arr; //递归出口 } var left = [], right = [], current = arr.splice(0,1); //注意splice后，数组长度少了一个 for(let i = 0; i < arr.length; i++) { if(arr[i] < current) { left.push(arr[i]) //放在左边 } else { right.push(arr[i]) //放在右边 } } // console.log(this) return this.quick(left).concat(current,this.quick(right)); //递归}运行测试结果
数据量 | quick排序用时（ms） |
|---|---|
1000 | 11.1 |
5000 | 35.7 |
10000 | 80.0 |
25000 | 279.0 |
100000 | 2878.3 |
125000 | 4255.8 |
625000 | 97497.3 |
在拟合方案上，采用二项式建模
也就说 因此快速排序 平均耗费时间 t 与 数据量N的大致关系为
结论
在综合各个算法理论上的时间复杂度后，汇总得表：
不考虑机器性能，在较少数据量（小于10000）时，插入排序可以获得比较好的效果。在数据量较多时，快速排序的时间处理效率优势明显。
腾讯云开发者
