探索sort是怎么排序的

数组排序方法研究sort

Google Chrome 对 sort 做了特殊处理，对于长度 <= 10 的数组使用的是插入排序(稳定排序算法)

，>10 的数组使用的是快速排序。快速排序是不稳定的排序算法。

插入排序算法（稳定排序算法）

1、插入排序js代码实现

function insertionSort(array) {
    var swop = function (arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    };

    var len = array.length,
        i,
        j;
    for (i = 1; i < len; i++) {
        for (j = i; j > 0; j--) {
            if (array[j - 1] > array[j]) {
                swop(array, j - 1, j);
            } else {
                break;
            }
        }
    }
    return array;
}

2、基于1优化的sort排序方法 对比与上一种减少了交换次数

function insertionSOrt(array) {
    var len = array.length,
        i,
        j,
        temp;
    for (i = 1; i < len; i++) {
        temp = array[i];
        for (j = i; j > 0; j--) {
            if (array[j - 1] > temp) {
                array[j] = array[j - 1];
            } else {
                arr[j] = temp;
                break;
            }
        }
    }
    return array;
}

3.二分查找排序

function insertionSort2(array) {
  function binarySearch(array, start, end, temp) {
    var middle;
    while (start <= end) {
      middle = Math.floor((start + end) / 2);
      if (array[middle] < temp) {
        if (temp <= array[middle + 1]) {
          return middle + 1;
        } else {
          start = middle + 1;
        }
      } else {
        if (end === 0) {
          return 0;
        } else {
          end = middle;
        }
      }
    }
  }
  function binarySort(array) {
    var length = array.length,
        i,
        j,
        k,
        temp;
    for (i = 1; i < length; i++) {
      temp = array[i];
      if (array[i - 1] <= temp) {
        k = i;
      } else {
        k = binarySearch(array, 0, i - 1, temp);
        for (j = i; j > k; j--) {
          array[j] = array[j - 1];
        }
      }
      array[k] = temp;
    }
    return array;
  }
  return binarySort(array);
}

原文

快速排序（不稳定排序算法）

/*
 * 1、找准基准点
 * 2、把所有比基准点小的数放左边大的数放右边
 * 3、递归调用自己
 *
 * */
 function quickSort(arr){
     var len = arr.length;
     if(len <= 1) {
         return arr;
     }
     var leftArr=[],rightArr=[];
     var pivot = Math.floor(len/2);
     for(var i=0;i<len;i++){
         if(arr[i]<arr[pivot]){
             leftArr.push(arr[i]);
         } else if(arr[i]>arr[pivot]){
             rightArr.push(arr[i]);
         }
     }
     return quickSort(leftArr).concat(arr[pivot],quickSort(rightArr));
 }
 var aa = quickSort([22,3,42,12,123,123,211,23221,22,2,12]);
 console.log(aa);//[2, 3, 12, 22, 42, 123, 211, 23221]去重排序

快速排序参考

4.冒泡排序法

/*
* 冒泡排序法
* 两两比较把最大的沉到最低
* n*(n-1)/2
* */
 function bubbleSort(arr){
    let len = arr.length;
    for(let i = 0; i < len;i++){
        for(let j = 0 ;j<len-1-i;j++) {
            if(arr[j]>arr[j+1]) {
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]];
            }
        }
    }
    return arr;
 }

4.1冒泡排序法优化

/*
* <=n*(n-1)/2
* 看要排序的数组的空间复杂度
* */
function bubbleSort(arr) {
    let i = arr.length,pos;
    while(i>0) {
        pos = 0;
        for(let j = 0;j<i;j++) {
            if(arr[j]>arr[j+1]) {
                pos = j;
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]];
            }
        }
        i = pos;
    }
    return arr;
}

5.选择排序法

/*
* 选择排序法
* 选择最小的数放到数组最前面
* n*(n-1)/2
* */

function selectionSort(arr){
    let minIndex,
        len = arr.length;
    for(let i = 0;i<len;i++){
        minIndex = i;
        for(let j = i+1;j<len;j++){
            if(arr[j]<arr[minIndex]){
                minIndex = j;
            }
        }
        [arr[i],arr[minIndex]] = [arr[minIndex],arr[i]];
    }
    return arr;
}

赏

谢谢你请我喝咖啡

支付宝

微信