快速排序--洛谷卡TLE後最終我還是選擇了三向切割

語言: CN / TW / HK

theme: cyanosis highlight: vs2015


小知識,大挑戰!本文正在參與“  程式設計師必備小知識  ”創作活動

寫在前邊

這篇文章呢,我們接著聊一下排序演算法,我們之前已經談到了簡單插入排序 和ta的優化版希爾排序 ,這節我們要接觸一個更“高階”的演算法了--快速排序。
在做洛谷的時候,遇到了一道卡優化的題,如果沒有去對快排進行優化的話,會有幾個點是TLE的,後邊我們可以圍繞這道題來做各種優化,先來認識一下快速排序。

思路

假如我們的計算機每秒鐘可以執行 10 億次,那麼對 1 億個數進行排序,排序只需要 0.1 秒,而冒泡排序則需要 1 千萬秒,達到 115 天之久,是不是很嚇人?那有沒有既不浪費空間又可以快一點的排序演算法呢?那就是“快速排序”! 假設我們現在對“ 6 1 2 7 9 3 4 5 10 8”這 10 個數進行排序。首先在這個序列中隨便找一個數作為基準數(不要被這個名詞嚇到了,這就是一個用來參照的數,待會兒你就知道它用來做啥了)。為了方便,就讓第一個數 6 作為基準數吧。接下來,需要將這個序列中所有比基準數大的數放在 6 的右邊,比基準數小的數放在 6 的左邊,類似下面這種排列。

3 1 2 5 4 6 9 7 10 8

在初始狀態下,數字 6 在序列的第 1 位。我們的目標是將 6 挪到序列中間的某個位置,假設這個位置是 k。現在就需要尋找這個 k,並且以第 k 位為分界點,左邊的數都小於等於 6,右邊的數都大於等於 6。 ​

方法其實很簡單:分別從初始序列“ 6 1 2 7 9 3 4 5 10 8”兩端開始“探測”。先從右往左找一個小於 6 的數,再從左往右找一個大於 6 的數,然後交換它們。這裡可以用兩個變數 i 和 j,分別指向序列最左邊和最右邊。我們為這兩個變數起個好聽的名字“哨兵 i”和“哨兵 j”。剛開始的時候讓哨兵 i 指向序列的最左邊(即 i=1),指向數字 6。讓哨兵 j 指向序列的最右邊(即 j=10),指向數字 8。
image.png image.png image.png

圖源: 《啊哈演算法》

完整流程圖

image.png

如果mid取最左端的話,當本身有序時,會淪為氣泡排序,變成n平方

image.png

(例題)洛谷1177快速排序

https://www.luogu.com.cn/problem/P1177

錯誤版本

無優化,有序會TLE

```cpp

include

include

int a[1000001];//定義全域性變數,這兩個變數需要在子函式中使用

void swap(int a, int b) { int temp; temp = a; a = b; b = temp; }

//遞迴方法 void quicksort(int left, int right) { //舉例子可得出若左邊大於等於右邊就返回? //大於的情況是:index剛好==right,然後還要再去(index+1,right) if (left >= right) { return; } //預設基準index是最左邊那個,且i從左邊開始,j從右邊開始 int i = left, j = right, index = left;

//重構方法
//大前提,兩個沒相遇
while (i != j) {
    //裡邊還得判斷一下i<j,因為外邊的大前提,裡邊可能會破壞掉
    while (a[j] >= a[left]&&i<j) {
        j--;
    }
    while(a[i] <= a[left]&&i<j){
        i++;
    }
    //若i,j還未相遇
    if (i < j) {
        swap(&a[i], &a[j]);
    }
}
//出來時i,j必然相遇
swap(&a[i],&a[index]);
//將i賦值給基準
index = i;

quicksort(left, index - 1);
quicksort(index + 1, right);

} ``` image.png

先取到mid,然後讓左邊跟mid交換

由於是單邊搜尋,後兩個點都TLE

```cpp

include

include

include

include

include

include

void swap(int arr[], int i, int j) { int temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void QuickSort(int arr[], int left, int right) { int i, pivot;

if (left >= right)
    return;
pivot = left;
swap(arr, left, (left + right) / 2);
for (i = left + 1; i <= right; i++) //單邊搜尋,可以該為雙向搜尋
    if (arr[i] < arr[left])
        swap(arr, i, ++pivot);
swap(arr, left, pivot);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);

} int main() { int n; int *arr; int i;

scanf("%d", &n);
arr = (int*)malloc(sizeof(int) * (n + 1));
for (i = 1; i <= n; i++)
    scanf("%d", arr + i);

QuickSort(arr, 1, n); 
for (i = 1; i <= n; i++)
    printf("%d ", arr[i]);
return 0;

} ``` image.png

改進成雙邊搜尋

只是最後一個點TLE了,而最後一個點,剛好就是常數列的情況

```cpp

include

include

int a[100010];//定義全域性變數,這兩個變數需要在子函式中使用

void swap(int a, int b) { int temp; temp = a; a = b; b = temp; }

//遞迴方法 void quickSort(int left, int right) { //舉例子可得出若左邊大於等於右邊就返回? //大於的情況是:index剛好==right,然後還要再去(index+1,right) if (left >= right) { return; } //預設基準index是最左邊那個,且i從左邊開始,j從右邊開始 int i = left, j = right, index ; int mid=(left+right)/2; swap(&a[left],&a[mid]); index=left;

//重構方法
//大前提,兩個沒相遇
while (i != j) {
    //裡邊還得判斷一下i<j,因為外邊的大前提,裡邊可能會破壞掉
    while (a[j] >= a[left]&&i<j) {
        j--;
    }
    while(a[i] <= a[left]&&i<j){
        i++;
    }
    //若i,j還未相遇
    if (i < j) {
        swap(&a[i], &a[j]);
    }
}
//出來時i,j必然相遇
swap(&a[i],&a[index]);
index = i;

quickSort(left, index - 1);
quickSort(index + 1, right);

} int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } quickSort(0, n - 1); for (int i = 0; i < n; i++) { i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]); } } ```

覆盤mid(考慮常數列)

還沒三數取中,取到的mid是最小的話還是會退化到冒泡n平方

```cpp

include

include

using namespace std; int a[100010]; //交換元素位置 void swap(int a, int b) { int temp; temp = a; a = b; b = temp; } void quickSort(int* arr, int low, int high) { //若長度已經不符合要求,直接返回 if (low >= high) { return; } int left = low; int right = high; //選取中間為基準,注意是取中間的值,而不是下標,因為下標可能在後續交換中會改變 //比如left走到了mid這裡,而right停在了mid右邊,這時會去交換,arr[mid]就變了 int mid = arr[(low + high) >> 1]; while (left <= right) { //注意是小於,如果是小於等於的話,常數列就會一直left移動,而right不移動,淪為n平方 while (arr[left] < mid) { left++; } //同樣注意是大於 while (arr[right] > mid) { right--; } //這裡要注意是小於或等於,以便於left和right直接跳到樞紐點的左右 if (left <= right) { swap(&arr[left], &arr[right]); left++; right--; } } //遞迴呼叫 //right走到了區間一的尾部 quickSort(arr,low, right); //left走到了區間二的頭部 quickSort(arr, left, high); } int main() { int n, i; cin >> n; for (i = 1; i <= n; i++) { cin >> a[i]; } quickSort(a,1,n); for (i = 1; i <= n; i++) { cout << a[i] << " "; } cout << endl; } ```

流程圖

此處取到的mid是60

image.png

此時left和right已經相遇了

  • 然後left發現不滿足條件,86>mid(60),left還在86
  • right滿足條件,right去--,走到了15那裡停下來
  • 然後left不滿足<=right,直接就要開始繼續遞迴了
  • 遞迴的區間①是: [42,15] (都小於等於60)
  • 區間②是 : [86,68] (都大於等於60) c while (arr[left] < mid) { left++; } //同樣注意是大於 while (arr[right] > mid) { right--; } //這裡要注意是小於或等於,以便於left和right直接跳到樞紐點的左右 if (left <= right) { swap(&arr[left], &arr[right]); left++; right--; } //遞迴呼叫 //right走到了區間一的尾部 quickSort(arr,low, right); //left走到了區間二的頭部 quickSort(arr, left, high);

問題

因為沒有去把樞紐放到正確的位置,導致最後其實分出來的區間長度會多出一個元素:樞軸(這樣會很影響時間效率嗎)

自行用一定資料量測試的話,時間效率上差距還算不上很大的。

**結合三數取中(暫時的神)

```c

include

include

include"RcdSqList.h"

using namespace std; //int a[100010]; //交換元素位置 void swap(int a, int b) { int temp; temp = a; a = b; b = temp; } //三數取中 int getmid(int array, int left, int right) { int mid = left + ((right - left) >> 1); if (array[left] <= array[right]) { if (array[mid] < array[left]) return left; else if (array[mid] > array[right]) return right; else return mid; } else { if (array[mid] < array[right]) return right; else if (array[mid] > array[left]) return left; else return mid; } } void quickSort(int arr, int low, int high) { //若長度已經不符合要求,直接返回 if (low >= high) { return; } int left = low; int right = high; //選取中間為基準,注意是取中間的值,而不是下標,因為下標可能在後續交換中會改變 //比如left走到了mid這裡,而right停在了mid右邊,這時會去交換,arr[mid]就變了 //呼叫三數取中,得到中間數 int mid = arr[getmid(arr, low, high)]; while (left <= right) { //注意是小於,如果是小於等於的話,常數列就會一直left移動,而right不移動,淪為n平方 while (arr[left] < mid) { left++; } //同樣注意是大於 while (arr[right] > mid) { right--; } //這裡要注意是小於或等於,以便於left和right直接跳到樞紐點的左右 if (left <= right) { swap(&arr[left], &arr[right]); left++; right--; } } //遞迴呼叫 //right走到了區間一的尾部 quickSort(arr, low, right); //left走到了區間二的頭部 quickSort(arr, left, high); } int main() { int n, i; /cin >> n;/ /for (i = 1; i <= n; i++) { cin >> a[i]; }/ int a[100] = { 0,42 ,90,30,86,42,15,57,20 }; quickSort(a, 1, 8); for (i = 1; i <= 8; i++) { cout << a[i] << " "; } cout << endl; } ```

總結

最後是下載了測試點,然後看了部落格,去找超時的原因,其實是完全有序 然後拿標準答案debug一下,終於發現了區別,就是常數列的時候他兩個都移動,我只是一個移動,就退化成n平方了

注意

要<號而不是<=

**要去放大問題,比如j一直往左走,要放大到一直走走走走到i那裡去了!

看黑馬視訊得出的感悟.... 這個問題很嚴重,會變成n平方 如果把基準放最左邊,而本身有序的話就會超時了

xxxx樞軸要選大小為中間的值,才能解決完全有序的情況(得三數取中.)

  • 注意這裡的取中間值不是說取區間中間的值,而是大小在首尾區間中間數三個值排列居中的那個
  • 如果取的是區間中間的值,並不能解決完全有序的問題,比如 5 4 1 2 3 ,取mid等於1,又是取到了最小的情況,最後mid放到正確的位置(即第一個位置),遞迴他的左右,並沒有起到把原區間化成兩半的效果,只是得到了右邊那一段,相當與只是減少了一個元素(類似冒泡的把一個元素放到正確的位置而已)

讓left++的條件應該是<號! , 交換完要順便讓left++,right--,這樣才能解決常數列的情況

如果我們不在交換完做移動的話,那>就得改成>=,這樣才會移動,但就變成單指標移動了,還是退化成n平方了

交換完移動後,left和right剛好就是兩個區間的首跟尾

**三向切割法

https://www.luogu.com.cn/problem/P1177(依舊是模板題)

先來看程式碼

```c

include

include

using namespace std; int a[100010]; //交換元素位置 void swap(int a, int b) { int temp; temp = a; a = b; b = temp; } //三數取中 int getmid(int* array, int left, int right) { int mid = left + ((right - left) >> 1); if (array[left] <= array[right]) { if (array[mid] < array[left]) return left; else if (array[mid] > array[right]) return right; else return mid; } else { if (array[mid] < array[right]) return right; else if (array[mid] > array[left]) return left; else return mid; } } void quickSort_2(int rcd[], int low, int high) { if (low >= high) { return; } //呼叫三數取中,獲取樞紐位置 int pivot=getmid(rcd,low,high); //把樞紐值放到low位置(交換) swap(&rcd[low],&rcd[pivot]); //樞紐值就等於rcd[low] int pivotVal = rcd[low]; //i用來遍歷一趟區間 int left, right, i; //直接從樞紐的下一位開始遍歷區間 left = low, right = high, i = low + 1; //遍歷整個區間 while (i <= right) { //若小於樞紐值 if (rcd[i] < pivotVal) { //得放到前邊,跟left交換 swap(&rcd[i], &rcd[left]); //交換完,i換來了一個i前邊的值,肯定比較過了,所以i++ i++; //left換來了一個i原來位置的值,也比較過了,所以left++ left++; } //若大於樞紐值 else if(rcd[i]>pivotVal) { //得放到後邊,跟right交換 swap(&rcd[i], &rcd[right]); //right換來了一個i原來位置的值,也比較過了,所以right++ right--; //i不動,因為換過來一個i後邊的新的值,還沒比較過

    }
    //等於的情況
    else
    {
        i++;
    }
}
quickSort_2(rcd, low, left - 1);
quickSort_2(rcd, right + 1, high);

} int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } quickSort_2(a,0, n - 1); for (int i = 0; i < n; i++) { i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]); } } ```

粗糙的流程圖

這裡我們先預設樞軸就是最左邊的元素就好了,方便理解(實際情況再按上邊程式碼取中後跟最左邊交換即可)

用一個i去遍歷這個區間,還需要一個left和一個right指標

  • 當 rcd[i]大於樞紐值時,比如圖中的90
  • 當rcd[i]小於樞紐值時,比如圖中的20
  • 當rcd[i]等於樞紐值時,比如圖中的42

    具體看圖中的文字說明

總結一下就是,如果該位置是一個已經跟樞紐值比較過了的值,或者換過來一個已經跟樞紐值比較過了的值(那就需要更新一下他的指標位置) image.png

優勢

  • 減少了對重複元素的比較操作,因為重複元素在一次排序中就已經作為單獨一部分排好了,之後只需要對不等於該重複元素的其他元素進行排序。

寫在最後

  • 到了快排這裡,其實已經涉及到一些遞迴的知識,跟遞迴相關的其實還有“折半查詢”、“歸併排序”等,本專欄也還還會持續更新相關的知識,歡迎關注一起學習!