关于javascript:几种常见的排序方法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
}