排序幾乎是每個程序員都會用到的知識點,今天簡單總結記錄一下常見的排序算法。
一、冒泡排序
冒泡排序思路非常直觀:不停對數組進行兩兩比較,把較大(或較小)的一項往前面放。以 var arr = [7, 3, 10, 1, 8, 4, 2, 4, 4, 3] 升序排列為例:
第一次 [3, 7, 1, 8, 4, 2, 4, 4, 3, 10]
第二次 [3, 1, 7, 4, 2, 4, 4, 3, 8, 10]
以此類推……
結果 [1, 2, 3, 3, 4, 4, 4, 7, 8, 10]。
// 冒泡排序
function bubbleSort(arr){
var len = arr.length, t;
for(j=0; j<=len-1; j++){
for(i=0; i<=len-j-1; i++){
if(arr[i] > arr[i+1]){
t = arr[i+1];
arr[i+1] = arr[i];
arr[i] = t;
}
}
}
return arr;
}
二、快速排序
快速排序核心步驟:
1. 選擇中間數。
2. 構建兩個臨時數組,比中間數小的放左邊,大的放右邊。
3. 對臨時數組重復 1-2。
例如原始數組 [2,4,1,5,6,3,12,9,7],第一步選第 5 項 6 為中間數,創建 left、right,left 結果為 [2,4,1,5,3],right 結果為 [12,9,7],再分別對 left 和 right 做相同操作,直到長度為 1。
// 快速排序
function quickSort(arr){
if(arr.length <= 1){ // 長度為 1 時停止遞歸
return arr;
}
var l = Math.floor(arr.length/2); // 選擇中間數
var left = [], right = [];
var splitEle = arr.splice(l, 1)[0]; // 將中間數從原數組刪除並保存
for(i=0; i<arr.length; i++){
if(arr[i] < splitEle){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return arguments.callee(left).concat(splitEle, arguments.callee(right));
}
三、選擇排序
升序排列時,假設第一項為最小值,把它與其他項分別比較,若其他項更小則交換位置,這樣第一輪結束後第一項即為最小值,然後對第二項做類似操作,以此類推。

// 選擇排序
function selectQuot(arr){
for(i=0; i<arr.length-1; i++){
for(j=i+1; j<arr.length; j++){
if(arr[i] > arr[j]){
var temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
四、插入排序
插入排序很好理解:先取出第一項放入一個虛構數組,再取第二項,若比第一項小則放前面,否則放後面;接著取第三項,與前兩項分別比較……有點像打撲克牌。以 [2, 4, 1, 5, 3, 8, 7, 9, 6] 為例,虛擬數組依次變成 [2]、[2,4]、[1,2,4]……以此類推。實際編程中並不需要單獨創建數組。
// 插入排序
function insertSort(arr){
for(i=1; i<arr.length; i++){
var temp = arr[i], j = i - 1;
while(j>=0 && temp < arr[j]){
arr[j+1] = arr[j]; // 相當於把虛擬數組當前項後移一位
j--;
}
arr[j+1] = temp; // 新加項最終插入的位置
}
return arr;
}
五、希爾排序
希爾排序是插入排序的升級版,又稱縮小增量排序。對於插入排序,若數據本就有序則無需移動,基於此,希爾排序先把數組按一定間隔分成若干小組分別插入排序,然後逐漸減小間隔直至為 1,最後一次(間隔為 1)處理時數組已基本有序,從而提高效率。
原始數組 [3, 4, 6, 5, 1, 9, 6, 10, 8, 8],假設增量為 3:

// 希爾排序
function shellSort(array){
var len = array.length;
var gap = len;
do {
gap = Math.floor(gap/3)+1; // 減小增量
// 把距離為 gap 的元素編為一組,掃描所有組
for (var i = gap; i < len; i++){
var temp = array[i], j = i - gap;
while(j>=0 && temp < array[j]){
array[j + gap] = array[j];
j -= gap;
}
array[j+gap] = temp;
}
}while(gap > 1)
return array;
}
六、歸並排序
歸並排序核心思想:先把數組分成若干子數組並各自變成有序數組,再合併這些有序數組。

var mergeSort = {
splitArr: function(arr){
if(arr.length == 1) return arr;
var mid = Math.floor(arr.length/2),
left = arr.slice(0, mid),
right = arr.slice(mid);
return this.merge(this.splitArr(left), this.splitArr(right));
},
merge: function(left, right){
var result = [];
while(left.length > 0 && right.length > 0){
if(left[0] < right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}
}