前言
就几种常见的排序算法用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}