冒泡排序
工作原理
重复遍历序列，比较相邻的两个元素，如果这两个元素顺序不正确，则交换。重复以上步骤直到排序完成。
js代码实现 + 效率测试
运算10次，平均耗时1018 ms
// 创建 20000 个随机数，数值范围：1 - 100000
let ary = [];
for (let i = 0; i < 20000; i++) {
ary.push( Math.floor( Math.random()*99999 + 1 ) );
}// 冒泡排序
console.time( '冒泡排序' );
let len = ary.length;
while (len > 0) {
for (let i = 0; i < len; i++) {
if (ary[i] > ary[i+1]) {
let temp = ary[i];ary[i] = ary[i+1];ary[i+1] = temp;}}len--;
}
console.timeEnd( '冒泡排序' );
选择排序
工作原理
首先在未排序的序列中找到最小（或最大）的元素。然后将其与未排序的序列中最左侧的元素进行交换。以此类推，直到排序完成。
js代码实现 + 效率测试
运算10次，平均耗时344 ms
// 创建 20000 个随机数，数值范围：1 - 100000
let ary = [];
for (let i = 0; i < 20000; i++) {
ary.push( Math.floor( Math.random()*99999 + 1 ) );
}// 选择排序 以每次找到最小的元素为例
console.time( '选择排序' );
let start = 0, len = ary.length;
while (start < len - 1) {
let minIdx = start, min = ary[start];for (let i = start; i < len; i++) {
if (ary[i] < min) {
minIdx = i;min = ary[i];}}if (minIdx !== start) {
let temp = ary[start];ary[start] = ary[minIdx];ary[minIdx] = temp;}start++;
}
console.timeEnd( '选择排序' );
插入排序
工作原理
通过构建有序序列，对未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。
js代码实现 + 效率测试
运算10次，平均耗时121 ms
// 创建 20000 个随机数，数值范围：1 - 100000
let ary = [];
for (let i = 0; i < 20000; i++) {
ary.push( Math.floor( Math.random()*99999 + 1 ) );
}// 插入排序
console.time( '插入排序' );
let len = ary.length;
for (let i = 1; i < len; i++) {
let curr = ary[i],j = i - 1;while (j >= 0) {
if (ary[j] > curr) {
ary[j+1] = ary[j];}else {
break;}j -= 1;}ary[j+1] = curr;
}
console.timeEnd( '插入排序' );
希尔排序
工作原理
希尔排序，是插入排序的一种更高效的改进版本。
它是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。希尔排序通过将序列分为几个区域来提升插入排序的性能，这样可以让一个元素一次性地朝最终位置前进一大步。然后再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序。但是到了这步，需排序的数据几乎是已排好 的了（此时插入排序较快）。
js代码实现 + 效率测试
运算10次，平均耗时16.79 ms
// 创建 20000 个随机数，数值范围：1 - 100000
let ary = [];
for (let i = 0; i < 20000; i++) {
ary.push( Math.floor( Math.random()*99999 + 1 ) );
}// 希尔排序
console.time( '希尔排序' );
let len = ary.length,step = Math.floor(len / 2 );
while (step > 0) {
for (let i = 0; i < len; i++) {
let curr = ary[i];let j = i;while (j >= step && ary[j - step] > curr) {
ary[j] = ary[j - step];j -= step;}ary[j] = curr;}step = Math.floor(step / 2);
}
console.timeEnd( '希尔排序' );
快速排序（应用最为广泛）
工作原理
使用分治法来把一个序列分为两个子序列，然后递归地排序这两个子序列。
快速排序步骤为：
- 挑选基准值：从数列中挑出一个元素，称为“基准”。
- 分割：重新排序数列，所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准后面。在这个分割结束之后，对基准值的排序就已经完成。
- 递归排序子序列：分别递归地将小于和大于基准值元素的子序列排序。
js代码实现 + 效率测试
运算10次，平均耗时19.58 ms
// 创建 20000 个随机数，数值范围：1 - 100000
let ary = [];
for (let i = 0; i < 20000; i++) {
ary.push( Math.floor( Math.random()*99999 + 1 ) );
}// 快速排序 基准默认总是取当前区间的最后一个元素
function quickSort(ary, start, end) {
let _quickSort = function(ary, start, end) {
if (end <= start) {
return ;}let pivot = ary[end],left = start,right = end - 1;while (left < right) {
while (ary[left] < pivot && left < right) left++;while (ary[right] >= pivot && left < right) right--;[ary[left], ary[right]] = [ary[right], ary[left]];}if (ary[left] >= pivot) {
[ary[left], ary[end]] = [ary[end], ary[left]];}else {
left++;}_quickSort(ary, start, left - 1);_quickSort(ary, left + 1, end);}_quickSort(ary, start, end);
}
console.time( '快速排序' );
quickSort(ary, 0, ary.length - 1);
console.timeEnd( '快速排序' );