排序算法
定義
對一序列對象根據某個關鍵字進行排序
評判标準
- 穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面；
- 不穩定：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面；
- 内排序：所有排序操作都在記憶體中完成；
- 外排序：由于資料太大，是以把資料放在磁盤中，而排序通過磁盤和記憶體的資料傳輸才能進行；
- 時間複雜度：一個算法執行所耗費的時間；
- 空間複雜度：運作完一個程式所需記憶體的大小；
各種排序算法對比圖
這個圖是在網上找的咯
冒泡排序
算法描述
冒泡排序是一種簡單的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
算法步驟
1.比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
2.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數
3.針對所有的元素重複以上的步驟，除了最後一個；
4.重複步驟1~3，直到排序完成。
或者你願意從後面開始比較也是可以哒。
算法實作
var bubble = function (nums) {
var num = nums.length;
//現在沒有元素是确定有序的
var tail = num-;
while(tail>) {
//走一遍所有的無序元素，這裡面最大的會排到最後
//有序區就多增加了一個元素
for(var i = ;i < tail; i++){
if (nums[i]>nums[i+]) {
var temp = nums[i];
nums[i] = nums[i+];
nums[i+] = temp;
}
}
tail--;
}
return nums;
};
算法改進
最後進行交換的位置就是有序區的開始，tail變量每次可以使用這個來标記有序區的位置
var bubble = function (nums) {
var num = nums.length;
var tail = num-;
while(tail>) {
//記錄交換位置的臨時變量
var tempTail = ;
for(var i = ;i < tail; i++){
if (nums[i]>nums[i+]) {
tempTail = i;
var temp = nums[i];
nums[i] = nums[i+];
nums[i+] = temp;
}
}
//下次周遊周遊到這裡就可以了
tail = tempTail;
}
return nums;
};
選擇排序
由于其時間複雜度永遠為o(n2)，是以資料集越小用這個排序方法越好。
算法描述
先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
算法步驟
1.初始狀态：無序區為R[1..n]，有序區為空；
2.第i趟排序(i=1,2,3…n-1)開始時，目前有序區和無序區分别為R[1..i-1]和R(i..n）。該趟排序從目前無序區中-選出關鍵字最小的記錄 R[k]，将它與無序區的第1個記錄R交換，使R[1..i]和R[i+1..n)分别變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；
3.n-1趟結束，數組有序化了
算法實作
var choose = function (nums) {
var num = nums.length;
//目前無序區第一個數的下标
var tail = ;
var small = ;
var smallIndex = ;
while(tail<(num-)) {
//目前無序區最小的數
smallIndex = tail;
//目前無序區最小的數的下标
small = nums[smallIndex];
//尋找無序區中最小的數
for(var i = tail+;i<num;i++) {
if (nums[i]<small) {
smallIndex = i;
small = nums[i];
}
}
//把最小的數與目前無序區的第一個數交換
nums[smallIndex] = nums[tail];
nums[tail] = small;
tail++;
}
return nums;
};
插入排序
算法描述
對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。插入排序在實作上，通常采用in-place排序（即隻需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反複把已排序元素逐漸向後挪位，為最新元素提供插入空間。
算法步驟
1.從第一個元素開始，該元素可以認為已經被排序；
2.取出下一個元素，在已經排序的元素序列中從後向前掃描；
3.如果該元素（已排序）大于新元素，将該元素移到下一位置；
4.重複步驟3，直到找到已排序的元素小于或者等于新元素的位置；
5.将新元素插入到該位置後；
6.重複步驟2~5。
算法實作
var insert = function(nums) {
var num = nums.length;
for (var i = ; i < num; i++) {
//目前要向有序區插入的元素a
var numNow = nums[i];
//從後往前在有序區中尋找
//如果目前數比要插入的數大就把目前數往後挪
//如果等于或小于，就把要插入的放在目前數後面
//有個特殊情況要注意，就是沒有比目前數小的數，那目前數就要插在最前面
for(var j = i - ;j >= && numNow < nums[j];j --) {
nums[j+] = nums[j];
}
nums[j+] = numNow;
}
return nums;
}
希爾排序
1959年Shell發明，第一個突破O(n^2)的排序算法，是簡單插入排序的改進版，它與插入排序的不同之處在于，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。
希爾排序的核心在于間隔序列的設定。既可以提前設定好間隔序列，也可以動态的定義間隔序列。動态定義間隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。
算法描述
把記錄按步長gap分組，對每組記錄采用直接插入排序方法進行排序。随着步長逐漸減小，所分成的組包含的記錄越來越多，當步長的值減小到 1 時，整個資料合成為一組，構成一組有序記錄，則完成排序。
算法的關鍵是步長gap的選擇，Donald Shell 最初建議步長選擇為N/2并且對步長取半直到步長達到1。雖然這樣取可以比O(N2)類的算法（插入排序）更好，但這樣仍然有減少平均時間和最差時間的餘地。可能希爾排序最重要的地方在于當用較小步長排序後，以前用的較大步長仍然是有序的。比如，如果一個數列以步長5進行了排序然後再以步長3進行排序，那麼該數列不僅是以步長3有序，而且是以步長5有序。如果不是這樣，那麼算法在疊代過程中會打亂以前的順序，那就不會以如此短的時間完成排序了。比較在希爾排序中是最主要的操作，而不是交換。
目前有這麼幾個步長序列：
- n/2i：最壞情況下複雜度O(n2)
- 2k-1：O(n3/2)
- 已知的最好步長序列是由Sedgewick提出的(1, 5, 19, 41, 109,…)
算法實作
這裡有兩種實作的辦法，差別在使用gap将數組分組後如何周遊。
比如我們有這麼一個數組：[1,2,3,4,5,6,7,8,9]，gap=3；
數組被分成了這樣[1,2,3],[4,5,6],[7,8,9]；
我們可以這樣周遊：4,5,6,7,8,9，然後分别和自己該比較的進行比較，比如9就要和6,3進行比較。我們暫且稱為按照自然組周遊：
function shellSort(list) {
var gap = parseInt(list.length / );
while ( <= gap) {
//從第2個自然組開始周遊數組
for (var i = gap; i < list.length; i++) {
var j = ;
var temp = list[i];
//向前對距離自己為gap的元素組進行插入排序
for (j = i - gap; j >= && temp < list[j]; j = j - gap) {
list[j + gap] = list[j];
}
list[j + gap] = temp;
}
gap = parseInt(gap / ); // 減小增量
}
return list;
}
分組：[1,2,3],[4,5,6],[7,8,9]；
我們還可以按照排序組周遊：4,7、5,8、6,9，比較還是一樣的。
var shellSort = function(nums) {
var num = nums.length;
var gap = parseInt(num/);
while (gap>=) {
//從第1個自然組中，周遊每個排序組的第1個元素
for (var i = gap - ; i >= ; i--) {
//目前排序組的第1個元素的位置記錄
var lowBound = i;
//從目前排序組的第2個元素開始進行排序
var index = i + gap;
//周遊排序組，進行插入排序
while (index<num) {
var now = nums[index];
for (var j = index - gap; j >= lowBound && now < nums[j];j -= gap) {
nums[j+gap] = nums[j];
}
nums[j+gap] = now;
index += gap;
}
}
//gap減半
gap = parseInt(gap/);
}
return nums;
}
歸并排序
和選擇排序一樣，歸并排序的性能不受輸入資料的影響，但表現比選擇排序好的多，因為始終都是O(n log n）的時間複雜度。代價是需要額外的記憶體空間。
算法描述
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。歸并排序是一種穩定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為2-路歸并。
我們可以遞歸，也可以疊代，核心思想是一樣的
算法步驟
1.将數組分為單個元素的塊
2.将相鄰兩個塊的元素逐一比較，組成一個新的塊，這個塊是有序的
3.重複2，直到隻剩一個塊
算法實作
剛才我們提到有兩種實作方式。
疊代：
var margeIteration = function(nums) {
var temp = [];
var num = nums.length;
//每個元素是一個塊
var block = ;
var start;
//如果整個數組還不是一個塊
while (block<=num) {
//循環取相鄰兩個塊
for (start = ;start<num;start+=*block) {
var low = start;
var mid = Math.min(start + block,num);
var high = Math.min(start + * block,num);
//塊1的起始和結束
var start1 = low;
var end1 = mid;
//塊2的起始和結束
var start2 = mid;
var end2 = high;
//比較兩個塊，使得新的塊有序
while (start1 < end1 && start2 < end2) {
temp[low++] = nums[start1] < nums[start2] ? nums[start1++] : nums[start2++];
}
//到最後塊可能不一樣長
while(start1 < end1) {
temp[low++] = nums[start1++];
}
while(start2 < end2) {
temp[low++] = nums[start2++];
}
}
nums = temp;
temp = [];
block*=;
}
return nums;
}
遞歸：
var mergeRecursive = function(nums){
if (nums.length===)
return nums;
var mid = parseInt(nums.length/);
var left = mergeRecursive(nums.slice(,mid));
var right = mergeRecursive(nums.slice(mid));
var res = [];
var i = ;
var j = ;
var k = ;
while (i<left.length&&j<right.length)
res[k++] = left[i] < right[j] ? left[i++] : right[j++];
while (i<left.length)
res[k++] = left[i++];
while (j<right.length)
res[k++] = right[j++];
return res;
}
快速排序
快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高! 它是處理大資料最快的排序算法之一了。
算法描述
快速排序使用分治法來把一個串分為兩個子串。其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序。
算法步驟
1.從數列中挑出一個元素，稱為 “基準”（pivot）；
2.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
3.遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
算法實作
var fastSort = function(nums){
var fast = function (left,right) {
if (left>=right)
return;
//選最左邊的元素當基準
var stand = nums[left];
var low = left;
var high = right;
//把比基準小的數都放在基準左邊，大的放右邊
while (low<high) {
while (low<high&&nums[high]>=stand)
high--;
nums[low] = nums[high];
while (low<high&&nums[low]<=stand)
low++;
nums[high] = nums[low];
}
nums[high]=stand;
//基準不用動了，基準左右重複這個動作
fast(left,low-);
fast(low+,right);
};
fast(,nums.length-);
return nums;
}
堆排序
堆排序可以說是一種利用堆的概念來排序的選擇排序。
其中每個結點的關鍵字都不大于其孩子結點的關鍵字，這樣的堆稱為小根堆。
其中每個結點的關鍵字都不小于其孩子結點的關鍵字，這樣的堆稱為大根堆。
用一個數組來表示堆時，第0個元素是堆的根；
對于每一個節點R[i]，左孩子結點是：R[2*i+1]，右孩子結點是：R[2*i+2]， 父結點是：R[(i-1)/2]。
算法描述
根據初始數組去構造初始堆（建構一個完全二叉樹，保證所有的父結點都比它的孩子結點數值大）。
然後每次交換第一個和最後一個元素，輸出最後一個元素（最大值），然後把剩下元素重新調整為大根堆。
當輸出完最後一個元素後，這個數組已經是按照從小到大的順序排列了。
算法步驟
1.将初始待排序關鍵字序列(R1,R2….Rn)建構成大頂堆，此堆為初始的無序區；
2.将堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]；
3.由于交換後新的堆頂R[1]可能違反堆的性質，是以需要對目前無序區(R1,R2,……Rn-1)調整為新堆，然後再次将R[1]與無序區最後一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重複此過程直到有序區的元素個數為n-1，則整個排序過程完成。
算法實作
function heapSort(list) {
// 循環建立初始堆，從最後一個有孩子的節點開始
for (var i = parseInt((list.length-) / ); i >= ; i--) {
HeapAdjust(list, i, list.length);
}
// 進行n-1次循環，完成排序
for (var i = list.length - ; i > ; i--) {
// 最後一個元素和第一進制素進行交換
var temp = list[i];
list[i] = list[];
list[] = temp;
// 篩選 R[0] 結點，得到i-1個結點的堆
HeapAdjust(list, , i);
}
return list;
//這個方法接收一個堆，一個根節點，和堆的長度
//用于在以根節點為根的堆中調整堆，這個堆中應隻有根節點不符合要求
function HeapAdjust(array, parent, length) {
var temp = array[parent]; //儲存目前父節點
var child = * parent + ; //先獲得左孩子
while (child < length) {
// 如果有右孩子結點，并且右孩子結點的值大于左孩子結點，則選取右孩子結點
if (child + < length && array[child] < array[child + ]) child++;
// 如果父結點的值已經大于孩子結點的值，則直接結束
if (temp >= array[child]) break;
// 把孩子結點的值賦給父結點
array[parent] = array[child];
// 選取孩子結點的左孩子結點,繼續向下篩選
parent = child;
child = * child + ;
}
array[parent] = temp;
}
}
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)