React寫多了，干啥都想用函數(shù)式粗仓，結(jié)果導(dǎo)致看快排看了一天還沒弄清楚，最后原來(lái)不是生成新數(shù)組设捐，是在原數(shù)組上進(jìn)行排序敖枳恰！Ｂ苷小蚂斤！這樣還省了空間，天哪真是越來(lái)越蠢了
閑話不多說(shuō)槐沼，先上代碼
function quickSort(array) {
quick(array, 0, array.length - 1);
}
function quick(array, left, right) {
// 對(duì)數(shù)組長(zhǎng)度為1的情況不作處理曙蒸，減小時(shí)間
if (array.length > 1) {
// 對(duì)數(shù)組進(jìn)行二分處理，并且返回剛才算出的中間值岗钩，因?yàn)橹虚g值之前的肯定比中間值要小
const pivot = partition(array, left, right);
if (left < pivot - 1) {
quick(array, left, pivot - 1);
}
if (right > pivot) {
quick(array, pivot, right);
}
}
}
function partition(array, left, right) {
const pivot = array[Math.floor((left + right) / 2))];
let iL = left;
let iR = right;
while (iL <= iR) {
while(array[iL] < pivot) iL++;
while(array[iR] > pivot) iR--;
if (iL < iR) {
// 交換順序纽窟，就不寫了很簡(jiǎn)單
swap(array, iL, iR);
iL++;
iR++;
}
}
// 把上次計(jì)算的位置返回，用于做下次計(jì)算的分隔
return iL;
}
快排比起歸并排序稍微難理解一點(diǎn)
歸并排序?qū)嵸|(zhì)就是一個(gè)簡(jiǎn)單的遞歸兼吓，一個(gè)遞歸的方法將數(shù)組切成兩半臂港，切到一個(gè)元素為止，另外一個(gè)函數(shù)不斷的合并排好序的數(shù)組视搏，最終合并好审孽，因?yàn)槭怯行驍?shù)組，所以合并的會(huì)更快浑娜。
所以歸并排序的精髓就是把兩個(gè)小有序數(shù)組合成一個(gè)有序的大數(shù)組
快排實(shí)質(zhì)是二分的策略佑力，把數(shù)組根據(jù)一個(gè)中間值分隔成兩份，中間值左邊都比他小筋遭，右邊都比他大打颤，然后把中間值的位置返回暴拄，下一次對(duì)中間值的左邊和右邊的數(shù)組分別計(jì)算，直到數(shù)組長(zhǎng)度為1時(shí)就不進(jìn)行了瘸洛。
做一次簡(jiǎn)單的分析
[ 3, 6, 4, 5, 2, 1]
中間值pivot是 Math.floor((0 + 5)/ 2, 10) = 2揍移，就是array[2] = 4
| 值 | 步驟 |
|---|---|
| pivot | 中間值等于4 |
| i=0 | 第一步 array[i] = 3 i < pivot 前進(jìn) |
| i=1 | 第二步 array[i] = 6 i > pivot 停止 |
| j=5 | 第三步 array[j] = 1 j < pivot 停止 |
| 交換 | 第四步 數(shù)組變?yōu)?code>[3, 1, 4, 5, 2, 6]i, j 分別前進(jìn) |
| i=2 | 第五步 array[i] = 4 i = pivot 停止 |
| j=4 | 第六步 array[j] = 2 j < pivot 停止 |
| 交換 | 第七步 數(shù)組變?yōu)?code>[3, 1, 2, 5, 4, 6] i, j 分別前進(jìn) |
| i=3 | 第八步 array[i] = 5 停止 |
| j=3 | 第九步 array[j] = 5 停止 |
第一次分隔完畢，返回中間值位置為4
以此類推
image.png
