快速排序 golang
快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），簡稱快排，一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序 個項目要（大O符号）次比較。在最壞狀況下則需要次比較，但這種狀況并不常見。
快排應用
- 快排是一般語言内置排序包中的實作，當然在數組大小不同的情況下會有不同的選擇，但是整體以快排為主，為了防止出現一般采用随機選擇中間節點的方式來實作。
- 作為算法題，要求實作。
分治法
分而治之，先将原問題的規模下降，分解為子問題，此所謂“分”，然後解決子問題，此為“治”。
分治法的基本思想是将一個規模為n的原問題分解為k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然後将子問題的解合并為原問題的解。
算法描述
步驟為：
- 從數列中挑出一個元素，稱為”基準”（pivot），
- 重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（相同的數可以到任何一邊）。在這個分區結束之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
- 遞歸地（recursively）把小于基準值元素的子數列和大于基準值元素的子數列排序。
遞歸到最底部時，數列的大小是零或一，也就是已經排序好了。這個算法一定會結束，因為在每次的疊代（iteration）中，它至少會把一個元素擺到它最後的位置去。
一般采用的都是原地排序版本，這樣不需要配置設定額外的空間，對速度有提升。
僞代碼如下：
procedure quicksort(a, left, right)
if right > left
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
quicksort(a, left, pivotNewIndex-1)
quicksort(a, pivotNewIndex+1, right)
實作
單路快排
遞歸版本實作
- 首先通過随機數選取比較的點
- 周遊 head + 1-> tail
- 大于mid 則和tail交換 并且tail–
- 小于等于 則交換head 并且head++ i++
疑問：
- 為什麼在大于的情況下 index i 沒有移位？
因為交換後的tail，并沒有保證一定會大于mid元素，是以需要再次進行比較
- 為什麼在小于的情況下 index i 需要移位？
因為第一次交換的時候是arr[0] -> mid，是以交換後一定滿足arr[i] <= mid，是以可以移位操作。否則周遊無法結束
func QSortRecursion(arr []int){
arrLen := len(arr)
if arrLen <= 1{
return
}
randNum := getRandNum(arrLen -1)
arr[randNum], arr[0] = arr[0],arr[randNum]
mid := arr[0]//取出用于比較的元素
head, tail := 0, arrLen -1
for i := 1; i <= tail;{// 從 head + 1 到 tail 周遊 case 大于比較元素 換 else 小于等于 換 并且head++ 維護左邊的數組
if arr[i] > mid{
arr[i], arr[tail] = arr[tail], arr[i]
tail--
}else{
arr[i], arr[head] = arr[head], arr[i]
head++
i++
}
}
QSortRecursion(arr[:head])
QSortRecursion(arr[head+1:])
}
func getRandNum(totalNum int)int{
rand.Seed(time.Now().Unix())// 設定随機種子
return rand.Intn(totalNum)
}
雙路快排
上面的實作方法是單路快排，常用的我們會用雙路快排的方式，更加快。
可以看到當資料比較多重複的時候，單路快排會有非常備援的swap操作，雙路快排避免了這一點。
/*
雙路快排
從左向右找到大于pivot的元素
從右向左找小于pivot的元素
判斷是否越界 交換元素 head++ tail--
*/
func QSortTwoWay(arr []int){
arrLen := len(arr)
if arrLen <= 1{
return
}
randNum := getRandNum(arrLen -1)
arr[randNum], arr[0] = arr[0],arr[randNum]
mid := arr[0]//取出用于比較的元素
head, tail := 0, arrLen -1
for {
for head <= tail && arr[head] < mid{
head ++
}
for tail > head && arr[tail] > mid{
tail --
}
if head > tail{
break
}
swap(arr, head,tail)
head++
tail--
}
QSortTwoWay(arr[:head])
QSortTwoWay(arr[head+1:])
}
三路快排
當遇到非常多重複元素的時候，會使用三路快排的方式解決。
三路快排複雜的地方就在于對指定的變量的描述以及邊界問題上。
由于時間關系暫時來一版c語言實作 詳細資訊情況下文參看連結
private void quickSort(int[] a, int left, int right) {
if (right <= left)
return;
/*
* 工作指針
* p指向序列左邊等于pivot元素的位置
* q指向序列右邊等于Pivot元素的位置
* i指向從左向右掃面時的元素
* j指向從右向左掃描時的元素
*/
int p, q, i, j;
int pivot;// 錨點
i = p = left;
j = q = right - 1;
/*
* 每次總是取序列最右邊的元素為錨點
*/
pivot = a[right];
while (true) {
/*
* 工作指針i從右向左不斷掃描，找小于或者等于錨點元素的元素
*/
while (i < right && a[i] <= pivot) {
/*
* 找到與錨點元素相等的元素将其交換到p所訓示的位置
*/
if (a[i] == pivot) {
swap(a, i, p);
p++;
}
i++;
}
/*
* 工作指針j從左向右不斷掃描，找大于或者等于錨點元素的元素
*/
while (left <= j && a[j] >= pivot) {
/*
* 找到與錨點元素相等的元素将其交換到q所訓示的位置
*/
if (a[j] == pivot) {
swap(a, j, q);
q--;
}
j--;
}
/*
* 如果兩個工作指針i j相遇則一趟周遊結束
*/
if (i >= j)
break;
/*
* 将左邊大于pivot的元素與右邊小于pivot元素進行交換
*/
swap(a, i, j);
i++;
j--;
}
/*
* 因為工作指針i指向的是目前需要處理元素的下一個元素
* 故而需要退回到目前元素的實際位置，然後将等于pivot元素交換到序列中間
*/
i--;
p--;
while (p >= left) {
swap(a, i, p);
i--;
p--;
}
/*
* 因為工作指針j指向的是目前需要處理元素的上一個元素
* 故而需要退回到目前元素的實際位置，然後将等于pivot元素交換到序列中間
*/
j++;
q++;
while (q <= right) {
swap(a, j, q);
j++;
q++;
}
/*
* 遞歸周遊左右子序列
*/
quickSort(a, left, i);
quickSort(a, j, right);
}
參考:維基百科
三路快排