前言
就几种常见的排序算法用 js 语言实现：冒泡排序，抉择排序，插入排序，希尔排序，疾速排序，归并排序，桶排序。
尚未实现 ：
1. 剖析排序算法： 根本思维，稳定性，空间和工夫复杂度
2. 用图片、视频算法，深入浅出
在网上看到一个对于排序的图片
上面排序均依照由小到大排序
冒泡排序
思维：每趟之后的后果，最大值或者最小值到队尾
var bubbleSort = function(arr){for(let i=0; i<arr.length-1; i++){ // 趟数
for(let j=0; j<arr.length-1-i; j++){ // 还未排序的数量
if(arr[j+1]<arr[j]){[arr[j],arr[j+1]] = [arr[j+1],arr[j]]
}
}
}
return arr
}抉择排序
思维：每趟取得最小值。每趟之后的后果：右边为已排序，左边为未排序
留神以后的 curIndex 别忘赋值
var selectSort = function(arr){for(let i=0;i<arr.length-1; i++){ // 趟数
let min =arr[i]
let curIndex = i
for(let j = i; j<arr.length ; j++){if(arr[j]<min){min = arr[j]
curIndex = j
}
}
[arr[curIndex],arr[i]] = [arr[i],arr[curIndex]]
}
return arr
}插入排序
思维：右边为有序，左边组里每找到一个，倒序跟后面的进行比拟，把他插入到后面已排序的组中
var insertSort = function(arr){
var preIndex =0
for(var i=1; i<arr.length; i++){var temp = arr[i]
preIndex = i-1
while(preIndex>= 0 && temp< arr[preIndex] ) {// 这时候不能再用 arr[i], 应该用 temp
arr[preIndex+1] = arr[preIndex]
preIndex-=1
}
arr[preIndex+1] = temp
}
return arr;
}希尔排序
思维：是变形的插入排序，因为插入排序在根本有序的状况下工夫复杂度低
var shellSort = function(arr){
var len =arr.length, temp, gap =1;
while(gap< len/3){gap=gap*3 + 1} // 确定 gap，依据 arr 的长度
for(gap; gap>0; gap =Math.floor(gap/3)){
/**
* 能够替换掉上面这个 for 循环
* for(var i= gap; i<len; i++){* temp = arr[i]
* for(var preIndex = i-gap ;preIndex >=0 && arr[preIndex]> temp ; preIndex -=gap){* arr[preIndex + gap]= arr[preIndex]
* }
* arr[preIndex +gap]= temp
* }
*/
for(var i =gap; i<len; i++){temp = arr[i]
preIndex =i -gap
while(preIndex >=0 && arr[preIndex]> temp){arr[preIndex + gap]= arr[preIndex]
preIndex -= gap
}
arr[preIndex +gap]= temp
}
}
return arr
}快排
// 令人头疼，晓得思路，然而写起来的确有点麻烦
// 上面是递归算法
var quickSort = function (arr, left, right) {let target = arr[left]
let i =left ,j =right; //
if(left > right){ // 特地留神这点
return;
}
while(i !== j){while(arr[j]>= target && i<j){j--}
while(arr[i]<= target && i<j){i++}
if(i<j){[arr[i],arr[j]] = [arr[j],arr[i]]
}
}
arr[left] =arr[i]
arr[i]= target
// 这里的 left 和上面的 right
quickSort(arr,left,i-1)
quickSort(arr,i+1,right)
return arr
}归并排序
思维：先将数组拆分成几个小的组，而后合在一起
var merge = function(left, right) { // 合并两个有序数组
var result = [];
while(left.length && right.length){if(left[0] > right[0]){ // 每次选取 left 和 right 数组中最小的元素进入 result
result.push(right.shift()) // 做了两个操作 1. 删除 right 中最小的元素 2. 将最小的元素放入 result 中
} else{result.push(left,shift())
}
}
return result.concat(right,left) // 将 left 或者 right 中剩下的元素一起放入 result 中
}
var mergeSort = function(arr){
// 判断长度
if(arr.length<=1){return arr}
var mid = Math.floor(arr.length/2)
var left = arr.slice(0,mid)
var right = arr.slice(mid)
return merge(mergeSort(left),mergeSort(right))
}桶排序
思维：如有 10 个数字在 1 -100 以内，设置 10 个桶，每个桶所能包容的范畴别离为 1 -10，11-20，…… ,91-100。
将这 10 个数字放在相应的桶中，放入同一个桶时采纳插入排序，这样保障桶内也是有序的。整体桶也是有序，间接合并就行
var bucketSort1 = function (arr) {var min = arr[0]
var max = arr[0]
var len = arr.length;
var sum = len;
var size = 0
var index;
for (var i = 0; i < len; i++) {if (arr[i] > max) {max = arr[i]
} else if (arr[i] < min) {min = arr[i]
}
}
// 边界条件判断：min 是否等于 max，若等于，则无需排序
if (max != min) {var bucket = new Array(len)
for (var i = 0; i < sum; i++) { // 把数组中的数分到各个桶中
index = Math.floor((arr[i] - min) / (max - min) * (sum - 1))
bucket[index] = new Array() // 这句定义数组。不能省略
bucket[index].push(arr[i]) // 这个中央能够换位插入排序或者其余排序
}
for (var i = 0; i < sum; i++) {if (bucket[i].length > 1) {bucketSort1(bucket[i])
}
for (var j = 0; j < bucket[i].length; j++) {arr[size++] = bucket[i][j]
}
}
}
return arr
}