摘要：回顧選擇排序，插入排序，冒泡排序，快速排序，希爾排序，歸并排序，堆排序以及如何計算時間復雜度學習文章同學的描述數據結構等同學的十大經典算法本文代碼也上傳到了排序算法回顧。但希爾排序是非穩定排序算法。

回顧選擇排序，插入排序，冒泡排序，快速排序，希爾排序，歸并排序，堆排序以及如何計算時間復雜度
學習文章：hahda同學的javascript描述數據結構、hustcc等同學的十大經典算法

本文代碼也上傳到了 排序算法回顧(javascript)。

思路：從未排序的序列中選出最小(大)的元素，放進已排好序的序列末尾。
時間復雜度：O(n^2)
算法穩定性：不穩定

// 定義一個函數用于交換
function swap (array, i, j) {
  let temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

function selectionSort (arr) {
  let minIndex;
  for (let i = 0; i < arr.length; i++) {
    minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {  // 對未排序的序列進行循環，找出最小元素。
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    swap(arr, i, minIndex);                     // 最小元素與放如排好序的序列末尾。
  }
  return arr;
}

let arr = [1,2,8,4,3,6,10];

selectionSort(arr)   // 1，2，3，4，6，8，10

選擇排序所需要的元素比較次數為 (n-1) + (n-2) + ... + 1 = n*(n-1)/2 ，元素賦值次數界于 0 ~ 3(n-1) 之間，也就是原序列已排好序于原序列為反序兩種極端情況。

思路：從第二個元素往后遍歷，從前面的序列中找到一個合適的位置進行插入。
時間復雜度：O(n^2)
算法穩定性：穩定

let arr = [5,3,2,6,7,10,1];  // 進行小到達排序

function InsertionSort(arr) {
  let len = arr.length;
  for (let i = 1; i < len; i++) {
    let curr = arr[i];                    // 要執行插入操作的元素
    let j = i;                            // 從i開始往回遍歷
    while (j > 0 && arr[j-1] > curr) {   
// 不斷跟curr元素進行比較，大于curr的往后退一位，最終給curr騰出一個插入的位置
      arr[j] = arr[j-1];
      j--;
    }
    arr[j] = curr                         // curr插入到合適的位置中
  }
  return arr;
}

console.log(InsertionSort(arr)); // 1,2,3,5,6,7,10

容易看出，當序列已排好序的時候，元素比較的次數最少，比較次數為 n - 1 次，每一個元素只需要和前一個元素比較即可，當序列是按反序排列，那么比較次數最多，比較次數為 n*(n-1)/2 。
元素賦值次數為等于比較次數加上 n - 1。

思路：多次遍歷序列，比較相鄰元素，將最大(最小)元素像泡泡一樣冒到后面已排好序的序列中。
時間復雜度：O(n^2)
算法穩定性：穩定

function advanceBubbleSort1(arr){
    let len = arr.length;
    let flag;          // 設置一個標記，如果某一輪沒有交換，表示已經排好序了。不必再循環遍歷。
    for(let i = 1, i <= len - 1; i++){
        flag = false;
        for(let j = 0; j < len - i; j++){
            if(arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if(flag === false){
            break;
        }
    }
    return arr;
}

快速排序是一個非常流行并且高效的排序算法。
它之所以高效是因為它在原位上進行排序，不需要輔助的存儲空間。
思路：以最左元素作為主元進行劃分，最后再將主元放回正確位置，遞歸。
平均時間復雜度 Θ(nlogn), 最壞的情況 θ(n^2)
算法穩定性：不穩定

在了解快速排序之前需要了解一個關鍵算法：劃分算法

function partition(arr, left ,right) {   // 分區操作
  var pivot = left,                      // 設定基準值（pivot）,即以最左元素為主元
      index = pivot + 1;
  for (var i = left + 1; i <= right; i++) {
      if (arr[i] < arr[pivot]) {
          swap(arr, i, index);
          index++;
      }        
  }
  swap(arr, pivot, index - 1);          // 最后把主元放回正確位置
  return index-1;
}


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

我們可以看到，整個劃分都在原數組上進行，不需要引進額外的輔助數組。
快速排序算法需要以劃分算法為核心：

function quickSort(arr, left, right) {
  var len = arr.length,
      partitionIndex;

  if (left < right) {
      partitionIndex = partition(arr, left, right);
      quickSort(arr, left, partitionIndex-1);
      quickSort(arr, partitionIndex+1, right);
  }
  return arr;
}

let arr = [1,6,3,8,5,0,7]

console.log(quickSort(arr, 0, 6))     // 0，1，3，5，6，7，8

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。
平均時間復雜度：O(nlogn)
算法穩定性：不穩定
思路：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

function shellSort(arr) {
  var len = arr.length,
      temp,
      gap = 1;
      while (gap < len/3) {
        gap = gap*3 + 1;
      }
      for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
          temp = arr[i];
          for (var j = i-gap; i >= 0 && arr[j] > temp; j-=gap) {
            arr[j + gap] = arr[j];
          }
          arr[j + gap] = temp;
        }
      }
      return arr;
}

let arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

console.log(shellSort(arr)); // [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

歸并排序采用分治法的思想。這里給出一種自上而下遞歸的方法。
思路：分半->分半->再分半->分到每組只剩下一個元素的時候就回溯
平均時間復雜度：O(nlogn)
算法穩定性： 穩定

function mergeSort(arr) {
  var len = arr.length;
  if (len < 2) {
    return arr;
  }
  var middle = Math.floor(len/2),
      left = arr.slice(0, middle),
      right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
  var result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());

  return result;
}

let arr = [5, 3, 6, 8, 2, 0, 1];
console.log(mergeSort(arr)); // [ 0, 1, 2, 3, 5, 6, 8 ]

堆排序是指利用堆這種數據結構所設計的一種排序算法。
大項堆：每個節點的值都大于或等于其子節點的值，用于升序排序
小項堆：每個節點的值都小于或等于其子節點，用于降序排序
平均時間復雜度：O(nlogn)
算法穩定性： 不穩定

var len;

function buildMaxHeap(arr) {   // 建立大頂堆
    len = arr.length;
    for (var i = Math.floor(len/2) - 1; i >= 0; i--) {
        heapify(arr, i);
    }
}

function heapify(arr, i) {     // 堆調整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}

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

function heapSort(arr) {
    buildMaxHeap(arr);

    for (var i = arr.length-1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

let arr = [4,3,8,10,11,13,7,30,17,26];
console.log(heapSort(arr))  // [ 3, 4, 7, 8, 10, 11, 13, 17, 26, 30 ]

了解幾個概念：

O 符號表示一個運行時間的上界。

Ω 符號表示一個運行時間的下界。

θ 符號表示一個精準描述。

可以這樣幫助理解，O 類似于 <= ,Ω 類似于 >=, θ 類似于 = ，但只能說是類似于。

如

let i = 0;
for (let i = 0; i < n; i++) {
  i ++;
}

可以看到迭代次數為n，所以時間復雜度為 θ(n)

什么是基本運算呢？

在分析搜索和排序算法時，如果比較是元運算（不能再細化的運算），可以選擇它為基本運算

矩陣乘法算法中，可以選擇數量乘法運算

遍歷鏈表時，可以選擇設置或更新指針的運算

再圖的遍歷中可以選擇訪問結點的動作和被訪問結點的計算

如上一份代碼

let i = 0;
for (let i = 0; i < n; i++) {
  i ++;
}

選擇自加運算，同理得時間復雜度 θ(n)