①冒泡算法
②選擇排序
③插入排序
④快速排序件
認證
開源
平臺行業詞雲分析中有哪幾種排序方式
搜索
登錄/註冊
會員中心
收藏
動態
創作
常見的幾種排序方法
從零開始學前端 於 2019-06-01 09:34:54 發布 4965 收藏
分類專欄： 從零開始學前端
版權
從零開始學前端
專欄收錄該內容
198 篇文章2 訂閱
訂閱專欄
常見的幾種排序方法
1.背景介紹
在計算機科學與數學中，壹個排序算法（英語：Sorting algorithm）是壹種能將壹串資料依照特定排序方式進行排列的壹種算法。 最常用到的排序方式是數值順序以及字典順序。有效的排序算法在壹些算法（例如搜尋算法與合並算法）中是重要的， 如此這些算法才能得到正確解答。 排序算法也用在處理文字資料以及產生人類可讀的輸出結果。 基本上，排序算法的輸出必須遵守下列兩個原則：
輸出結果為遞增序列（遞增是針對所需的排序順序而言）
輸出結果是原輸入的壹種排列、或是重組
雖然排序算法是壹個簡單的問題，但是從計算機科學發展以來，在此問題上已經有大量的研究。 更多的新算法仍在不斷的被發明。
2.知識剖析
查找和排序算法是算法的入門知識，其經典思想可以用於很多算法當中。因為其實現代碼較短，應用較常見。 所以在面試中經常會問到排序算法及其相關的問題。但萬變不離其宗，只要熟悉了思想，靈活運用也不是難事。 壹般在面試中最常考的是快速排序和歸並排序，並且經常有面試官要求現場寫出這兩種排序的代碼。 對這兩種排序的代碼壹定要信手拈來才行。還有插入排序、冒泡排序、堆排序、基數排序、桶排序等。
常見的幾種算法：
①冒泡算法
②選擇排序
③插入排序
④快速排序
常見問題
問題壹:各種排序算法用JavaScript 如何實現?
問題二:各種排序算法的優劣及其應用?
解決方案
問題壹:各種排序算法用JavaScript 如何實現?
問題二:各種排序算法的優劣及其應用?
解決方案、
冒泡排序
冒泡排序（英語：Bubble Sort）是壹種簡單的排序算法。它重復地走訪過要排序的數列，壹次比較兩個元素， 如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有元素再需要交換， 也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端。
冒泡排序演算法的運作如下：
比較相鄰的元素。如果第壹個比第二個大，就交換他們兩個。
對每壹對相鄰元素作同樣的工作，從開始第壹對到結尾的最後壹對。這步做完後，最後的元素會是最大的數。
針對所有的元素重復以上的步驟，除了最後壹個。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何壹對數字需要比較。
代碼實現:
Array.prototype.bubbleSort = function () {undefined
var i, j, temp;
for (i = 0; i < this.length - 1; i++)
for (j = 0; j < this.length - 1 - i; j++)
if (this[j] > this[j + 1]) {undefined
temp = this[j];
this[j] = this[j + 1];
this[j + 1] = temp;
}
return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];//定義壹個數組
num.bubbleSort();//數組調用冒泡排序算法
選擇排序（Selection sort）是壹種簡單直觀的排序算法。它的工作原理如下。 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩余未排序元素中繼續尋找最小（大）元素， 然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。 選擇排序的思想其實和冒泡排序有點類似，都是在壹次排序後把最小的元素放到最前面。但是過程不同， 冒泡排序是通過相鄰的比較和交換。而選擇排序是通過對整體的選擇。
Array.prototype.selectionSort = function() {undefined
var i, j, min;
var temp;
for (i = 0; i < this.length - 1; i++) {undefined
min = i;
for (j = i + 1; j < this.length; j++)
if (this[min] > this[j])
min = j;
temp = this[min];
this[min] = this[i];
this[i] = temp;
}
return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定義壹個數組
num.selectionSort(); //數組定義選擇排序算法
插入排序（英語：Insertion Sort）是壹種簡單直觀的排序算法。它的 工作原理是通過構建有序序列，對於未排序數據， 在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常采用in-place排序 （即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反復把已排序元素逐步向後挪位， 為最新元素提供插入空間。
從第壹個元素開始，該元素可以認為已經被排序
取出下壹個元素，在已經排序的元素序列中從後向前掃描
如果該元素（已排序）大於新元素，將該元素移到下壹位置
將新元素插入到該位置後
Array.prototype.insertionSort = function () {undefined
for (var i = 1; i < this.length; i++) {undefined
var temp = this[i];
var j = i - 1;
//如果將賦值放到下壹行的for循環內, 會導致在第13行出現j未聲明的錯誤
for (; j >= 0 && this[j] > temp; j–) {undefined
this[j + 1] = this[j];
}
this[j + 1] = temp;
}
return this;
}
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定義壹個數組
num.insertionSort(); //數組調用插入排序算法
快速排序
快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort）， 壹種排序算法， 最早由東尼·霍爾提出。在平均狀況下，排序n個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較， 但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n)演算法更快， 因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。 快速排序使用分治法（Divide and conquer）策略來把壹個序列（list）分為兩個子序列（sub-lists）。
步驟為：
從數列中挑出壹個元素，稱為"基準"（pivot），
重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（相同的數可以到任壹邊）。在這個分割結束之後，該基準就處於數列的中間位置。這個稱為分割（partition）操作。
遞歸地（recursively）把小於基準值元素的子數列和大於基準值元素的子數列排序。
遞歸到最底部時，數列的大小是零或壹，也就是已經排序好了。這個演算法壹定會結束，因為在每次的叠代（iteration）中，它至少會把壹個元素擺到它最後的位置去。
Array.prototype.quickSort = function () {undefined
var len = this.length;
if (len <= 1)
return this.slice(0);
var left = [];
var right = [];
var mid = [this[0]];
for (var i = 1; i < len; i++)
if (this[i] < mid[0])
left.push(this[i]);
else
right.push(this[i]);
return left.quickSort().concat(mid.concat(right.quickSort()));
};
var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quickSort();
編碼實戰
擴展思考
各種排序算法的時間復雜度和空間復雜度
算法優劣評價術語
穩定性:
穩定：如果 a 原本在 b 前面，而 a = b，排序之後 a 仍然在 b 的前面；
不穩定：如果 a 原本在 b 的前面，而 a = b，排序之後 a 可能會出現在 b 的後面；
排序方式:
內排序：所有排序操作都在內存中完成，占用常數內存，不占用額外內存。
外排序：由於數據太大，因此把數據放在磁盤中，而排序通過磁盤和內存的數據傳輸才能進行，占用額外內存。
復雜度:
時間復雜度: 壹個算法執行所耗費的時間。
空間復雜度: 運行完壹個程序所需內存的大小。