javascript十大经典排序算法
稳定：如果a原本在b前面，而且a=b，排序之后a仍然在b前面。
不稳定：如果a原本在b前面，而且a=b，排序之后a可能会出现在b后面。
排序.png
一、冒泡排序
中心思想：重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
算法描述：
1、比较相邻的元素，如果第一个比第二个大，就交换它们
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样在最后对元素就是最大的数
3、针对所有的元素，重复以上的步骤(除了最后一个)
4、重复步骤1～3，直到排序完成
冒泡排序.gif
具体实现方法一：
function bubbleSort(arr){
var len = arr.length;
for(var i=0;i<len;i++){
for(var j=0;j<len;j++){
if(arr[j]>arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
具体实现方法二：每次排序后，记录下最后一次交换的位置，因为在这之后的数字已经排好序了，因此不需要再次进行比较。
function bubbleSort2(arr){
var i = arr.length-1;
while(i>0){
var pos = 0;
for(var j=0;j<i;j++){
if(arr[j]>arr[j+1]){
pos = j;
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
i = pos;
}
return arr;
}
具体实现方法三：利用在每趟排序中进行正向和反向两遍冒泡的方法，一次可以得到两个最值(最大值和最小值)，从而使排序趟数几乎减少一半。
function bubbleSort3(arr){
var low = 0, high = arr.length-1;
while(low<high){
var j = low;
for(j;j<high;j++){ // 正向冒泡找到最大值
if(arr[j]>arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
--high;
for(j=high;j>low;j--){// 反向冒泡找到最小值
if(arr[j]<arr[j-1]){
var temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
++low;
}
return arr;
}
具体实现方法四：方法二和方法三的结合，设置一个最大值标志maxPos和最小值标志minPos，每次只将两个标志之间的进行排序比较。
function bubbleSort4(arr){
var minPos = 0, maxPos = arr.length-1;
while(minPos<maxPos){
var j = minPos, tempMin, tempMax;
for(j;j<maxPos;j++){
if(arr[j]>arr[j+1]){
tempMax = j;
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
maxPos = tempMax;
for(j=maxPos;j>minPos;j--){
if(arr[j]<arr[j-1]){
tempMin = j;
var temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
minPos = tempMin;
}
return arr;
}
方法6：
function BubbleSort(arr){
let l = arr.length;
for(let i = l - 1;i >= 0;i--){
for(let j = 0;j < i ;j++){
if(arr[j] > arr[j+1]){
[arr[j],arr[j+1]] = [arr[j+1],arr[j]];
}
}
}
return arr;
}
方法7：方法1的升级版
解析
两个循环
当i=0的时候，里面的循环完整执行，从j=0执行到j=6,这也就是第一遍排序，结果是将最大的数排到了最后，这一遍循环结束后的结果应该是[8,15,88,55,76,21,39,94]
当i=1的时候，里面的循环再次完整执行，由于最大的数已经在最后了，没有必要去比较数组的最后两项，这也是j<arr.length-1-i的巧妙之处，结果是[8,15,55,76,21,39,88,94]
说到这里，规律就清楚了，每次将剩下数组里面最大的一个数排到最后面，当第一个循环执行到最后的时候，也就是i=6,此时，j=0,只需要比较数组的第一和第二项，比较完毕，返回。
let examplearr=[6,5,3,1,8,7,2,4];
function sortarr(arr){
for(let i=0;i<arr.length-1;i++){
console.log(i)
for(let j=0;j<arr.length-1-i;j++){
console.log(j)
if(arr[j]>arr[j+1]){
let temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr;
}
sortarr(examplearr);
console.log(examplearr);
二、选择排序
中心思想：首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小(大)元素，放到已排序队列的末尾。以次类推，直到所有元素均排序完毕。
算法描述：
1、初始状态：无序区为R[1…n]，有序区为空
2、第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个的新无序区
3、n-1趟结束，数组有序化
具体实现方法：
function selectionSort(arr){
var len = arr.length;
var minIndex, temp;
for(var i=0;i<len-1;i++){
minIndex = i;
for(var j=i+1;j<len;j++){
if(arr[j]<arr[minIndex]){
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
//或者：
function SelectSort(arr){
let l = arr.length;
for(let i = 0;i < l-1;i++){
let min = i;
for(let j = min + 1;j < l;j++){
if(arr[min] > arr[j]){
min = j;
}
}
let temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
return arr;
}
三、插入排序
中心思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述：
1、从第一个元素开始，该元素可以认为已经被排序
2、取出下一个元素，在已经排序的元素队列中从后向前扫描
3、如果该元素(已排序)大于新元素，将该元素移到下一位置
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5、将新元素插入到该位置后
重复步骤2～5
插入排序.gif
具体实现方法一：
function insertionSort(arr){
for(var j=1;j<arr.length;j++){
var temp = arr[j];
var i = j-1;
while(arr[i]>temp && i>=0){
arr[i+1] = arr[i--];
}
arr[i+1] = temp;
}
return arr;
}
具体实现方法二：二分法插入排序，从第一个元素开始，该元素可以认为已经被排序，取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置，将新元素插入到该位置后。
function binaryInsertionSort(arr){
for(var i=1;i<arr.length;i++){
var left = 0, right = i-1;
var temp = arr[i];
while(left<=right){
var middle = parseInt((left+right)/2);
if(temp>arr[middle]){
left = middle+1;
}else {
right = middle-1;
}
}
for(var j=i;j>=left;j--){
arr[j] = arr[j-1];
}
arr[left] = temp;
}
return arr;
}
四、希尔排序
中心思想：希尔排序是简单插入排序的改进版，在简单插入排序中，比较间隔是1，而希尔排序可以动态的定义间隔序列。先将整个待排序的记录序列分割成为若干个子序列分别进行直接插入排序。
算法描述：
1、选择一个增量序列t1,t2,…,tk，其中ti>tk，tk=1
2、按增量序列个数，对序列进行k趟排序
3、每趟排序，根据对应对增量ti，将待排序列分割成若干长度为m的子序列，分别对各字表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度
具体实现方法：
function shellSort(arr){
var gap = arr.length;
while(gap>1){
gap = parseInt(gap/2);
for(var j=gap;j<arr.length;j++){
var temp = arr[j];
var i = j-gap;
while(arr[i]>temp && i>=0){
arr[i+gap] = arr[i];
i = i-gap;
}
arr[i+gap] = temp;
}
}
return arr;
}
或者：
function ShellSort(arr){
let l = arr.length;
// 初始增量
let gap = Math.floor(l / 2);
while(gap >= 1){
// 对每个分组使用插入排序，类似插入排序从分组的第二个数开始
for(let i = gap;i < l;i++){
let temp = arr[i];
let j = i;
while(arr[j-gap] > arr[j] && j > gap-1){
arr[j] = arr[j-gap];
j -= gap;
}
arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
举个例子，加强理解：
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,1];
第一次，增量为7，则分割为：
1-->[3, 26, 1]
2-->[44, 27]
3-->[38, 2]
4-->[5, 46]
5-->[47, 4]
6-->[15, 19]
7-->[36, 50]
进行排序后结果为：
[1, 27, 2, 5, 4, 15, 36, 3, 44, 38, 46, 47, 19, 50, 26]
第二次，增量为3，则分割为：
1-->[1,5, 36, 38, 19]
2-->[27, 4, 3, 46, 50]
3-->[2, 15, 44, 47, 26]
进行排序后结果为：
[1, 3, 2, 5, 4, 15, 19, 27, 26, 36, 46, 44, 38, 50, 47]
第三次，增量为1，进行排序后为：
[1, 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50]
五、归并排序
中心思想：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法描述：
1、把长度为n的输入序列分成两个长度为n/2的子序列
2、对这两个子序列分别采用归并排序
3、将两个排序好的子序列合并成一个最终的排序序列
归并排序.gif
具体实现方法：
function mergeSort(arr){
var len = arr.length;
if(len<2){
return arr;
}
var middle = parseInt(len/2);
var left = arr.slice(0, middle), right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right){
var result = [];
while(left.length && right.length){
if(left[0]<right[0]){
result.push(left.shift());
}else {
result.push(right.shift());
}
}
if(left.length==0){
result = result.concat(right);
}else if(right.length==0){
result = result.concat(left);
}
return result;
}
六、快速排序
中心思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述：
1、从数列中挑出一个元素，称为‘基准’
2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以放到任何一边)。在这个分区退出后，该基准就处于数列的中间位置，这个称为分区操作
3、递归地把小于基准值元素的子数列和大于基准值元素的子数列排序
具体实现方法：
function quickSort(arr){
var len = arr.length;
if(len<=2){
return arr;
}
var middle = parseInt(len/2);
var base = arr[middle];
var left = [], right = [];
var i = 0;
while(i<len){
if(arr[i]<base){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
i = i+1;
}
right.unshift(base);
return quickSort(left).concat(quickSort(right));
}
或者：
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = []; var right = [];
for (var 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));
};
七、堆排序
中心思想：利用堆这种数据结构设计的一种算法，即子节点的键值或索引总是小于(或大于)它的父节点。
算法描述：
1、将初始待排序关键字序列(R1,R2,…,Rn)构建成大顶堆，此堆为初始堆无序区
2、将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新堆无序区(R1,R2,…,Rn-1)和新堆有序区(Rn)，且满足R[1,2,…,n-1]<R[n]
3、由于交换后新堆堆顶R[1]可能违反堆的性质，因此需要堆当前无序区(R1,R2,…,Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2,…,Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程，直到有序区的元素个数为n-1，则整个排序过程完成
具体实现方法：
function heapSort(arr){
var len = arr.length;
for(var i=len;i>1;i--){
buildHeap(arr, i);
var temp = arr[0];
arr[0] = arr[i-1];
arr[i-1] = temp;
}
return arr;
}
function buildHeap(arr, end){
for(var i=end-1;i>0;i--){
if(arr[i]>arr[i-1]){
var temp = arr[i];
arr[i] = arr[i-1];
arr[i-1] = temp;
}
}
}
八、计数排序
中心思想：使用一个额外的数组C，其中第i各元素是待排序数组A中值等于i的元素的个数，然后根据数组C来将A中的元素排到正确的位置，它只能对整数进行排序。
算法描述：
1、找出待排序对数组中最大和最小对元素
2、统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3、对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加)
4、反向填充目标数组：将每个元素i放在新数组的第C(i)项，没放一个元素就将C(i)减去i
具体实现方法：
function countingSort(arr){
var len = arr.length;
var min = max = arr[0], result = [];
for(var i=1;i<len;i++){
max = arr[i]>max ? arr[i] : max;
min = arr[i]<min ? arr[i] : min;
}
var newArr = new Array(max+1);
newArr.fill(0);
for(var i=0;i<len;i++){
newArr[arr[i]] = ++newArr[[arr[i]]];
}
for(var i=min-1;i<max+1;i++){
if(newArr[i]!=0){
while(newArr[i]){
result.push(i);
--newArr[i];
}
}
}
return result;
}
九、桶排序
中心思想：计数排序的升级版。假设输入数据服从均匀分布，则数据分到有限数量到桶里，每个桶再分别排序(有可能再使用别的排序或是以递归方法继续使用桶排序进行排序)
算法描述：
1、设置一个定量的数组，当作空桶
2、遍历输入数据，并且把数据一个一个放到对应的桶里去
3、对每个不是空对桶进行排序
4、从不是空的桶里把排好序的数据拼接起来
具体实现方法一：
function bucketSort(arr, num=5){
var len = arr.length;
if(len<2 || singleArray(arr)){
return arr;
}
var min = max = arr[0], result = [];
var temp = new Array(num);
for(var i=0;i<num;i++){
temp[i] = [];
}
for(var i=0;i<len;i++){
max = arr[i]>max ? arr[i] : max;
min = arr[i]<min ? arr[i] : min;
}
var gap = (max-min+1)/num;
for(var i=0;i<len;i++){
var index = parseInt((arr[i]-min)/gap);
temp[index].push(arr[i]);
}
temp = temp.filter(function(item){ return item.length; });
var tempLen = temp.length;
for(var i=0;i<tempLen;i++){
temp[i] = bucketSort(temp[i]);
result = result.concat(temp[i]);
}
return result;
}
function singleArray(arr){ // 判断数组各项是否相同
var len = arr.length;
for(var i=1;i<len;i++){
if(arr[i]!=arr[0]){
return false;
}
}
return true;
}
举个例子，加强理解：
var arr = [98,89, 89,1,2,3];
(1)设置桶的数量为5，找到最大值98，最小值1，每个桶的范围(98-1+1)/5=19.6
(2)遍历原始数据，以连标结构放到对应的桶中，数组98，索引值为4(=parseInt(98-1)/19.6)，数字89索引值为4(=parseInt(89-1)/19.6)，数字1，2，3的索引都为0
桶0–>[1,2,3]
桶1–>[]
桶2–>[]
桶3–>[]
桶4–>[98,89,89]
(3)过滤掉为空的桶
(4)递归地利用桶排序(或者其他排序方法)对各个桶中的数组进行排序，如果数组长度为1，或者数组中各项相同（至关重要），则直接返回数组
(5)将各桶合并
十、基数排序
中心思想：按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
算法描述：
注：基数排序使用与数据范围较小时(建议小于1000)且每个数值都要大于等于0
1、取得数组中的最大值，并取得位数
2、arr为原始数组，从最低位开始取每个位组成radix数组
3、对radix进行计数排序(利用计数排序适用于小范围的特点)
动图演示：
[图片上传失败...(image-4bee64-1576578876150)]
具体实现方法：
function radixSort(arr){
var len = arr.length;
var max = arr[0], dev = 1, mod = 10;
for(var i=1;i<len;i++){
max = arr[i]>max ? arr[i] : max;
}
var radix = max.toString().length;
for(var j=1;j<=radix;j++){
var result = [];
var temp = new Array(10);
for(var i=0;i<10;i++){
temp[i] = [];
}
for(var i=0;i<len;i++){
var pos = parseInt(arr[i]%mod/dev);
temp[pos].push(arr[i]);
}
dev *= 10;
mod *= 10;
for(var i=0;i<10;i++){
result = result.concat(temp[i]);
}
arr = result;
}
return arr;
}
