JS常用的排序算法有哪些，如何实现这些算法？
1.背景介绍
什么是算法
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解
决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
2.知识剖析
算法的特点
1.有限性（Finiteness）：一个算法必须保证执行有限步之后结束。
2.确切性（Definiteness）： 一个算法的每一步骤必须有确切的定义。
3.输入（Input）：一个算法有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身给定了初始条件。
4.输出（Output）：一个算法有一个或多个输出。没有输出的算法毫无意义。
5.可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。
3.常见问题
几种常见算法的写法及实现
4.解决方案
冒泡排序（Bubble Sort）
是重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
走访数列的工作是重复地进行直到没有再需要交换时，此时该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
思想：每一次对比相邻两个数据的大小，小的排在前面，如果前面的数据比后面的大就交换这两个数的位置
要实现上述规则需要用到两层for循环，外层从第一个数到倒数第二个数，内层从外层的后面一个数到最后一个数
特点：排序算法的基础。简单实用易于理解，缺点是比较次数多，效率较低。
具体算法描述如下：
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。
改进冒泡排序： 我们设置一个标志性变量pos，用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的元素均已交换到位，
故在进行下一趟排序时只要扫描到pos位置即可。 这样的优化方式可以在最好情况下把复杂度降到O(n)O(n)。
const bubbleSort2 = (arr) => {let i = arr.length - 1;
while(i > 0){let pos = 0;
for(let j = 0; j < i; j++){if (arr[j] > arr[j+1]){pos = j; //记录交换的位置
let tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
i = pos; //为下一趟排序作准备
}
return arr;
}
另外传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值，我们可以考虑利用在每趟排序中进行正向和反向两遍冒泡的方法来一次
得到两个最终值(最大者和最小者)，从而继续优化使排序趟数几乎减少一半。（这就是鸡尾酒排序）
const cooktailSort = (arr) => {let min = 0;
let max = arr.length - 1;
while(min < max){for(let j = min;j < max;j++){if(arr[j] > arr[j+1]){let tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
-- max;
for(let j = max;j > min;j--){if(arr[j] < arr[j-1]){let tmp = arr[j]
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
++ min;
}
return arr;
}
算法分析
冒泡排序对有n个元素的项目平均需要O(n^2)次比较次数，它可以原地排序，并且是能简单实现的几种排序算法之一，但是它对于少数元素之外
的数列排序是很没有效率的。
最佳情况：T(n) = O(n)
最差情况：T(n) = O(n^2)
平均情况：T(n) = O(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个记录RR交换，使R[1...i]和R[i+1...n]
分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n−1趟结束后，数组有序化。
const SelectionSort = (arr) => {let len = arr.length;
let minIndex, tmp;
console.time('选择排序耗时');for (let i = 0;i < len - 1; i++){minIndex = i;
for(let j = i + 1;j < len;j++){if(arr[minIndex] > arr[j]){minIndex = j;
}
}
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
console.timeEnd('选择排序耗时');return arr;}
算法分析
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，
它们当中至少有一个将被移到其最终位置上，因此对nn个元素的表进行排序总共进行至多n−1n−1次交换。在所有的完全依靠交换去移动元素的排
序方法中，选择排序属于非常好的一种。 但原地操作几乎是选择排序的唯一优点，当空间复杂度要求较高时，可以考虑选择排序；
实际适用的场合非常罕见。
最佳情况：T(n)=O(n2)T(n)=O(n2)
最差情况：T(n)=O(n2)T(n)=O(n2)
平均情况：T(n)=O(n2)
插入排序（Insertion Sort）
算法原理
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前s扫描，
找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)O(1)的额外空间的排序），因而在从后向前的扫描过程中，
需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间
算法描述与实践
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2 5
const insertionSort = (arr) => {let len = arr.length;
console.time('插入排序耗时');for (let i = 1;i < len; i++){let key = arr[i];
let j = i - 1;
while(j >= 0 && arr[j] > key){arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
console.timeEnd('插入排序耗时');return arr;
}
具体思路如下：
在插入第i个元素时，对前面的0 i−1元素进行折半。
与前面的0 i−1个元素中间的元素进行比较，如果小，则对前半再进行折半，否则对后半进行折半。
直到left > right，再把第ii个元素前1位和目标位置间的所有元素后移，把第ii个元素放在目标位置上。
快速排序
算法原理:通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述与实现具体算法描述如下：
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
从数列中挑出一个元素，称为“基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
'use strict'
const quickSort = (arr) => {if (arr.length <= 1) { return arr; }let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++){if (arr[i] < pivot) {left.push(arr[i]);
} else {right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
let arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.time('快速排序耗时');console.log(quickSort(arr));
console.timeEnd('快速排序耗时');
算法分析
最佳情况：T(n)=O(nlogn)T(n)=O(nlogn)
最差情况：T(n)=O(n2)T(n)=O(n2)
平均情况：T(n)=O(nlogn)
5.编码实战
6.扩展思考
1.排序的差异
2.算法优劣评价术语
1.排序的差异
快速排序是一种不稳定的排序算法，而归并排序是一种稳定的排序算法。由于不同引擎在算法选择上可能存在差异，导致前端如果依赖
Array.prototype.sort接口实现的JavaScript代码，在浏览器中实际执行的排序效果是不一致的。
而排序稳定性的差异其实也只是在特定的场景才会体现出问题；
2.算法优劣评价术语
稳定性:
稳定：如果a原本在b前面，而a = b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a = b，排序之后a可能会出现在b的后面；
排序方式:
内排序：所有排序操作都在内存中完成，占用常数内存，不占用额外内存。
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行，占用额外内存。
复杂度:
时间复杂度:一个算法执行所耗费的时间。
空间复杂度:运行完一个程序所需内存的大小。
排序算法图片总结
名词解释：n :数据规模k :桶的个数
从分类上来讲：
7.参考文献
参考一：JS的十大经典算法排序
参考二：js实现两种实用的排序算法——冒泡、快速排序
参考三：JavaScript排序算法汇总
