本文內容包括：(雙向)冒泡排序、選擇排序、插入排序、快速排序(填坑和交換)、歸并排序、桶排序、基數排序、計數排序(優化)、堆排序、希爾排序。大家可以在這里測試代碼。更多 leetcode 的 JavaScript 解法也可以在我的算法倉庫中找到，歡迎查看~

另外附上十大排序的 C++版本，因為寫慣了JavaScript，所以這個 C++版本寫得有些丑，請不要介意呀。

如果你覺得有幫助的話，就點個 star 鼓勵鼓勵我吧，蟹蟹😊

先推薦一個數據結構和算法動態可視化工具，可以查看各種算法的動畫演示。下面開始正文。

冒泡排序

通過相鄰元素的比較和交換，使得每一趟循環都能找到未有序數組的***值或最小值。

***：O(n)，只需要冒泡一次數組就有序了。 

最壞：O(n²) 

平均：O(n²)

單向冒泡 

function bubbleSort(nums) {  
  for(let i=0, len=nums.length; i<len-1; i++) {  
    // 如果一輪比較中沒有需要交換的數據，則說明數組已經有序。主要是對[5,1,2,3,4]之類的數組進行優化  
    let mark = true;  
    for(let j=0; j<len-i-1; j++) {  
      if(nums[j] > nums[j+1]) {  
        [nums[j], nums[j+1]] = [nums[j+1], nums[j]];  
        mark = false;  
      }  
    }  
    if(mark)  return;  
  }  
}  

雙向冒泡

普通的冒泡排序在一趟循環中只能找出一個***值或最小值，雙向冒泡則是多一輪循環既找出***值也找出最小值。 

function bubbleSort_twoWays(nums) {  
  let low = 0;  
  let high = nums.length - 1;  
  while(low < high) {  
    let mark = true;  
    // 找到***值放到右邊  
    for(let i=low; i<high; i++) {  
      if(nums[i] > nums[i+1]) {  
        [nums[i], nums[i+1]] = [nums[i+1], nums[i]];  
        mark = false;  
      }  
    }  
    high--;  
    // 找到最小值放到左邊  
    for(let j=high; j>low; j--) {  
      if(nums[j] < nums[j-1]) {  
        [nums[j], nums[j-1]] = [nums[j-1], nums[j]];  
        mark = false;  
      }  
    }  
    low++;  
    if(mark)  return;  
  }  
}  

選擇排序

和冒泡排序相似，區別在于選擇排序是將每一個元素和它后面的元素進行比較和交換。

***：O(n²) 

最壞：O(n²) 

平均：O(n²) 

function selectSort(nums) {  
  for(let i=0, len=nums.length; i<len; i++) {  
    for(let j=i+1; j<len; j++) {  
      if(nums[i] > nums[j]) {  
        [nums[i], nums[j]] = [nums[j], nums[i]];  
      }  
    }  
  }  
}  

插入排序

以***個元素作為有序數組，其后的元素通過在這個已有序的數組中找到合適的位置并插入。

***：O(n)，原數組已經是升序的。 

最壞：O(n²) 

平均：O(n²) 

function insertSort(nums) {  
  for(let i=1, len=nums.length; i<len; i++) {  
    let temp = nums[i];  
    let j = i;  
    while(j >= 0 && temp < nums[j-1]) {  
      nums[j] = nums[j-1];  
      j--;  
    }  
    nums[j] = temp;  
  }  
}  

快速排序

選擇一個元素作為基數（通常是***個元素），把比基數小的元素放到它左邊，比基數大的元素放到它右邊（相當于二分），再不斷遞歸基數左右兩邊的序列。

***：O(n * logn)，所有數均勻分布在基數的兩邊，此時的遞歸就是不斷地二分左右序列。 

最壞：O(n²)，所有數都分布在基數的一邊，此時劃分左右序列就相當于是插入排序。 

平均：O(n * logn)

參考學習鏈接： 

算法 3：最常用的排序——快速排序 

三種快速排序以及快速排序的優化

快速排序之填坑

從右邊向中間推進的時候，遇到小于基數的數就賦給左邊（一開始是基數的位置），右邊保留原先的值等之后被左邊的值填上。 

function quickSort(nums) {  
  // 遞歸排序基數左右兩邊的序列  
  function recursive(arr, left, right) {  
    if(left >= right)  return;  
    let index = partition(arr, left, right);  
    recursive(arr, left, index - 1);  
    recursive(arr, index + 1, right);  
    return arr;  
  }  
  // 將小于基數的數放到基數左邊，大于基數的數放到基數右邊，并返回基數的位置  
  function partition(arr, left, right) {  
    // 取***個數為基數  
    let temp = arr[left];  
    while(left < right) {  
      while(left < right && arr[right] >= temp)  right--;  
      arr[left] = arr[right];  
      while(left < right && arr[left] < temp)  left++;  
      arr[right] = arr[left];  
    }  
    // 修改基數的位置  
    arr[left] = temp;  
    return left;  
  }  
  recursive(nums, 0, nums.length-1);  
}  

快速排序之交換

從左右兩邊向中間推進的時候，遇到不符合的數就兩邊交換值。 

function quickSort1(nums) {  
  function recursive(arr, left, right) {  
    if(left >= right)  return;  
    let index = partition(arr, left, right);  
    recursive(arr, left, index - 1);  
    recursive(arr, index + 1, right);  
    return arr;  
  }  
  function partition(arr, left, right) {  
    let temp = arr[left];  
    let p = left + 1;  
    let q = right;  
    while(p <= q) {  
      while(p <= q && arr[p] < temp)  p++;  
      while(p <= q && arr[q] > temp)  q--;  
      if(p <= q) {  
        [arr[p], arr[q]] = [arr[q], arr[p]];  
        // 交換值后兩邊各向中間推進一位  
        p++;  
        q--;  
      }  
    }  
    // 修改基數的位置  
    [arr[left], arr[q]] = [arr[q], arr[left]];  
    return q;  
  }  
  recursive(nums, 0, nums.length-1);  
}  

歸并排序

遞歸將數組分為兩個序列，有序合并這兩個序列。

***：O(n * logn) 

最壞：O(n * logn) 

平均：O(n * logn)

參考學習鏈接： 

圖解排序算法(四)之歸并排序 

function mergeSort(nums) {  
  // 有序合并兩個數組  
  function merge(l1, r1, l2, r2) {  
    let arr = [];  
    let index = 0;  
    let i = l1, j = l2;  
    while(i <= r1 && j <= r2) {  
      arr[index++] = nums[i] < nums[j] ? nums[i++] : nums[j++];  
    }  
    while(i <= r1)  arr[index++] = nums[i++];  
    while(j <= r2)  arr[index++] = nums[j++];  
    // 將有序合并后的數組修改回原數組  
    for(let t=0; t<index; t++) {  
      nums[l1 + t] = arr[t];  
    }  
  }  
  // 遞歸將數組分為兩個序列  
  function recursive(left, right) {  
    if(left >= right)  return;  
    // 比起(left+right)/2，更推薦下面這種寫法，可以避免數溢出  
    let mid = parseInt((right - left) / 2) + left;  
    recursive(left, mid);  
    recursive(mid+1, right);  
    merge(left, mid, mid+1, right);  
    return nums;  
  }  
  recursive(0, nums.length-1);  
}  

桶排序

取 n 個桶，根據數組的***值和最小值確認每個桶存放的數的區間，將數組元素插入到相應的桶里，***再合并各個桶。

***：O(n)，每個數都在分布在一個桶里，這樣就不用將數插入排序到桶里了(類似于計數排序以空間換時間)。 

最壞：O(n²)，所有的數都分布在一個桶里。 

平均：O(n + k)，k表示桶的個數。

參考學習鏈接： 

拜托，面試別再問我桶排序了！！！ 

function bucketSort(nums) {  
  // 桶的個數，只要是正數即可  
  let num = 5;  
  let max = Math.max(...nums);  
  let min = Math.min(...nums);  
  // 計算每個桶存放的數值范圍，至少為1，  
  let range = Math.ceil((max - min) / num) || 1;  
  // 創建二維數組，***維表示第幾個桶，第二維表示該桶里存放的數  
  let arr = Array.from(Array(num)).map(() => Array().fill(0));  
  nums.forEach(val => {  
    // 計算元素應該分布在哪個桶  
    let index = parseInt((val - min) / range);  
    // 防止index越界，例如當[5,1,1,2,0,0]時index會出現5  
    indexindex = index >= num ? num - 1 : index;  
    let temp = arr[index];  
    // 插入排序，將元素有序插入到桶中  
    let j = temp.length - 1;  
    while(j >= 0 && val < temp[j]) {  
      temp[j+1] = temp[j];  
      j--;  
    }  
    temp[j+1] = val;  
  })  
  // 修改回原數組  
  let res = [].concat.apply([], arr);  
  nums.forEach((val, i) => {  
    nums[i] = res[i];  
  })  
}  

基數排序

使用十個桶 0-9，把每個數從低位到高位根據位數放到相應的桶里，以此循環***值的位數次。但只能排列正整數，因為遇到負號和小數點無法進行比較。

***：O(n * k)，k表示***值的位數。 

最壞：O(n * k) 

平均：O(n * k)

參考學習鏈接： 

算法總結系列之五: 基數排序(Radix Sort) 

function radixSort(nums) {  
  // 計算位數  
  function getDigits(n) {  
    let sum = 0;  
    while(n) {  
      sum++;  
      n = parseInt(n / 10);  
    }  
    return sum;  
  }  
  // ***維表示位數即0-9，第二維表示里面存放的值  
  let arr = Array.from(Array(10)).map(() => Array());  
  let max = Math.max(...nums);  
  let maxDigits = getDigits(max);  
  for(let i=0, len=nums.length; i<len; i++) {  
    // 用0把每一個數都填充成相同的位數  
    nums[i] = (nums[i] + '').padStart(maxDigits, 0);  
    // 先根據個位數把每一個數放到相應的桶里  
    let temp = nums[i][nums[i].length-1];  
    arr[temp].push(nums[i]);  
  }  
  // 循環判斷每個位數  
  for(let i=maxDigits-2; i>=0; i--) {  
    // 循環每一個桶  
    for(let j=0; j<=9; j++) {  
      let temp = arr[j]  
      let len = temp.length;  
      // 根據當前的位數i把桶里的數放到相應的桶里  
      while(len--) {  
        let str = temp[0];  
        temp.shift();  
        arr[str[i]].push(str);  
      }  
    }  
  }  
  // 修改回原數組  
  let res = [].concat.apply([], arr);  
  nums.forEach((val, index) => {  
    nums[index] = +res[index];  
  })   
}  

計數排序

以數組元素值為鍵，出現次數為值存進一個臨時數組，***再遍歷這個臨時數組還原回原數組。因為 JavaScript 的數組下標是以字符串形式存儲的，所以計數排序可以用來排列負數，但不可以排列小數。

***：O(n + k)，k是***值和最小值的差。 

最壞：O(n + k) 

平均：O(n + k) 

function countingSort(nums) {  
  let arr = [];  
  let max = Math.max(...nums);  
  let min = Math.min(...nums);  
  // 裝桶  
  for(let i=0, len=nums.length; i<len; i++) {  
    let temp = nums[i];  
    arr[temp] = arr[temp] + 1 || 1;  
  }  
  let index = 0;  
  // 還原原數組  
  for(let i=min; i<=max; i++) {  
    while(arr[i] > 0) {  
      nums[index++] = i;  
      arr[i]--;  
    }  
  }  
}  

計數排序優化

把每一個數組元素都加上 min 的相反數，來避免特殊情況下的空間浪費，通過這種優化可以把所開的空間大小從 max+1 降低為 max-min+1，max 和 min 分別為數組中的***值和最小值。

比如數組 [103, 102, 101, 100]，普通的計數排序需要開一個長度為 104 的數組，而且前面 100 個值都是 undefined，使用該優化方法后可以只開一個長度為 4 的數組。 

function countingSort(nums) {  
  let arr = [];  
  let max = Math.max(...nums);  
  let min = Math.min(...nums);  
  // 加上最小值的相反數來縮小數組范圍  
  let add = -min;  
  for(let i=0, len=nums.length; i<len; i++) {  
    let temp = nums[i];  
    temp += add;  
    arr[temp] = arr[temp] + 1 || 1;  
  }  
  let index = 0;  
  for(let i=min; i<=max; i++) {  
    let temp = arr[i+add];  
    while(temp > 0) {  
      nums[index++] = i;  
      temp--;  
    }  
  }  
}  

堆排序

根據數組建立一個堆（類似完全二叉樹），每個結點的值都大于左右結點（***堆，通常用于升序），或小于左右結點（最小堆，通常用于降序）。對于升序排序，先構建***堆后，交換堆頂元素（表示***值）和堆底元素，每一次交換都能得到未有序序列的***值。重新調整***堆，再交換堆頂元素和堆底元素，重復 n-1 次后就能得到一個升序的數組。

***：O(n * logn)，logn是調整***堆所花的時間。 

最壞：O(n * logn) 

平均：O(n * logn)

參考學習鏈接： 

常見排序算法 - 堆排序 (Heap Sort) 

圖解排序算法(三)之堆排序 

function heapSort(nums) {  
  // 調整***堆，使index的值大于左右節點  
  function adjustHeap(nums, index, size) {  
    // 交換后可能會破壞堆結構，需要循環使得每一個父節點都大于左右結點  
    while(true) {  
      let max = index;  
      let left = index * 2 + 1;   // 左節點  
      let right = index * 2 + 2;  // 右節點  
      if(left < size && nums[max] < nums[left])  max = left;  
      if(right < size && nums[max] < nums[right])  max = right;  
      // 如果左右結點大于當前的結點則交換，并再循環一遍判斷交換后的左右結點位置是否破壞了堆結構（比左右結點小了）  
      if(index !== max) {  
        [nums[index], nums[max]] = [nums[max], nums[index]];  
        index = max;  
      }  
      else {  
        break;  
      }  
    }  
  }  
  // 建立***堆  
  function buildHeap(nums) {  
    // 注意這里的頭節點是從0開始的，所以***一個非葉子結點是 parseInt(nums.length/2)-1  
    let start = parseInt(nums.length / 2) - 1;  
    let size = nums.length;  
    // 從***一個非葉子結點開始調整，直至堆頂。  
    for(let i=start; i>=0; i--) {  
      adjustHeap(nums, i, size);  
    }  
  }  
  buildHeap(nums);  
  // 循環n-1次，每次循環后交換堆頂元素和堆底元素并重新調整堆結構  
  for(let i=nums.length-1; i>0; i--) {  
    [nums[i], nums[0]] = [nums[0], nums[i]];  
    adjustHeap(nums, 0, i);  
  }  
}  

希爾排序

通過某個增量 gap，將整個序列分給若干組，從后往前進行組內成員的比較和交換，隨后逐步縮小增量至 1。希爾排序類似于插入排序，只是一開始向前移動的步數從 1 變成了 gap。

***：O(n * logn)，步長不斷二分。 

最壞：O(n * logn) 

平均：O(n * logn)

參考學習鏈接： 

圖解排序算法(二)之希爾排序 

function shellSort(nums) {  
  let len = nums.length;  
  // 初始步數  
  let gap = parseInt(len / 2);  
  // 逐漸縮小步數  
  while(gap) {  
    // 從第gap個元素開始遍歷  
    for(let i=gap; i<len; i++) {  
      // 逐步其和前面其他的組成員進行比較和交換  
      for(let j=i-gap; j>=0; j-=gap) {  
        if(nums[j] > nums[j+gap]) {  
          [nums[j], nums[j+gap]] = [nums[j+gap], nums[j]];  
        }  
        else {  
          break;  
        }  
      }  
    }  
    gap = parseInt(gap / 2);  
  }  
}  

看完后如果大家有什么疑問或發現一些錯誤，可以在下方留言呀，或者在我的倉庫里 提issues，我們一起討論討論😊