排序算法

前端 931° Views

每个语言一般都有语言自带的排序方法，每个语言的排序内部实现都是不同的。对于 JS 来说，数组长度大于 10 会采用快排，否则使用插入排序。抛开语言自带的排序方法，这里总结了一些排序的算法。

冒泡排序

  1. 从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素，那么此时最后一个元素就是该数组中最大的数。
  2. 下一轮重复以上操作，每次只要比较到上一次的最大值位置。
function bubbleSort(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    // 从 0 到 `length - 1` 遍历
    for (let j = 0; j < i; j++) {
        if (arr[j] > arr[j + 1]){
            let temp = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = temp
        }
    }
  }
  return arr
}

二分法排序

  1. 获取中间元素，以中间元素把原数组切割成左右两个数组
  2. 余下元素和该元素对比，大于的放右边，小于的放左边
  3. 递归迭代

ps:这里的中间值可以是中间，也可以是随机的某个值（快排）。

function twoSort(arr){
    if(arr.length<=1){
        return arr;
    }
    var middle = arr.splice(Math.floor(arr.length/2),1)
    //var middle = arr.splice(parseInt(Math.random() * arr.length),1)   //随机取
    console.log(middle)
    var leftArr = []
    var rightArr = []
    for(var i=0; i<arr.length; i++){
       if(parseInt(arr[i])<=middle){
           leftArr.push(arr[i])      //把比中间值小的放一个数组
       }else{
           rightArr.push(arr[i])     //把比中间值大的放另一个数组
       }
    }
    return twoSort(leftArr).concat(middle,twoSort(rightArr))
}
var arr = [9,5,1,2,7,8,4,6,3];
var newArr = twoSort(arr);
console.log(newArr, 0)

插入法（前插）

  1. 依次找出比前一项小的所有值
  2. 让它们依次和之前已经排序好的数列进行比较，将小值与前一项互换位置
function insertSort(arr) {
    var len = arr.length
    for(var i=0; i<len; i++) {
        for(var j=i; j<len && arr[j+1]<arr[j]; j--) {
            var temp = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = temp
        }
    }
    return arr
}

选择排序

  1. 假定第一个数为最小值，让余下的第一个作比较，如果比第一个更小，交换位置
  2. 再假定第二个为最小值，依次迭代
function selectSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for(var i=0; i<len; i++) {
        //先给一个索引号，假设i为最小的数
        minIndex = i;
        //循环遍历，如果i之后有比索引i更小的数，则将索引变为j
        for(var j=i; j<len; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if(minIndex!=i){
             //将i索引的数和j索引的数互换
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    return arr;
}

本文固定连接：https://code.zuifengyun.com/2020/03/2227.html，转载须征得作者授权。

加载中...
加载中...