排序算法初探

冒泡排序#

冒泡排序是一種簡單的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢 “浮” 到數列的頂端。

冒泡排序算法的運作如下：

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
針對所有的元素重複以上的步驟，除了最後一個。
持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

冒泡排序平均時間複雜度 O (n^2)，在最好情況下，即一次排完時複雜度為 O (n)，在最壞情況下複雜度為 O (n^2)。

經典冒泡算法#

經典冒泡算法：通過雙層循環實現排序，外層循環表示當前是第幾輪排序，內層循環表示當前輪的第幾次排序，通過兩兩比較交換位置完成排序。

function bubbleSort(nums) {
  const len = nums.length
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        ;[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]] // 交換位置
      }
    }
  }
  return nums
}

改進冒泡算法#

改進冒泡算法：設置一標誌性變量 pos，用於記錄每輪排序中最後一次進行交換的位置。由於 pos 位置之後的記錄均已交換到位，故在進行下一輪排序時只要掃描到 pos 位置即可。

function bubbleSort(nums) {
  const len = nums.length
  let i = len - 1
  while (i > 0) {
    let pos = 0
    for (let j = 0; j < i; j++) {
      if (nums[j] > nums[j + 1]) {
        pos = j // 記錄交換時的位置
        ;[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]] // 交換位置
      }
    }
    i = pos
  }
  return nums
}

終極冒泡算法#

終極冒泡算法：傳統冒泡排序中每一輪排序操作只能找到一個最大值或最小值，可以在每趟排序中進行正向和反向兩遍冒泡方法一次得到兩個最終值（最大者和最小者），從而使排序輪數幾乎減少了一半。

function bubbleSort(nums) {
  let low = 0
  let high = nums.length - 1
  let i
  while (low < high) {
    // 正向排序，找出最大值
    for (i = low; i < high; ++i) {
      if (nums[i] > nums[i + 1]) {
        ;[nums[i], nums[i + 1]] = [nums[i + 1], nums[i]] // 交換位置
      }
    }
    --high // 前移一位

    // 反向排序，找出最小值
    for (i = high; i > low; --i) {
      if (nums[i] < nums[i - 1]) {
        ;[nums[i], nums[i - 1]] = [nums[i - 1], nums[i]] // 交換位置
      }
    }
    ++low // 後移一位
  }
  return nums
}

選擇排序#

選擇排序是一種簡單直觀的排序算法。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩余未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序算法的運作如下：

初始狀態：無序區為 R [1..n]，有序區為空。
第 i 輪排序開始時，當前有序區和無序區分別為 R [1..i-1] 和 R [i..n]。然後從當前無序區中選出最小值，將它與無序區的第一個值交換，使得新增一位有序區和減少一位無序區。
n-1 輪排序結束，數組全部變為有序區，從而完成排序。

選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對 n 個元素的表進行排序總共進行至多 n-1 次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種。

選擇排序平均時間複雜度穩定在 O (n^2)。

經典選擇算法#

經典選擇算法：將數列分為有序區和無序區兩部分，在每輪循環中從無序區選擇一個最小值並入有序區，新增一位有序區同時減少一位無序區，n - 1 輪排序後全部變為有序區，從而完成排序。

function selectionSort(nums) {
  const len = nums.length
  let min = 0
  for (let i = 0; i < len - 1; i++) {
    min = i
    for (let j = i + 1; j < len; j++) {
      if (nums[min] > nums[j]) {
        min = j // 保存最小值的索引
      }
    }
    ;[nums[i], nums[min]] = [nums[min], nums[i]] // 交換位置
  }
  return nums
}

插入排序#

是一種簡單的排序算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用 in-place 排序，因而在從後向前掃描過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間。

插入排序算法的運作如下：

從第一個元素開始，該元素可以認為已經被排序。
取出下一個元素，在已排序的元素序列中從後向前掃描，如果該元素大於新元素，將該元素移到下一位置。
重複步驟 2，直到找到已排序的元素小於或者等於新元素的位置，將新元素插入到該位置後。
重複步驟 2~3，直到完成排序。

插入排序平均時間複雜度 O (n^2)，在最好情況下複雜度為 O (n)，在最壞情況下複雜度為 O (n^2)。

經典插入算法#

function insertionSort(nums) {
  const len = nums.length
  for (let i = 1; i < len; i++) {
    let k = nums[i]
    let j = i - 1
    while (j >= 0 && nums[j].num > k.num) {
      nums[j + 1] = num[j]
      j--
    }
    nums[j + 1] = k
  }
  return nums
}

二分插入算法#

二分插入算法：查找插入位置時使用二分查找的方式，在插入值之前，先在有序區中找到待插入值需要比較的左邊界，在數據長度較大時，可以有效減少每輪排序中的查找插入位置的次數。

function insertionSort(nums) {
  const len = nums.length
  for (let i = 1; i < len; i++) {
    let k = nums[i]
    let left = 0
    let right = i - 1
    while (left <= right) {
      let middle = ~~((left + right) / 2)
      if (k < nums[middle]) {
        right = middle - 1
      } else {
        left = middle + 1
      }
    }
    for (let j = i - 1; j >= left; j--) {
      nums[j + 1] = nums[j]
    }
    nums[left] = k
  }
  return nums
}

归并排序#

归并排序是创建在归并操作上的一种有效的排序算法。归并操作也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序时间复杂度为 O (nlogn)。该算法是采用分治法的一个非常典型的应用，且各层分治递归可以同时进行。

归并排序算法的运作如下：

将长度为 n 的序列每相邻两个数字进行归并操作，形成 n/2 个序列，排序后每个序列包含二或一个元素。
若此时序列数不是 1 个则将上述序列再次归并，形成 n/4 个序列，每个序列包含三或四个元素。
重复步骤 2，直到所有元素排序完毕，即序列数为 1，即完成排序。
归并排序平均时间复杂度稳定在 O (nlogn)。

经典运用算法#

经典归并算法：将数列分为两个子序列，如果子序列长度不为一，再将子序列细分，直至子序列长度为一。递归比较两个子序列并排序后，再相互组合成有序数列，最终完成排序。

function mergeSort(nums) {
  const len = nums.length
  if (len <= 1) return nums
  let middle = ~~(len / 2)
  let left = nums.slice(0, middle)
  let right = nums.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
  const result = []
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  return result.concat(left, right)
}