排序 | Colommar Blog

原稿：语雀 · 排序 · 原目录：算法 › 排序

所有的排序算法可以借用 leetcode912 排序数组进行测试

排序算法与复杂度参考Ch7 内排序

算法	稳定性	原地性	时间开销	空间开销
选择排序	否	是	Θ(n2)	Θ(1)
冒泡排序	是	是	Θ(n2)	Θ(1)
插入排序	是	是	Θ(n2)	Θ(1)
归并排序	是	否	Θ(nlogn)	Θ(n)
快速排序	否	是	Θ(nlogn)	Θ(logn)
堆排序	否	是	Θ(nlogn)	Θ(1)

- 稳定性：假定在待排序的记录序列中存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变则称这种排序算法是稳定的，否则称为不稳定的 - 原地性：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序

冒泡排序

let arr = [1, 7, 2, 3, 4, 4, 16, 7, 3, 0, 18, 29];

// 升序冒泡排序
function bubbleSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
}

bubbleSort(arr)
console.log(arr);
// (12) [0, 1, 2, 3, 3, 4, 4, 7, 7, 16, 18, 29]

优化：针对已有序数组

上述代码对于已经有序的数组依旧会比较O(n2)次，实际上内层只要不发生一次交换就足以说明当前数组本身有序

// 升序冒泡排序
function bubbleSort(arr) {
  let len = arr.length;
  let isSorted = true;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
        isSorted = false;
      }
    }
    if (isSorted) break;
  }
  return arr;
}

插入排序

// 升序插入排序
function insertSort(arr) {
  for (let i = 1, len = arr.length; i < len; i++) {
    for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
      let temp = arr[j - 1];
      arr[j - 1] = arr[j];
      arr[j] = temp;
    }
  }
}

insertSort(arr);
console.log(arr);
// (12) [0, 1, 2, 3, 3, 4, 4, 7, 7, 16, 18, 29]

选择排序

// 升序选择排序
function selectSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let min = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[min]) min = j;
    }
    if (min !== i) {
      let temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  }
}

selectSort(arr);
console.log(arr);

堆排序

参考链接：JS实现堆排序堆排序的时间复杂度分析

升序堆排序 2. 先构造大顶堆 4. 每次交换堆顶（当前最大元素）和无序区最后一个元素，有序区元素加一，无序区元素减一。堆顶重新下沉到合适位置。不断重复，直到无序区只有最后一个元素

复杂度

建堆：siftdown()的复杂度取决于以a $i$ 为root的子树高度，为O(logn)。这里从倒数第二层开始建堆（循环次数数n//2），开始树高为1，不断向上，log1+log2+log3+ … => O(n)
排序重建堆过程：n-1次循环，每次执行siftdown，但结点数也减一，近似为O(nlogn)
总时间复杂度为O(nlogn)

function swap(arr, i, j) {  let temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;}function siftdown(arr, i, length) {  for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {    let parent = arr[i];    // 选择子节点较大者    if (j + 1 < length && arr[j] < arr[j + 1]) j++;    if (parent < arr[j]) {      swap(arr, i, j);      i = j;    } else break;  }}function heapSort(arr) {  for (let i = (arr.length >> 1) - 1; i >= 0; i--) {    siftdown(arr, i, arr.length);  }  for (let i = arr.length - 1; i > 0; i--) {    swap(arr, i, 0);    // 交换完后arr[i]处元素已进入有序区，则length可减一    siftdown(arr, 0, i);  }  return arr;}

快速排序

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function quickSort(arr, l, r) {
  if(l>=r) return;

  let pivot = ((r - l) >> 1) + l;
  // pivot暂时移动至末尾
  swap(arr, pivot, r);
  // 找到合适的pivot索引
  pivot = partition(arr, l - 1, r, arr[r]);
  swap(arr, pivot, r);

  quickSort(arr, l, pivot - 1);
  quickSort(arr, pivot + 1, r);
}

function partition(arr, l, r, pivot) {
  while (l < r) {
    // pivot作为最后元素，l不会增长过len-1
    while (arr[++l] < pivot);
    while (r>0 && arr[--r] > pivot);
    swap(arr, l, r);
  }
  // 丢弃最后一次交换
  swap(arr, l, r);
  return l;
}

let arr = [1, 7, 2, 3, 4, 4, 16, 7, 3, 0, 18, 29];
quickSort(arr, 0, arr.length - 1);
console.log(arr);

优化：三项切分

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const quickSort = function(nums, l, r){
        if(l>=r) return;
        let [curr, gt, lt] = [l+1, r, l];
        let pivot = nums[l];
        while(curr <= gt){
            if(nums[curr]<pivot) swap(nums, lt++, curr++);
            else if(nums[curr]>pivot) swap(nums, curr, gt--);
            else curr++;
        }

        quickSort(nums, l, lt-1);
        quickSort(nums, gt+1, r);
    }

    quickSort(nums, 0, nums.length-1);
    return nums;
};

归并排序

function mergeSort(arr, tempArr, l, r) {
  // 考虑arr为空数组时
  if (l >= r) return;

  let mid = ((r - l) >> 1) + l;
  mergeSort(arr, tempArr, l, mid);
  mergeSort(arr, tempArr, mid + 1, r);

  for (let i = l; i <= r; i++) {
    tempArr[i] = arr[i];
  }

  for (let curr = l, i1 = l, i2 = mid + 1; curr <= r; curr++) {
    if (i1 == mid + 1) arr[curr] = tempArr[i2++];
    else if (i2 > r) arr[curr] = tempArr[i1++];
    else if (tempArr[i2] < tempArr[i1]) arr[curr] = tempArr[i2++];
    else arr[curr] = tempArr[i1++];
  }
}

let arr = [1, 7, 2, 3, 4, 4, 16, 7, 3, 0, 18, 29];
let tempArr = [];
mergeSort(arr, tempArr, 0, arr.length - 1);
console.log(arr);

优化：针对小序列

原始算法中最小的归并发生在两个元素上，【2】【1】=》【1，2】，期间同样进行了拷贝比较。考虑对较小的子序列设置Threshold，当子序列长度小于Threshold时使用插入排序，可节省在小序列排序中的开销

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    const insertSort = function(arr, l, r){
        // 注意是 i<=r
        for(let i=l+1; i<=r; i++){
            for(let j=i-1; j>=l && arr[j]>arr[j+1];j--){
                swap(arr, j, j+1);
            }
        }
    }
    const mergeSort = function(temp, arr, l, r){
        if(r-l<=4){
            insertSort(arr, l, r);
            return;
        }
        let mid = ((r-l)>>1)+l;
        mergeSort(temp, arr, l, mid);
        mergeSort(temp, arr, mid+1, r);

        for(let i=l; i<=r; i++){
            temp[i] = arr[i];
        }

        for(let curr=l, i1=l, i2=mid+1; curr<=r; curr++){
            if(i1 == mid+1 || temp[i2]<temp[i1]) arr[curr]=temp[i2++];
            else if(i2 == r+1 || temp[i1]<= temp[i2]) arr[curr]=temp[i1++];
        }
    }

    mergeSort([], nums, 0, nums.length-1);
    return nums;
};

冒泡排序#

优化：针对已有序数组#

插入排序#

选择排序#

堆排序#

快速排序#

优化：三项切分#

归并排序#

优化：针对小序列#