几种常见的排序方法（JS实现）

前言

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