JS 中的排序算法

假設我們有一個沒有任何排列順序的號碼簿。當需要添加聯絡人和電話時， 你只能將其寫在下一個空位上。

假定你的聯系人列表上有很多人，某天，你要找某個聯系人及其電話號碼。但是由于聯系人列表沒有按照任何順序來組織，你只能逐個檢查，直到找到那個你想要的聯系人為止。

這個方法太嚇人了，難道你不這么認為?想象一下你要在黃頁上搜尋一個聯系 人，但是那本黃頁沒有進行任何組織，那得花多久時間啊?!

因此(還有其他原因)，我們需要組織信息集，比如那些存儲在數據結構里的信息。排序和搜索算法廣泛地運用在待解決的日常問題中。

冒泡排序

從運行時間的角度來看，冒泡排序是最差的一個。

冒泡排序比較任何兩個相鄰的項，如果第一個比第二個大，則交換它們。元素項向上移動至 正確的順序，就好像氣泡升至表面一樣，冒泡排序因此得名。

下面這個示意圖展示了冒泡排序的工作過程:

let arr = [5, 4, 3, 2, 1]
let len = arr.length
for (let i = 0; i < len; i++) {
 for (let j = 0; j < len - 1; j++) {
 if (arr[j] > arr[j+1]) {
 swap(j, j+1)
 }
 }
}
function swap(index1, index2){
 let tmp = arr[index1]
 arr[index1] = arr[index2]
 arr[index2] = tmp
}

改進后的冒泡排序

如果從內循環減去外循環中已跑過的輪數，就可以避免內循環中所有不必要的比較

下面這個示意圖展示了改進后的冒泡排序算法是如何執行的:

for (let i = 0; i < len; i++) {
 for (j = 0; j < len - 1 - i; j++) {
 if (arr[j] > arr[j+1]) {
 swap(j, j+1)
 }
 }
}

即便我們做了這個小改變，改進 了一下冒泡排序算法，但我們還是不推薦該算法，它的復雜度是 O(n ² )。

選擇排序

選擇排序大致的思路是找到數據結構中的最小值并將其放置在第一位，接著找到第二小的值并將其放在第二位，以此類推。

let arr = [5, 4, 3, 2, 1]
let len = arr.length
let indexMin = 0
for (let i = 0; i < len - 1; i++) {
 indexMin = i
 for (let j = i; j < len; j++) {
 if (arr[indexMin] > arr[j]) {
 indexMin = j
 }
 }
 if (indexMin !== i) {
 swap(indexMin, i)
 }
}

選擇排序同樣也是一個復雜度為 O(n ² ) 的算法。和冒泡排序一樣，它包含有嵌套的兩個循環， 這導致了二次方的復雜度。

插入排序

假定第一項已經排序了，接著，它和第二項進行比較，第二項是應該待在原位還是插到第一項之前呢?這樣，頭兩項就已正確排序，接著和第三項比較(它是該插入到第一、第二還是第三的位置呢?)，以此類推。

let arr = [1, 2, 3, 4, 5]
let len = arr.length
let j = 0
let tmp = 0

for (let i = 1; i < len; i++) {
 j = i
 tmp = arr[i]
 while (j > 0 && arr[j-1] > tmp) {
 arr[j] = arr[j-1]
 j--
 }
 arr[j] = tmp
}

排序小型數組時，此算法比選擇排序和冒泡排序性能要好。

歸并排序

前三個排序算法性能不好,但歸并排序性能不錯,其復雜度為 O(nlog ⁿ )。

JavaScript 的 Array 類定義了一個 sort 函數( Array.prototype.sort )用 以排序 JavaScript 數組。 ECMAScript 沒有定義用哪 個排序算法，所以瀏覽器廠商可以自行去實現算法。例如， Mozilla Firefox 使用 歸并排序作為 Array.prototype.sort 的實現，而 Chrome 使用了一個快速排序的變體。

歸并排序是一種分治算法。其思想是將原始數組切分成較小的數組，直到每個小數組只有一個位置，接著將小數組歸并成較大的數組，直到最后只有一個排序完畢的大數組。由于是分治法，歸并排序也是遞歸的:

function mergeSort (arr){
 let len = arr.length
 if (len === 1) {
 return arr
 }
 let mid = Math.floor(len / 2)
 let left = arr.slice(0, mid)
 let right = arr.slice(mid, len)
 return merge(mergeSort(left), mergeSort(right))
}
function merge (leftArr, rightArr){
 let result = []
 let leftIndex = 0
 let rightIndex = 0

 while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
 if (leftArr[leftIndex] < rightArr[rightIndex]) {
 result.push(leftArr[leftIndex])
 leftIndex++
 } else {
 result.push(rightArr[rightIndex])
 rightIndex++
 }
 }
 while (leftIndex < leftArr.length) {
 result.push(leftArr[leftIndex])
 leftIndex++
 }
 while (rightIndex < rightArr.length) {
 result.push(rightArr[rightIndex])
 rightIndex++
 }
 return result
}

算法首先將原始數組分割直至只有一個元素的子數組，然后開始歸并。歸并過程

也會完成排序，直至原始數組完全合并并完成排序。

快速排序

快速排序的復雜度為 O(nlog ⁿ )，且它的性能通常比其他的復雜度為 O(nlog ⁿ ) 的排序算法要好。和歸并排序一樣，快速排序也使用分治的方法，將原始數組分為較小的數組(但它沒有像歸并排序那樣將它們分割開)。

1. 首先，從數組中選擇中間一項作為主元
2. 創建兩個指針，左邊一個指向數組第一項，右邊一個指向數組的最后一項。移動左指針，直到找到一個比主元大的元素，接著，移動右指針直到找到一個比主元小的元素，然后交換它們，重復這個過程，直到左指針超過了右指針。這個過程使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。這一步叫做劃分操作。
3. 接著，算法對劃分后的小數組重復之前兩個步驟，直至數組已完全排序。

function quick (arr, left, right){
 let index = 0
 if (arr.length > 1) {
 index = partition(arr, left, right)
 if (left < index - 1) {
 quick(arr, left, index - 1)
 }
 if (index < right) {
 quick(arr, index, right)
 }
 }
}
function partition (arr, left, right){
 let pivot = arr[Math.floor((right + left) / 2)]
 let i = left
 let j = right
 while (i <= j) {
 while (arr[i] < pivot) {
 i++
 }
 while (arr[j] > pivot) {
 j--
 }
 if (i <= j) {
 swap(arr, i, j)
 i++
 j--
 }
 }
 return i
}

 

來自：http://mertensming.github.io/2016/11/10/js-sorting-algorithms/