快速排序
快速排序是冒泡排序的優(yōu)化嚣伐，與冒泡排序不同的是，使用了分治法萍丐，進(jìn)行優(yōu)化轩端。會(huì)隨機(jī)選取一個(gè)值pivot（基準(zhǔn)元素），與其它值進(jìn)行比較逝变，將小于這個(gè)值的值全部放到一邊基茵，大于這個(gè)值的值放到另一邊奋构。然后再對兩邊的序列區(qū)間重復(fù)進(jìn)行此操作，直至成為有序隊(duì)列為止拱层。
- 時(shí)間復(fù)雜度為：nlogn
- 空間復(fù)雜度為：logn
- 是不穩(wěn)定的排序方法
快排的實(shí)現(xiàn)
單邊循環(huán)法
比如對于初始序列：[8, 9, 6, 3, 2, 7]
實(shí)現(xiàn)過程思路：
- 使用一個(gè)mark指針弥臼，用來表示小于基準(zhǔn)元素的區(qū)域邊界，初始時(shí)根灯，指向pivot（基準(zhǔn)元素径缅，一般我們可以取第1位），也就是mark指向8烙肺，[8(mark), 9, 6, 3, 2, 7]
- 從基準(zhǔn)元素下一位x開始遍歷纳猪，如果x > pivot，也就是9 > 8茬高，不做任何操作兆旬，，[8(mark), 9(x), 6, 3, 2, 7]怎栽，繼續(xù)遍歷
- 遍歷的下一位, [8(mark), 9, 6(x), 3, 2, 7]丽猬，此時(shí)6 < 8，代表著這個(gè)數(shù)要移動(dòng)到pivot的左側(cè)熏瞄，所以此時(shí)mark往右移一位脚祟，用來放置這個(gè)數(shù)，然后x和mark指向的數(shù)進(jìn)行位置交換强饮，也就是6和9交換由桌，得到[8, 6(mark), 9(x), 3, 2, 7]
- 繼續(xù)[8, 6(mark), 9, 3(x), 2, 7]，x = 3邮丰，x < pivot行您，mark向右移一位指向9，3和mark指向的數(shù)9交換剪廉，交換后得到 [8, 6, 3(mark), 9(x), 2, 7]
- 繼續(xù)娃循，[8, 6, 3(mark), 9, 2(x), 7], x = 2, 2 < 8，mark+1指向9斗蒋，9與2交換捌斧，得到[8, 6, 3, 2(mark), 9(x), 7]
- 繼續(xù)[8, 6, 3, 2(mark), 9, 7(x)]，7 < 8泉沾，mark+1指向9捞蚂，9與7交換，得到[8(pivot), 6, 3, 2, 7(mark), 9(x)]跷究，此時(shí)x已是遍歷的最后一位姓迅，所以這時(shí)將pivot與mark位置進(jìn)行交換, [7, 6, 3, 2, 8, 9]，這樣就完成了第一輪的快排，此時(shí)8左邊的數(shù)都是小于8的队贱，右邊的數(shù)都是大于8的
- 再遞歸對8左右兩邊序列[7,6,3,2]色冀、[9]進(jìn)行1-6步驟進(jìn)行快速，直至成為整個(gè)數(shù)組變成有序隊(duì)列
/*
* 快速排序
* 單邊循環(huán)法的遞歸實(shí)現(xiàn)
*/
function singleQuickSort(arr, startIndex, endIndex) {
// 健壯性判斷
if(!Array.isArray(arr)) throw new Error("請輸入一個(gè)數(shù)組")
if(!arr.length) return []
if(startIndex >= endIndex) return;
// 基準(zhǔn)元素
let pivot = arr[startIndex];
// 標(biāo)記指針,用于表示小于基準(zhǔn)元素的區(qū)域邊界
let mark = startIndex;
for(let i = startIndex + 1; i <= endIndex; i++) {
if(arr[i] < pivot) {
mark++;
[ arr[mark], arr[i] ] = [ arr[i], arr[mark] ]
}
}
[ arr[startIndex], arr[mark] ] = [ arr[mark], arr[startIndex] ]
singleQuickSort(arr, startIndex, mark - 1)
singleQuickSort(arr, mark + 1, endIndex)
return arr
}
const arr = singleQuickSort([8, 9, 6, 3, 2, 7], 0, 5)
console.log(arr) // [ 2, 3, 6, 7, 8, 9 ]
雙邊循環(huán)法
雙邊循環(huán)法柱嫌，顧名思義锋恬，就是用雙指針的方法來遍歷元素
實(shí)現(xiàn)過程：
如：[8, 2, 6, 3, 9, 7]
- 假如隨機(jī)值定基準(zhǔn)元素pivot為第一個(gè)數(shù)8，定義一個(gè)左指針（指向第一個(gè)數(shù)）编丘，和一個(gè)右指針（指向最后一個(gè)）与学，則8先與最后一個(gè)值進(jìn)行比較，8比7大嘉抓，所以兩值交換位置[7, 2, 6, 3, 9, 8]
- 此時(shí)左指針往右移一位索守，2與8比，2比8小抑片，位置不變卵佛，左指針繼續(xù)往右移動(dòng)一位
- 此時(shí)左指針往右移一位，6與8比敞斋，6比8小截汪，位置不變，左指針繼續(xù)往右移動(dòng)一位
- 3和8比植捎，左指針繼續(xù)往右移動(dòng)一位
- 9和8比衙解，交換位置[7, 2, 6, 3, 8, 9]，此時(shí)左指針不變焰枢，右指針向左移一位蚓峦，至此左右指針相同，第一輪比較結(jié)束济锄，注意暑椰，結(jié)束的條件是左指針位置大于等于右指針；比8小的數(shù)都在8的左邊荐绝，比8大的數(shù)都在8的右邊
- 對左邊[7, 2, 6, 3]和右邊的序列[9]分別再重復(fù)1-4步一汽，直至都成為有序序列
/*
* 快速排序
* 雙邊循環(huán)法的遞歸實(shí)現(xiàn)
*/
function doubleQuickSort(arr, startIndex, endIndex) {
// 健壯性判斷
if(!Array.isArray(arr)) throw new Error("請輸入一個(gè)數(shù)組")
if(!arr.length) return []
if(startIndex >= endIndex) return arr;
// 基準(zhǔn)元素
const pivot = arr[startIndex]
// 左指針
let left = startIndex
// 右指針
let right = endIndex
// 只要左右指針不重合，就會(huì)繼續(xù)循環(huán)
while(left != right) {
// 從最右邊開始比較很泊，如果right元素大于基準(zhǔn)元素，則右指針向左移一位
while(left < right && pivot <= arr[right]) {
right--;
}
// 如果右邊元素小于基準(zhǔn)元素沾谓，則交換位置委造，然后左指針向右移一位
if(arr[right] < pivot) {
[ arr[left], arr[right] ] = [ arr[right], arr[left] ]
left++;
}
// 然后開始比較基準(zhǔn)元素和左邊元素，如果左邊元素小于基準(zhǔn)元素均驶，左指針向右移一位
while(left < right && pivot >= arr[left]) {
left++;
}
// 如果左邊元素大于基準(zhǔn)元素昏兆，則交換位置，然后右指針向左移一位
if(arr[left] > pivot) {
[ arr[left], arr[right] ] = [ arr[right], arr[left] ]
right--;
}
}
// 當(dāng)left===right時(shí)妇穴，就是基準(zhǔn)元素所在的最終位置,此時(shí) arr[left] === arr[right] === pivot;
// 遞歸遍歷左邊和右邊的無序隊(duì)列
doubleQuickSort(arr, startIndex, left-1)
doubleQuickSort(arr, left + 1, endIndex)
return arr;
}
const arr2 = doubleQuickSort([8, 9, 6, 3, 2, 7], 0, 5)
console.log(arr2) // [ 2, 3, 6, 7, 8, 9 ]
排序算法系列文章傳送門(未完爬虱，持續(xù)更新中)：
排序算法-1（javascript） 冒泡隶债、選擇、插入跑筝、希爾排序的實(shí)現(xiàn)
排序算法-2（javascript） 快速排序的實(shí)現(xiàn)
排序算法-3（javascript） 堆排序的實(shí)現(xiàn)
排序算法-4（javascript） 歸并排序的實(shí)現(xiàn)
