[ algorithm ] 经典排序算法的 JavaScript 代码的实现和适用场景总结
排序算法的梳理和 JS 代码实现
冒泡排序
遍历执行，判断是否前小后大，是的话位置不变，不是的话全部元素遍历完毕才算结束。
每一轮都是把最大的值交换到最后的位置，遍历的次数为 n - 1 个。冒泡排序是是所有排序中可以提前中止的算法，排序流程如图：
上面的遍历为一轮，一共发生了 5 次交换，红色框就是发生交换的位置最后得到第一轮排序后的结果 R1 。第二轮也是这样一个原理。
最后的遍历为：
冒泡排序的时间复杂度是 O( n2) 。 是一种稳定的排序算法。
比较次数和交换次数的公式分别是：
KCN = ( 1 / 2 ) n ( n - 1 );
RMN = ( 3 / 2 ) n ( n - 1 );
JavaScript 代码代码实现：
const data = [34, 1, 56, 18, 90, 78, 40, 2, 48];
const bubbleSort = () => {
for (let i = 0; i < data.length; i++) {
let flag = true;
for (let j = 0; j < data.length - i - 1; j++) {
if (data[j] > data[j + 1]) {
flag = false;
const temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
if (flag === true) break;
}
return data;
}
const sort = bubbleSort();
console.log(sort);flag 是标记是否已经全部符合前小右大规则，如果是的话可以提前中止遍历。是一种改进方法，没有必要完全遍历全部的元素。
输出结果：
[ 1, 2, 18, 34, 40, 48, 56, 78, 90 ]动图演示：
快速排序
首先，取数据的第一个元素作为枢轴记录，他的关键字是 pivotkey 。 有两个指向分别是 high 和 low 。其中 high 指向最后一个位置元素，而 low 指向第一个元素的位置。
low 指向的数据都应该小于基准数值，而 high 指向的数据都应该大于基准数值。第一轮排序如图：
首先获取基准值，也就是第一个值 24。 用 24 和 high 指向的 22 做比较，由于 high 指向必须大于基准值，而这里不符合，所以需要交换一个位置，24 和 22交换。
交换之后需要切换方向，这时轮到了 low 指向。原本的 low 指向 22 ，22 比较基准值小符合条件移动指向到 15，15也符合再移动到39 。39大于24 不符合 low 指向的规则，再用 24 与 39 交换。重复之前的规则，知道 low 和 high 重叠就找到了 24 的基准位且中止了第一轮的执行。
在 24 的左边，所有的数值都是比 24 小，右边的数值都是比 24 大。
之后的遍历都是重复上面的操作，找基准点切割直到只剩下最后一个数。
先遍历左侧直到排序完毕，再遍历右侧最终得到就过。
快速排序的计算时间是 O( nlog2n )，且是一种不稳定的排序算法。
JavaScript 代码实现：
const quickSortData = [22, 15, 20, 12, 18, 24, 70, 39, 51, 42,1];
const getPivotKey = (items, low, high)=>{
let pivot = items[low];
while ( low < high ){
while (low < high && items[high] > pivot){
--high;
}
items[low] = items[high];
while (low < high && items[low] <= pivot){
++low;
}
items[high] = items[low];
}
items[low] = pivot;
return low;
};
const quickSort = (items, low, high) => {
if(low < high){
let pivotkey = getPivotKey(items, low, high);
quickSort(items, low, pivotkey - 1);
quickSort(items, pivotkey + 1, high);
}
return items
}
const quick = quickSort(quickSortData, 0, quickSortData.length - 1);
console.log(quick);获取基准值，第一次 quickSort 排序左侧，第二次 quickSort 排序右侧，最后执行 return。
输出结果：
[1, 12, 15, 18, 20, 22, 24, 39, 42, 51, 70]动图演示：
选择排序
选择排序的基本思路就是依次向数组遍历，每一次遍历找到最小的值同时标记下来，在扫描完一圈之后将这个最小的值交换到本轮遍历的第一个数值。
JavaScript 代码实现：
const selectSortData = [4, 23, 1, 90, 30, 6, 43, 111, 92, 5, 24, 7, 89, 32, 1000, 209, 113, 920];
const selectionSort = (items) => {
let minIndex;
let temp;
for (let i = 0; i < items.length; i++) {
minIndex = i;
for (let j = i + 1; j < items.length; j++) {
if (items[j] < items[minIndex]) {
minIndex = j;
}
temp = items[i];
items[i] = items[minIndex];
items[minIndex] = temp;
}
}
return items;
}
const select = selectionSort(selectSortData);
console.log(select);输出结果：
[4, 5, 1, 6, 7, 24, 23, 32, 30, 89, 43, 90, 92, 111, 209, 920, 113, 1000]选择排序的平均时间是 O ( n2 )， 且是一种不稳定的排序方法。
比较次数和交换次数的公式分别是：
KCN = n ( n - 1 ) / 2 ;
RMN = 3n ( n - 1 );
动图演示：
插入排序
每次遍历将值进行对比，直接插入在 n-1 < n < n+1 的位置。
const insertSortData = [4, 23, 1, 90, 30, 6, 43, 111, 92, 5, 24, 7, 89, 32, 1000, 209, 113, 920];
const insertSort = (items) => {
for (let i = 1; i < items.length; i++) {
let key = items[i];
let j = i - 1;
while (j >= 0 && items[j] > key) {
items[j + 1] = items[j];
j--;
}
items[j + 1] = key;
}
return items;
};
const insert = insertSort(insertSortData);
console.log(insert);输出结果：
[4, 5, 1, 6, 7, 24, 23, 32, 30, 89, 43, 90, 92, 111, 209, 920, 113, 1000]动图演示：
归并排序
归并排序是排序算法中比较快的一种方法，他是使用一种 “ 空间换取时间 ”的方法来处理，意思是不需要像快速排序一样不停的移动和交换位置。归并排序他是做插入操作不需要做交换和移动。他建立了一个新的空间，专门用来将比较之后的排序的元素存放。提高了排序的速度但是就是消耗了一倍的空间。
他是实现思路是将初始序列分成前后两组，通过对比归并到目标序列之中。
使用 JavaScript 实现：
const mergeSortData = [4, 23, 1, 90, 30, 6, 43, 111, 92, 5, 24, 7, 89, 32, 1000, 209, 113, 920];
const merge = (left, right) => {
let result = [];
while (left && right && left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left && left.length) {
result.push(left.shift());
}
while (right && right.length) {
result.push(right.shift());
}
return result;
}
const mergeSort = (items) => {
if (items.length < 2) {
return items;
}
let middle = Math.floor(items.length / 2);
let left = items.slice(0, middle);
let right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
const merges = mergeSort(mergeSortData);
console.log(merges);输出结果：
[4, 5, 1, 6, 7, 24, 23, 32, 30, 89, 43, 90, 92, 111, 209, 920, 113, 1000]动图演示：
希尔排序
是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序
使用 JavaScript 实现：
const shellSortData = [4, 23, 1, 90, 30, 6, 43, 111, 92, 5, 24, 7, 89, 32, 1000, 209, 113, 920];
const shellSort = (items) => {
let temp = null;
let gap = 1;
while (gap < items.length / 5) {
gap = gap * 5 + 1;
}
for (gap; gap > 0; gap = Math.floor(gap / 5)) {
for (var i = gap; i < items.length; i++) {
temp = items[i];
for (var j = i - gap; j >= 0 && items[j] > temp; j -= gap) {
items[j + gap] = items[j];
}
items[j + gap] = temp;
}
}
return items;
}
const shell = shellSort(shellSortData);
console.log(shell);动图展示：
堆排序
堆排序是基于完全二叉树的顺序存放方式放在一个数组中，他的顺序是从上到下，从左到右。
算法的实现思路是：
- 一组数据需要先将这一组数据转化为二叉树的堆。
- 最大的节点和排在最后且没有被交换的节点进行交换。
- 重复上面的操作。
创建堆思路如图：
- 从右往左，从下往上找到第一个非叶子结点
- 判断是不是最大堆如果是的话判断下一个，如果不是的话将最大的节点和最小节点交换位置
- 交换之后还要在看看其他的节点是不是符合最大堆的规则，如果不是就需要重复上面的步骤。
- 拿走根节点和最后一个未交换位置的节点进行交换，这个节点就不会再改变位置了，在重复上面的步骤，知道剩下最后一个节点。
第一次执行之后，70 这个最大的值就被放到了最后。
这里分解第二次执行的步骤：
查找了 3 个堆后， 将 20 和 24 做了一个交换，而 70 已经是交换完毕的，所以可以忽略。
再交换 24 到尾部。之后再重复上面的操作即可。
堆排序的时间复杂度是o( nlog2n ) , 且是一个不稳定的排序。
JavaScript 代码实现：
const heapSortData = [4, 23, 1, 90, 30, 6, 43, 111, 92, 5, 24, 7, 89, 32, 1000, 209, 113, 920];
const create = (items, i, length) => {
let l = 2 * i + 1,
r = 2 * i + 2,
largest = i,
temp;
if (l < length && items[l] > items[largest]) {
largest = l;
}
if (r < length && items[r] > items[largest]) {
largest = r;
}
if (largest != i) {
temp = items[i];
items[i] = items[largest];
items[largest] = temp;
create(items, largest, length);
}
};
const heapSort = (items) => {
// 建堆
let temp = null;
let len = items.length;
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
create(items, i, len);
}
// 堆排序
for (let j = len - 1; j >= 1; j--) {
temp = items[0];
items[0] = items[j];
items[j] = temp;
create(items, 0, --len);
}
return items;
};
console.log(heapSort(heapSortData));输出结果：
[4, 5, 1, 6, 7, 24, 23, 32, 30, 89, 43, 90, 92, 111, 209, 920, 113, 1000]动图演示：
计数排序
计数排序使用一个额外的数组，其中第 i 个元素是待排序数组中值等于 i 的元素的个数。然后根据额外数组来将在排序数组中的元素排到正确的位置。它只能对整数进行排序。
计数排序是一种稳定的排序算法。
JavaScript 代码实现：
const countingSortData = [4, 23, 1, 90, 30, 6, 43, 111, 92, 5, 24, 7, 89, 32, 1000, 209, 113, 920];
const countingSort = (items) => {
let sort = [],
cache = [],
min = [],
max = items[0];
min = max;
for (let i = 0; i < items.length; i++) {
min = min <= items[i] ? min : items[i];
max = max >= items[i] ? max : items[i];
cache[items[i]] = cache[items[i]] ? cache[items[i]] + 1 : 1;
}
for (let j = +min; j < max; j++) {
cache[j + 1] = (cache[j + 1] || 0) + (cache[j] || 0);
}
for (var k = items.length - 1; k >= 0; k--) {
sort[cache[items[k]] - 1] = items[k];
cache[items[k]]--;
}
return sort;
}
const counting = countingSort(countingSortData);
console.log(counting);输出结果：
[4, 5, 1, 6, 7, 24, 23, 32, 30, 89, 43, 90, 92, 111, 209, 920, 113, 1000]动画展示：
桶排序
桶排序的原理就是将数据进行分区间插入归类，在归类的同时也做好排序的操作，在最后将各桶内的数据拼接起来。
桶排序的实现思路：
- 首先需要遍历数组，找到数组最大和最小值；
- 获取区间值，注意这里的计算需要加 1；
- 遍历数组计算出当前元素是属于哪个区间的。
- 计算出区间之后，填写入区间，但是需要进行判断是否是桶内最大值，不是还要排序。
- 桶内元素拼接，注意要做好兼容，因为不是每一个桶都有数据，可能出现 1 3 4,而 2 桶是没有的
JavaScript 代码实现：
const bucketSortData = [5, 24, 2, 91, 31, 7, 44, 112, 93, 6, 25, 8, 90, 33, 1001, 210, 114, 921];
const bucketSort = (items, num) => {
const itemsLength = items.length;
const bucket = [];
let result = [];
let itemMin = items[0];
let itemMax = items[0];
let space = null;
let n = 0;
// 找到数组最大和最小值；
for (let i = 1; i < itemsLength; i++) {
itemMin = itemMin <= items[i] ? itemMin : items[i];
itemMax = itemMax >= items[i] ? itemMax : items[i];
}
// 获取区间值，注意这里的计算需要加 1
space = (itemMax - itemMin + 1) / num;
for (let j = 0; j < itemsLength; j++) {
const index = Math.floor((items[j] - itemMin) / space);
if (bucket[index]) {
// 非空桶 需要排序
let k = bucket[index].length - 1;
while (bucket[index][k] > items[j]) {
bucket[index][k + 1] = bucket[index][k];
k--;
}
bucket[index][k + 1] = items[j];
} else {
// 空桶 初始化和 push
bucket[index] = [];
bucket[index].push(items[j])
}
}
// 桶内元素拼接
while (n < num) {
// 因为不是每一个桶都有数据，可能出现 1 3 4,而 2 桶是没有的
if (bucket[n]) {
result = result.concat(bucket[n]);
}
n++;
}
return result;
};
const bucketNum = 4;
const bucket = bucketSort(bucketSortData, bucketNum);
console.log(bucket);输出结果：
[5, 24, 2, 91, 31, 7, 44, 112, 93, 6, 25, 8, 90, 33, 1001, 210, 114, 921]动图展示：
基数排序
基数排序的基本原理是，对数字的每一位数进行一个归类，从地位开始到高位依次归类。
基数排序的实现思路：
- 遍历每一位元素的各分位数字
- 将这些元素根据最后一个数字统一归类。
- 循环直到每一位数遍历完毕。
JavaScript 代码实现：
// 基数排序
const radixSortData = [6, 25, 3, 92, 32, 8, 45, 113, 94, 7, 26, 9, 91, 34, 1002, 211, 115, 922];
const radixSort = (items, maxDigit) => {
let mod = 10;
let dev = 1;
let counter = [];
for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for (let j = 0; j < items.length; j++) {
let bucket = parseInt((items[j] % mod) / dev);
if (!counter[bucket]) {
counter[bucket] = [];
}
counter[bucket].push(items[j]);
}
let index = 0;
for (let j = 0; j < counter.length; j++) {
let value = null;
if (counter[j]) {
while ((value = counter[j].shift())) {
items[index++] = value;
}
}
}
}
return items;
}
const radix = radixSort(radixSortData, 4);
console.log(radix);输出结果：
[6, 25, 3, 92, 32, 8, 45, 113, 94, 7, 26, 9, 91, 34, 1002, 211, 115, 922]动图展示：
算法的时间和空间复杂度归纳如图：
排序算法的适用场景
大致已有排序情况
- 插入排序： 在大致已经有排序的情况下，可以减少数据交换和移动的次数，从而提高排序的效率。
- 冒泡排序：同上
数组元素 n 比较小的情况下
- 选择排序
数组元素 n 比较大的情况下
- 归并排序： 缺点是比较消耗空间，但是现在硬盘内存都已经足够大，基本可以忽略。
- 快速排序：快排在元素随机的情况下速度最快，但是如果实在大致有序的情况下速度又是最慢的
- 堆排序：缺点是不太好理解，需要先转堆结构再交换和移动。
基本不常用排序
- 希尔排序 ： 增量的初始值不好确定，这个不常使用。
- 桶排序
- 基数排序：适用于位数较小的元素。
排序的稳定性
排序的稳定性大多数情况下不需要考虑，只有在初始顺序存在意义且是复杂对象或者是数字的情况下，在二次排序是在原有的基础上进行，这个时候稳定性才有意义。
举例：一个商品进行从高到低的排序，这时候不仅要满足价格从高到低的排列也要满足销量从高到低的排列情况，这个时候稳定性就有意义。
