已經有很多排序演算法的文章了，這里主要是做一個自己的總結，
內容大部分整合自《演算法第四版》，圖示大部分來自菜鳥教程網，語言選擇的當然是JavaScript啦~
代碼可以直接在LeetCode的912.排序陣列題目上運行

在此之前先定義一個交換陣列中兩個元素的函式

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

1. 冒泡排序 （簡單）

流程

• 比較相鄰的元素，如果前者大于后者就交換
• 對每一對相鄰元素作同樣的作業，從開始第一對到結尾的最后一對，這步做完后，最后的元素會是最大的數
• 針對所有的元素重復以上的步驟，除了最后一個
• 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較

圖示

代碼

參考代碼1

/**
 * @param {number[]} nums
 * @return {number[]}
 */
 var sortArray = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length - i -1; j++) {
      if (nums[j] > nums[j + 1]) {
        swap(nums, j, j + 1);
      }
    }
  }
  return nums;
};

參考代碼2 優化冒泡排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
 var sortArray = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    let flag = true;
    for (let j = 0; j < nums.length - i -1; j++) {
      if (nums[j] > nums[j + 1]) {
		swap(nums, j, j + 1);
        flag = false;
      }
    }
    if(flag) {
      return;
    }
  }
  return nums;
};

復雜度分析

時間復雜度： O ( N 2 ) O(N^2) O(N2)，這里 N N N是陣列的長度；
空間復雜度： O ( 1 ) O(1) O(1)，使用到常數個臨時變數，

2. 選擇排序（簡單）

一種最簡單的排序演算法：首先找到陣列中最小的元素，將它和陣列中的第一個元素交換位置，然后在剩下的元素中找到最小的，與第二個元素交換位置，直到整個陣列排序，（不斷選擇剩余陣列中最小的元素）

流程

1. 首先在未排序序列中找到最小元素，存放到排序序列的起始位置
2. 再從剩余未排序元素中繼續尋找最小元素，然后放到已排序序列的末尾
3. 重復第二步，直到所有元素均排序完畢

圖示

代碼

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    let min = i;
    // 已排序區間 [0, i) ，未排序區間 [i+1 , len)
    // 遍歷 i+1 之后的元素找到最小元素的索引
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[min]) {
        min = j;
      }
    }
    swap(nums, i, min);
  }
  return nums;
};

復雜度分析

• 對于長度為N的陣列，選擇排序需要大約 N 2 / 2 N^2/2 N2/2次比較和 N N N次交換，
• 有兩個特點：①運行時間和輸入無關 ②資料移動是最少的，交換次數和陣列的大小是線性關系

時間復雜度： O ( N 2 ) O(N^2) O(N2)，這里 N N N 是陣列的長度；
空間復雜度： O ( 1 ) O(1) O(1)，使用到常數個臨時變數，

3. 插入排序（重點）

流程

每次將一個數字插入一個有序的陣列里，成為一個長度更長的有序陣列，有限次操作以后，陣列整體有序

圖示

代碼

參考代碼1（交換元素）（演算法第四版的思路）

/**
 * 插入排序
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  // 從下標為1的元素開始選擇合適的位置插入，因為下標為0的只有一個元素，默認是有序的
  // 已排序區間 [0, i) ，未排序區間 [i , len)

  // 將 nums[i] 插入到區間 [0, i) 使之成為有序陣列
  for (let i = 1; i < nums.length; i++) {
    // 從右往左遍歷
    for (let j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
      // 只要nums[j]比前一個元素nums[j-1]小，就交換這兩個元素
      swap(nums, j, j - 1);
    }
  }
  return nums;
};

參考代碼2（移動元素）

/**
 * 插入排序
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  for (let i = 1; i < nums.length; i++) {
    // 已排序區間 [0, i) ，未排序區間 [i , len)
    // 將 nums[i] 插入到區間 [0, i) 使之成為有序陣列

    // 先暫存這個元素，然后之前元素逐個后移，留出空位
    let temp = nums[i];
	let j = i;
    while(j > 0 && temp < nums[j - 1]) {
      // 只要nums[j]比前一個元素nums[j-1]小，將nums[j-1]移動到nums[j]
      nums[j] = nums[j - 1];
      j--;
    }
    
    // 找到位置j，將i的值放在j上
    nums[j] = temp;
  }
  return nums;
};

復雜度分析

插入排序對部分有序的陣列和“短陣列”很有效

時間復雜度： O ( N 2 ) O(N^2) O(N2)，這里 N N N 是陣列的長度；
空間復雜度： O ( 1 ) O(1) O(1)，使用到常數個臨時變數，

4. 希爾排序（了解）

對插入排序的改進！插入排序效率低的原因是它只會交換相鄰的元素
希爾排序的思想是使陣列中任意間隔為h的元素都是有序的，即帶間隔地使用插入排序

流程

設定增量序列是一個超引數，需要經驗，下面的代碼給出了兩種定義方式

圖示

代碼

設定增量序列是一個超引數，需要經驗，下面的代碼給出了兩種定義方式

參考代碼1（交換元素）

var shellSortArray = function (nums) {
  const N = nums.length;
  // 使用 Knuth 增量序列
  let h = 1;
  while (h < N / 3) {
    h = 3 * h + 1; // 動態定義間隔序列
  }

  while (h >= 1) {
    for (let i = h; i < N; i++) {
      for (let j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
        swap(nums, j, j - h);
      }
    }
    h = Math.floor(h / 3)
  }
};

參考代碼2（移動元素）

var shellSortArray2 = function (nums) {
  const N = nums.length;
  for (let gap = N / 2; gap > 0; gap = Math.floor(gap/2)) {
    for (let i = gap; i < N; i++) {
      let temp = nums[i];
      let j = i;
      while(j >= gap && nums[j - gap] > temp){
        nums[j] = nums[j - gap];
        j -= gap;
      }
      nums[j] = temp;
    }
  }
  return nums;
};

復雜度分析

在輸入隨機排序陣列的情況下，我們在數學上還不知道希爾排序所需要的平均比較次數

5. 歸并排序（重點）

將兩個有序的陣列歸并成一個更大的有序陣列

流程

分治演算法、遞回呼叫

1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；

2. 設定兩個指標，最初位置分別為兩個已經排序序列的起始位置；

3. 比較兩個指標所指向的元素，選擇相對小的元素放入到合并空間，并移動指標到下一位置；

4. 重復步驟 3 直到某一指標達到序列尾；

5. 將另一序列剩下的所有元素直接復制到合并序列尾，

圖示

代碼

使用JavaScript中陣列的佇列方法，使得歸并排序實作起來例外簡單，不用涉及過多的指標問題

/**
 * 歸并排序演算法
 * @param {*} arr 陣列
 * @returns 有序陣列
 */
function mergeSort(arr) {
  // 采用自頂向下的遞回方法
  const N = arr.length;
  if (N < 2) {
    // 遞回出口，陣列只有一個元素，直接回傳這個陣列
    return arr;
  }
  // x >> 1 是位運算中的右移運算，表示右移一位，等同于 x 除以 2 再取整，即 x >> 1 === Math.floor(x / 2)
  // N >> 1 和 Math.floor(N / 2) 等價
  let middle = N >> 1;
  // 拆分為兩個子陣列
  let left = arr.slice(0, middle);
  let right = arr.slice(middle);
  // 遞回呼叫mergeSort
  return merge(mergeSort(left), mergeSort(right));
}


/**
 * 對兩個有序陣列進行合并操作
 * @param {*} left left陣列
 * @param {*} right right陣列
 * @returns 一個有序陣列temp
 */
function merge(left, right) {
  // 臨時陣列存盤歸并后的資料
  const temp = [];
  // 兩個陣列都還沒有遍歷結束
  while (left.length && right.length) {
    // 注意: 判斷的條件是小于或等于，如果只是小于，那么排序將不穩定.
    if (left[0] <= right[0]) {
      // left[0]小，洗掉left陣列中第一項left[0]，并將它放入temp陣列中
      temp.push(left.shift());
    } else {
      // 洗掉right陣列中第一項，并將它放入temp陣列中
      temp.push(right.shift());
    }
  }
  // left陣列還有元素，right陣列遍歷完了
  while (left.length) {
    // 將left陣列剩下的元素都放入temp陣列中
    temp.push(left.shift());
  }
  // right陣列還有元素，left陣列遍歷完了
  while (right.length) {
    temp.push(right.shift());
  }
  // 回傳排序好的陣列
  return temp;
}

我們不使用JavaScript中Array自帶的一些方法，使用指標的方式按照《演算法（第四版）》重寫一遍

/**
 * 排序陣列
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  const N = nums.length;
  let temp = new Array();
  mergeSort(nums, 0, N - 1, temp);
  return nums;
};

/**
 * 歸并排序  采用自頂向下的遞回方法
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @param {number[]} temp
 * @returns
 */
var mergeSort = function (nums, left, right, temp) {
  // 如果指標重疊了就回傳
  if (left >= right) {
    return;
  }

  // let mid = Math.floor(left + (right - left) / 2);
  let mid = (left + right) >> 1;
  // 遞回呼叫mergeSort
  mergeSort(nums, left, mid, temp);
  mergeSort(nums, mid + 1, right, temp);
  // 歸并兩個有序陣列
  merge(nums, left, mid, right, temp);
};

/**
 * 歸并兩個有序陣列
 * @param {number[]} nums
 * @param {number} left
 * @param {number} mid
 * @param {number} right
 * @param {number[]} temp
 */
var merge = function (nums, left, mid, right, temp) {
  // 將nums復制到temp中去
  for (let k = left; k <= right; k++) {
    temp[k] = nums[k];
  }

  // 給兩個陣列分別定義一個指標
  let i = left;
  let j = mid + 1;

  // 將temp中的元素按規則寫回nums
  for (let k = left; k <= right; k++) {
    if (i > mid) {
      // 左半邊取盡，取右半邊元素
      nums[k] = temp[j];
      j++;
    } else if (j > right) {
      // 右半邊取盡，取左半邊元素，左指標右移
      nums[k] = temp[i];
      i++;
    } else if (temp[i] <= temp[j]) {
      // 誰小就取誰 ，左邊小
      nums[k] = temp[i];
      i++;
    } else {
      // 右邊小
      nums[k] = temp[j];
      j++;
    }
  }
};

復雜度分析

時間復雜度： O ( N log ? N ) O(N \log N) O(NlogN)，這里 N N N 是陣列的長度；
空間復雜度： O ( N ) O(N) O(N)，輔助陣列與輸入陣列規模相當，

優化

設定短陣列長度閾值，使歸并到短陣列的時候用插入排序法

上面介紹的是一種自頂向下的遞回方法，另外還有自底向上的遞回方法，在這里就不做過多介紹，具體可以參考演算法第四版的內容

6. 快速排序（重點）

流程

1. 從陣列中選擇一個值作為主元（pivot），也就是陣列中間的那個值，
2. 創建兩個指標（參考），左邊一個指向陣列第一個值，右邊一個指向陣列最后一個值，移動左指標直到我們找到一個比主元大的值，接著，移動右指標直到找到一個比主元小的值，然后交換它們，重復這個程序，直到左指標超過了右指標，這個程序將使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后，這一步叫作劃分（partition）操作，
3. 演算法對劃分后的小陣列（較主元小的值組成的子陣列，以及較主元大的值組成的子陣列）重復之前的兩個步驟，直至陣列已完全排序，

圖示

代碼

雙指標法

/** 
 * @param {number[]} nums
 * @return {number[]}
 */

var sortArray = function (nums) {
  const N = nums.length;
  quickSort(nums, 0, N - 1);
  return nums;
};

function quickSort(nums, left, right) {
  if (right <= left) {
    return;
  }
  let pIndex = partition(nums, left, right);
  quickSort(nums, left, pIndex - 1);
  quickSort(nums, pIndex + 1, right);
}

function partition(nums, left, right) {

  let pivot = nums[left];
  // 為兩個陣列分別定義一個指標
  let i = left + 1;
  let j = right;

  while (true) {
    while (i <= right && nums[i] <= pivot) {
      i++;
    }
    while (j > left && nums[j] > pivot) {
      j--;
    }
    if (i >= j) {
      break;
    }
    swap(nums, i, j);
    i++;
    j--;
  }
  swap(nums, left, j);
  return j;
}

復雜度分析

時間復雜度： O ( N log ? N ) O(N \log N) O(NlogN)，這里 N N N 是陣列的長度；
空間復雜度： O ( log ? N ) O(\log N) O(logN)，這里占用的空間主要來自遞回函式的堆疊空間，

7. 堆排序（重點）

概念

先來看看什么是堆

當一棵二叉樹的每個結點都大于等于它的兩個子結點時，它被稱為堆有序，
根結點是堆有序的二叉樹中的最大結點
一棵大小為N的完全二叉樹的高度為[lgN]

大頂堆：邏輯上是完全二叉樹，對于樹中任意節點，其關鍵字的值都不小于其孩子節點的關鍵字的值，

在堆上的一些操作

父節點位置為i，其左孩子節點位置為2i+1，右孩子節點位置為2i+2
最后一個非葉節點編號為 [n/2] - 1 （向下取整）
在一個堆中，位置k的結點的父結點的位置為[k/2]，而它的兩個子結點的位置則分別為2k和2k+1
從a[k]向上一層就令k等于k/2，向下一層則令k等于2k或2k+1

書上看的一個比較有意思的描述

我們把堆想象成一個嚴密的黑社會組織，每個子結點都表示一個下屬（父結點則表示它的直接上級），那么這些操作就可以得到很有趣的解釋，swim()【上浮】表示一個很有能力的新人加入組織并被逐級提升（將能力不夠的上級踩在腳下），直到他遇到了一個更強的領導，sink()【下沉】則類似于整個社團的領導退休并被外來者取代之后，如果他的下屬比他更厲害，他們的角色就會交換，這種交換會持續下去直到他的能力比其下屬都強為止，

function swim(k){
  while(k > 1 && nums[Math.floor(k/2)] < nums[k]){
    swap(nums, Math.floor(k/2), k);
    k = Math.floor(k/2);
  }
}

function sink(k){
  while(2*k <= N) {
    let j = 2 * k;
    if(j < N && nums[j] < nums[j+1]){
      j++;
    }
    if(nums[k] >= nums[j]){
      break;
    }
    swap(nums, k, j);
    k = j;
  }
}

1. 建堆

1. 找出完全二叉樹中最后一個非葉節點 [n/2] - 1
2. 比較這個節點和其孩子節點的大小，如果小于孩子的最大值，就交換他們的值，交換后繼續比較其與當前孩子的值的情況，進行同樣的處理
3. 指標不斷上移（減一）回圈步驟2

2. 插入節點

1. 將要插入的節點放入所有節點的最后面
2. 找到這個節點到根節點的一條路徑，如果比父節點大，就交換，直到不大于父節點的大小

3. 洗掉節點

1. 將要洗掉的節點拿出來
2. 用堆中最后一個節點替換到待洗掉的節點的位置
3. 對交換后的節點進行和【建堆步驟2】類似的調整

流程

堆排序可以分為兩個階段，在堆的構造階段中，我們將原始陣列重新組織安排進一個堆中；然后在下沉排序階段，我們從堆中按遞減順序取出所有元素并得到排序結果，

1. 將初始待排序關鍵字序列 ( R 1 , R 2 . . . . R n ) (R_1, R_2 .... R_n) (R1?,R2?....Rn?) 構建成大頂堆，此堆為初始的無序區；[堆的有序化（reheapifying）]
2. 將堆頂元素 R[1] 與最后一個元素 R[n] 交換，此時得到新的無序區 ( R 1 , R 2 . . . . R n ? 1 ) (R_1, R_2 .... R_{n-1}) (R1?,R2?....Rn?1?)和新的有序區 ( R n ) (R_n) (Rn?) ，且滿足 R [ 1 , 2... n ? 1 ] < = R [ n ] R[1, 2 ... n-1] <= R[n] R[1,2...n?1]<=R[n]，
3. 由于交換后新的堆頂 R[1] 可能違反堆的性質，因此需要對當前無序區 ( R 1 , R 2 . . . . R n ? 1 ) (R_1, R_2 .... R_{n-1}) (R1?,R2?....Rn?1?)調整為新堆，然后再次將 R[1] 與無序區最后一個元素交換，得到新的無序區 ( R 1 , R 2 . . . . R n ? 2 ) (R_1, R_2 .... R_{n-2}) (R1?,R2?....Rn?2?)和新的有序區 ( R n ? 1 , R n ) (R_{n-1}, R_n) (Rn?1?,Rn?)，不斷重復此程序，直到有序區的元素個數為 n ? 1 n - 1 n?1，則整個排序程序完成，

圖示

代碼

/**
 * 堆排序
 * @param {*} nums
 * @returns
 */
function sortArray(nums) {
  const N = nums.length;
  // 建堆 找到第一個非葉子節點，向上遍歷
  for (let i = Math.floor(N / 2 - 1); i >= 0; i--) {
    // 對 i位置節點 調整堆
    heapify(nums, i, N);
  }
  // 排序程序 每一次回圈都找出當前最大值（根節點），陣列長度減一
  for (let i = N - 1; i > 0; i--) {
    // 根節點與最后一個節點交換位置（將此時最大元素移動到陣列末尾）
    swap(nums, 0, i);
    // 對 此時的根節點 調整堆 最后的元素不用參與調整
    heapify(nums, 0, i);
  }
  return nums;
}

/**
 * 對節點i進行 調整堆
 * 滿足：i節點以下的子堆是一個大頂堆
 * 調整范圍 [i, length)
 * @param {*} nums
 * @param {*} i
 * @param {*} length
 */
function heapify(nums, i, length) {
  // 將i節點的值保存，這個程序就是給temp找到一個合適的位置
  let temp = nums[i]
  // j指向i的左孩子節點
  let j = 2 * i + 1;
  // 回圈遍歷[i, length)
  while (j < length) {
    if (j + 1 < length && nums[j] < nums[j + 1]) {
      // 父節點有右孩子 并且 左孩子小于右孩子 將j指向右孩子
      j++;
    }
    // 此時 j 指向 i 的孩子節點中較大的那個節點
    if (temp < nums[j]) {
      // 如果 父節點小于 j節點
      // 交換i，j的元素
      swap(nums, i, j);
      // 將i和j都下移一位
      i = j;
      j = 2 * i + 1; 
    } else {
      // 父節點 大于 孩子節點中最大的元素，就退出回圈
      break;
    }
  }
}

復雜度分析

堆排序包括建堆和排序兩個操作，建堆程序的時間復雜度是 O ( N ) O(N) O(N)，排序程序的時間復雜度是 O ( N log ? N ) O(N \log N) O(NlogN)，所以，堆排序整體的時間復雜度是 O ( N log ? N ) O(N \log N) O(NlogN)，

8. 計數排序（了解）

流程

1. 找出待排序的陣列中最大和最小的元素
2. 統計陣列中每個值為i的元素出現的次數，存入陣列C的第i項
3. 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）
4. 反向填充目標陣列：將每個元素i放在新陣列的第C(i)項，每放一個元素就將C(i)減去1

圖示

代碼

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue+1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}

9. 基數排序（了解）

圖示

代碼

//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

10. 桶排序（了解）

代碼

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 輸入資料的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 輸入資料的最大值
      }
    }

    //桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 設定桶的默認數量為5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    //利用映射函式將資料分配到各個桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 對每個桶進行排序，這里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                      
        }
    }

    return arr;
}

• 基數排序：根據鍵值的每位數字來分配桶；
• 計數排序：每個桶只存盤單一鍵值；
• 桶排序：每個桶存盤一定范圍的數值；

11. 總結