都說(shuō)快排是個(gè)很偉大的排序算法,名如其名,速度很快,而且是原位排序.
快排的精髓就在于,從數(shù)組中找一個(gè)基準(zhǔn)點(diǎn)piovt(可以隨便找,也可以找第一個(gè)),然后將數(shù)組元素移動(dòng)分區(qū),左邊小于pivot,中間部分則是等于pivot,右邊一部分是大于pivot的,然后對(duì)于左右兩部分在進(jìn)行快排.
看上圖:
我們以首個(gè)元素為基準(zhǔn)點(diǎn),將元素分為小于 v ,等于 v , 大于 v 三個(gè)部分;而元素i則指向當(dāng)前進(jìn)行比較的元素, 區(qū)間 [l+1,lt]是小于v的元素,區(qū)間[lt+1,i-1]則表示的是等于v的元素,從最右邊的索引r處開始往內(nèi),形成的區(qū)間[gt,r]存放的是大于v的元素;
當(dāng)然一開始這些區(qū)間其實(shí)都是不存在的,我們需要確定邊界,i的開始索引指向l+1,lt的初始值是l,而gt的初始值則是r+1,表示的是這三個(gè)區(qū)間均為空;
-
當(dāng)排序開始時(shí)
- 如果當(dāng)前i 指向的元素 等于v,那很好,i+1;
- 如果當(dāng)前i 指向的元素 小于v,那么就將 lt+1 與索引 i處的值 進(jìn)行交換,
然后lt+1, 并且 i+1; - 如果當(dāng)前元素 大于 v,那么 就將 gt - 1 處的元素與 當(dāng)前元素 交換,然后gt-1.
- 最后當(dāng)i 走到 gt 處 即 gt==i 時(shí) ;那就說(shuō)明 除了第一個(gè)元素之外,其余的區(qū)間已經(jīng)分區(qū)完畢,只要將首個(gè)元素與 lt 處的元素進(jìn)行交換, 然后lt -1 ;我們就形成了想要的三個(gè)區(qū)間,小于v,等于v,然后是大于v的.
4.代碼編寫,首先是個(gè)交換函數(shù),用于交換兩個(gè)索引位置處的值
function swap(arr, a, b) {
let temp;
temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
5.然后就是根據(jù)上面邏輯編寫的分區(qū)函數(shù),這個(gè)函數(shù)應(yīng)當(dāng)返回,小于v,和大于v的元素的區(qū)間信息:
function partion(arr, l, r) {
//基準(zhǔn)數(shù)選取區(qū)間的第一個(gè)值
let v = arr[l];
let lt = l;
let gt = r + 1;
for (let i = l + 1; i < gt; ) {
if (arr[i] == v) {
i++;
} else if (arr[i] > v) {
swap(arr, gt - 1, i);
gt--;
} else {
swap(arr, lt + 1, i);
lt++;
i++;
}
}
swap(arr, l, lt);
lt--;
return { lt: lt, gt: gt };
}
6.最后就是我們快排函數(shù) , 明顯就是用遞歸了,將沒(méi)有大于v,和小于v區(qū)間的元素在進(jìn)行快排
function quicksort(arr, l, r) {
// 只有l(wèi)<r 才需要對(duì)元素進(jìn)行處理
if (l >= r) {
return;
}
let obj = partion(arr, l, r);
quicksort(arr, l, obj.lt);
quicksort(arr, obj.gt, r);
}
7.好了快排到此就實(shí)現(xiàn)了我們來(lái)編寫個(gè)測(cè)試用例 測(cè)試實(shí)現(xiàn)的這個(gè)快排 有多快
//生成一個(gè)近乎有序的數(shù)組
function randomNearlyOrderArray(count) {
let arr = [];
for (let i = 0; i < count; i++) {
arr[i] = Math.floor(Math.random() * 50 + 1);
}
return arr;
}
//測(cè)試數(shù)組是否已經(jīng)排序
function isSorted(arr) {
for (let i = 0; i + 2 < arr.length - 1; i++) {
if (
(arr[i] > arr[i + 1] && arr[i + 1] < arr[i + 2]) ||
(arr[i] < arr[i + 1] && arr[i + 1] > arr[i + 2])
) {
return false;
}
}
return true;
}
8.來(lái)看看 node.js 下的實(shí)驗(yàn)結(jié)果吧,
對(duì)于生成 10000000
我們的三路快排花費(fèi) 350 ms 左右
使用Array.prototype.sort 來(lái)對(duì)數(shù)組進(jìn)行排序
則 花費(fèi)了 3500 ms 左右
- 總結(jié),看來(lái) 我們的快排在處理 近乎有序 數(shù)組時(shí) 還是 效率挺高的 ,原因就是,多了個(gè) 等于元素v的區(qū)間,這部分的元素,在形成后,下次就不需要移動(dòng)了,所以效率會(huì)很高.
