- 相關推薦
JavaScript快速排序實現實例教程
目前最常見的排序算法大概有七八種，理解和掌握各種排序算法似乎是一個合格的程序員所必須要掌握的。今天想要和大家分享快速排序算法的Javascript的實現。
快速排序(Quicksort),又稱為 劃分交換排序(partition-exchange sort)，最早是由東尼·霍爾提出的。
基本思想
快速排序使用 分治法(Divide and conquer)策略(即分而治之，各個擊破)把一個序列(list)分為兩個子序列(sub-lists)。其基本步驟如下:
從數列中挑出一個元素，稱為 基準(pivot)。
重新排序數列，所有小于基準的元素，都移到基準的左邊;所有大于基準的元素都移到基準的右邊。這個分區結束之后，該基準處于數列的中間位置，稱為 分區(partition)操作。
對基準左邊和右邊的兩個子集，進行遞歸操作，即不斷重復第一步和第二步。直到所有子集只剩下一個元素為止。
示例說明
下面我們舉個示例進行排序說明，數列為[8,7,0,7,5,2,5,3,1]。
第一步: 基準值選取。基準值可以任意選取，便于理解，這里我們選擇中間值5作為基準。
[8,7,0,7, 5, 2,5,3,1]
第二步: 進行分區操作。按照順序將每個元素與基準進行比較，想成兩個子集，大于5與小于5.
[0,2,5,3,1, 5, 8,7,7]
第三步，遞歸操作。對兩個子集不斷重復第一步和第二步，直到所有子集只剩下一個元素為止。
[0,2, 5, 3,1] 5 [8, 7, 7][0,2,3,1, 5 ] 5 [7, 7, 8][0, 2, 3,1]5,5,7, 7, 8[0,1, 2, 3] 5, 5, 7, 7, 8[0,1,2,3,5,5,7,7,8]
Javascript的實現
講述了快速排序的基本思想，下面就讓我們使用代碼對其進行實現吧~
第一步: 定義函數quicksort,參數為一個數組。
var quicksort = function(arr){
};
第二步: 檢查數組個數，小于等于1，則返回。
var quicksort = function(arr){ if(arr.length <= 1){ return arr;
}
};
第三步: 進行基準選擇，定義兩個空數組進行左右兩個子集元素的存放。
var quicksort = function(arr){ if(arr.length <= 1){ return arr;
} var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex,1)[0]; var left = []; var right = []; for(var i = 0;i < arr.length;i++){ if(arr[i] < pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
};
第四步: 遞歸操作。對兩個子集不斷重復第一步和第二步，直到所有子集只剩下一個元素為止。
var quicksort = function(arr){ if(arr.length <= 1){ return arr;
} var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex,1)[0]; var left = []; var right = []; for(var i = 0;i < arr.length;i++){ if(arr[i] < pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
} return quicksort(left).concat([pivot],quicksort(right));
};
第五步: quicksort函數的調用
這里可以直接定義一個數組，對函數進行調用即可。
var quicksort = function(arr){ if(arr.length <= 1){ return arr;
} var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex,1)[0]; var left = []; var right = []; for(var i = 0;i < arr.length;i++){ if(arr[i] < pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
} return quicksort(left).concat([pivot],quicksort(right));
};var array = [8,7,0,7,5,2,5,3,1];
quicksort(array); //[0,1,2,3,5,5,7,7,8]
小結
快速排序的基本思想還是比較簡單的，巧用了分治法策略 ~。
【JavaScript快速排序實現實例教程】相關文章：
深入理解JS實現快速排序和去重javascript技巧10-28
Javascript實例教程08-10
Javascript實例教程如何使用HoTMetal06-12
堆的javascript實現方法10-02
Javascript 繼承實現例子參考08-23
用Javascript進行簡單的Table點擊排序08-29
使用JavaScript實現Java的List功能10-26
JavaScript實現網頁刷新代碼段08-07
javascript實現貪吃蛇代碼08-20