javascript實(shí)現(xiàn)快速排序算法:
快速排序基本思想:
使用分治法策略來把一個(gè)序列分為兩個(gè)子序列
步驟為：
1.從數(shù)列中挑出一個(gè)元素,稱為"基準(zhǔn)"(pivot),一般選用最右邊元素為基準(zhǔn)元素.
2.重新排序數(shù)列,所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面检访，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）始鱼。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置脆贵。這個(gè)稱為分區(qū)(partition)操作医清。
3.遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
4.遞歸到最底部時(shí),數(shù)列的大小是零或一,也就是已經(jīng)排序好了卖氨。這個(gè)算法一定會(huì)結(jié)束,因?yàn)樵诿看蔚牡谢崂樱辽贂?huì)把一個(gè)元素?cái)[到它最后的位置去。
在平均狀況下筒捺，排序n個(gè)項(xiàng)目要O(nlogn)次比較柏腻。在最壞狀況下則需要O(n^2)次比較,但這種狀況并不常見
function quickSort(array) {
// 交換元素位置
function swap(array, i, k) {
var temp = array[i];
array[i] = array[k];
array[k] = temp;
}
// 數(shù)組分區(qū)，左小右大
function partition(array, left, right) {
var storeIndex = left;
var pivot = array[right]; // 直接選最右邊的元素為基準(zhǔn)元素
for (var i = left; i < right; i++) {
if (array[i] < pivot) {
swap(array, storeIndex, i);
storeIndex++; // 交換位置后系吭，storeIndex 自增 1五嫂，代表下一個(gè)可能要交換的位置
}
}
swap(array, right, storeIndex); // 最后將基準(zhǔn)元素放置正確位置上
return storeIndex;
}
function sort(array, left, right) {
console.log("原始left="+left+"---原始right="+right);
if (left > right) {
return;
}
var storeIndex = partition(array, left, right);
//基準(zhǔn)元素左邊排序
sort(array, left, storeIndex - 1);
//基準(zhǔn)元素右邊排序
sort(array, storeIndex + 1, right);
}
sort(array, 0, array.length - 1);
return array;
}
var arr=[3,7,8,5,2,1,9,5,4];
console.log(quickSort(arr));
步驟詳解:
原始順序: 3 7 8 5 2 1 9 5 4
說明: 序列一與序列二獨(dú)立運(yùn)行
pivot=4(最右邊的元素為基準(zhǔn)元素)
storeIndex=1; i=4時(shí)
3 2 8 5 7 1 9 5 4
stroeIndex=2; i=5時(shí)
3 2 1 5 7 8 9 5 4
stroeIndex=3; i=8時(shí)循環(huán)結(jié)束
交換 array[8]與array[3]值
3 2 1 4 7 8 9 5 5
返回stroeIndex=3
序列一(基準(zhǔn)元素左邊):
sort(array, 0,2)
left=0; right=2;
partition(array,0,2); 此時(shí) pivot=1
stroeIndex=0；i=2時(shí)跳出循環(huán)
交換 array[2]與array[0]值
1 2 3 4 7 8 9 5 5
返回stroeIndex=0
sort(array, 0,2)此函數(shù)結(jié)束
序列二(基準(zhǔn)元素左邊):
sort(array, 4,8)
partition(array,4,8); 此時(shí) pivot=5
stroeIndex=4肯尺；i=8是循環(huán)結(jié)束
交換 array[8]與array[4]值
1 2 3 4 5 8 9 5 7
返回stroeIndex=4
sort(array,5,8)
partition(array,5,8); 此時(shí) pivot=7
stroeIndex=5; i=7時(shí)
1 2 3 4 5 5 9 8 7
stroeIndex=6沃缘；i=8循環(huán)結(jié)束
交換 array[8]與array[6]值
1 2 3 4 5 5 7 8 9
返回stroeIndex=6
sort(array,7,8)
sort(array,8,8)
sort(array,9,8)此函數(shù)結(jié)束
返回最終結(jié)果: array
1 2 3 4 5 5 9 8 7
