? ? ? ?快速排序是一種高效的排序算法。它采用了分治的策略,通過選擇一個基準元素,將待排序的序列劃分為兩部分,一部分的元素都比基準元素小,另一部分的元素都比基準元素大,然后對這兩部分分別進行快速排序,從而實現整個序列的有序排列。
以下是快速排序的基本步驟:
- 選擇一個基準元素:通常可以選擇序列的第一個元素、最后一個元素或者中間元素作為基準。
- 分區操作:通過一系列的比較和交換,將序列中小于基準的元素移到基準的左邊,大于基準的元素移到基準的右邊。
- 對分區后的左右兩部分子序列,分別重復步驟 1 和 2,直到整個序列有序。
例如,對于序列?[12, 11, 13, 5, 6]
?,選擇第一個元素?12
?作為基準:
- 經過分區操作后,序列變為?
[5, 11, 6, 12, 13]
?。 - 然后對?
[5, 11, 6]
?和?[12, 13]
?分別繼續進行快速排序。
快速排序的平均時間復雜度為 (O(nlogn)) ,空間復雜度為(Ologn)? 。在大多數情況下,它的性能非常出色,但在最壞情況下,時間復雜度會退化為(On2)? 。不過,通過合理選擇基準元素,可以很大程度上避免最壞情況的發生。
快速排序的單趟排序
? ? ? ?通過一趟排序將數據分割成獨立的兩部分,其中一部分的所有數據都比另一組數據的數值小,然后再次使用相同的方法分別將這兩部分再分成兩部分,從而完成快速排序。
1.霍爾法
“霍爾法”通常指的是快速排序(Quick Sort)中的一種實現方式,也被稱為霍爾劃分。
快速排序是一種分治算法,其基本思想是通過一趟排序將待排序的序列劃分成兩部分,然后對這兩部分分別進行排序,以實現整個序列的有序。
霍爾法的具體實現步驟如下:
- 選取一個基準元素 key,通常選擇數組的第一個元素、中間元素或最后一個元素,也可以選擇這三個元素的中間值等,然后將這個基準元素與數組第一個元素進行交換。
- 定義兩個指針 left 和 right,left 從數組的第一個元素開始(即左邊)向右遍歷,right 從數組的最后一個元素開始(即右邊)向左遍歷。
- 首先,right 指針從右向左移動,找到比 key 小的值時停下來。然后,left 指針從左向右移動,找到比 key 大的值時停下來。
- 交換 left 和 right 所指向的值,這一步的目的是將比 key 小的值往左放,將比 key 大的值往右放。
- 重復步驟 3 和 4,直到 left 和 right 相遇。
- 當 left 和 right 相遇后,將第一個元素(即 key)與它們相遇位置的值交換。此時,key 左邊的元素都比它小,右邊的元素都比它大,但左右兩邊的子序列并不一定是有序的。
- 對 key 左邊的子序列和右邊的子序列,分別重復上述步驟,進行遞歸排序,直到子序列不存在或者只有一個元素時結束遞歸。
key——>基準下標值;
指針 left指向最左端的元素也就是第一個元素(找比key大的元素)
? ? ? ? right指向最右端的元素也就是最后一個元素(找比key小的元素)
<1>
? ? ? left記錄左下標,從左向右遍歷
? ? ? right記錄右下標,從右向左遍歷,以第一個數作為基準值
^left? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ^right ? ? ? ? ? ? ? ? ?? ? ? ? ?key=5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
<2>
? ? ? right先出發,找比key小的值,找到停下
^left? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??^right key=5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
<3>
? ? ? left出發,找比key大的值,找到停下并與right進行交換
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^left? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^right? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??key=5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^left? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^right? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??key=5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
<4>
? ? ?重復步驟<2>,<3>,直到left與right指向同一個數
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ^right? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^left? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?key=5? ? ? |
<5>
? ? 將left/right與key交換,完成單趟排序
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ^right? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^left? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?key=5? ? ? |
總的來說就是把比key小的放在key左邊,比key大的放在key右邊,以下是代碼實現單趟排序
#include <stdio.h>// 交換兩個整數的值
void swap(int* a, int* b) {int tmp = 0;tmp = *a;*a = *b;*b = tmp;
}// 獲取數組中 begin、mid、end 三個位置元素的中間值,并與數組第一個元素交換
int getMid(int* a, int begin, int end) {int mid = (begin + end) / 2;if (a[begin] > a[mid]) {if (a[mid] > a[end]) {return mid;} else if (a[end] > a[begin]) {return begin;} else {return end;}} else {if (a[begin] > a[end]) {return begin;} else if (a[end] > a[mid]) {return mid;} else {return end;}}
}// 霍爾法快速排序的核心函數
void quickSortHoare(int* a, int begin, int end) {int left = begin;int right = end;if (left >= right) {return;}int mid = getMid(a, begin, end);swap(&a[begin], &a[mid]); int keyi = begin; while (left < right) {while (left < right && a[right] >= a[keyi]) {right--;}while (left < right && a[left] < a[keyi]) {left++;}swap(&a[left], &a[right]);}swap(&a[left], &a[keyi]); keyi = left; quickSortHoare(a, begin, keyi - 1); quickSortHoare(a, keyi + 1, end);
}// 打印數組函數
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {12, 11, 13, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的數組為:");printArray(arr, n);quickSortHoare(arr, 0, n - 1); printf("排序后的數組為:");printArray(arr, n);return 0;
}
2.挖坑法
? ? ? ? 與霍爾法不同的是,將key基準值用變量保存起來,然后將key空出來,也就是形成一個坑,left先指向這個坑right找比key小的值放進坑里,并將自己的位置設為坑,left找比key大的放進坑里,自己又變成坑,如此循環。
<1>
? ? ?先定義變量key,存儲數組第一個值作為key,此時left指向坑
? ^key? ? ? ?^left? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ^right |
<2>
? ? ?right開始找比key小的數,放進坑里,自己變為坑
? ^key? ? ? ?^left? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ^right |
? ^key? ? ? ?^left? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ^right |
<3>
? ? ?left開始找比key大的數,同上
? ^key? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^left? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ^right |
? ^key? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^left? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ^right |
<4>
? ? ?重復步驟<2>,<3>,直到left與right相遇
? ^key? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ^left? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???^right |
<5>
? ? ?將key放在相遇的坑里,排序完畢,將key下標返回
?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ^left? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^key? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???^right |
以下是代碼實現:
int PartSort(int *arr,int left,int right){
int key=arr[left];
int hole=left;
while(left<right){
while(arr[right]>=key&&left<right){
right--;
}
arr[hole]=arr[right];
hole=right;
while(left<right&&arr[left]<=key){
left++;
}
arr[hole]=arr[left];
hole=left;
}
arr[hole]=key;
return hole;
}
?3.前后指針
? ? ? ?將數組的第一個元素作為基準值key,定義前指針prev指向數組第一個元素,后指針cur指向數組第二個數,由cur遍歷數組,找出比key小的數,prev在cur找到后向后移動一位并與cur交換,保證較小數在prev之前。
<1>
開始時prev指向數組第一個元素,cur指向第二個元素,此時cur的值比key小,prev向后移動一位后與cur交換,無變化
^prev? ? ? ? ? ^cur? ? ? ? ? ? ? ? ? ? ? ?key=5? ? ? ??^prev+1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
<2>
cur找到比key大的數此時cur繼續向后移動,prev不變
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ^cur? ? ? ? ? ? ? ? ? ? ? ?key=5? ? ? ??^prev? ?? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? |
<3>
cur找到比key小的數此時prev向后移動一位,并與cur交換
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ^cur? ? ? ? ? ? ? ? ? ? ? ?key=5? ? ? ??^prev? ?? ? ? ?? ? ? ? ? |
?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ^cur? ? ? ? ? ? ? ? ? ? ? ?key=5? ? ? ? ? ? ? ? ? ? ? ? ??^prev? ?? ? ? ?? ? ? ? ? |
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ^?cur? ? ? ? ? ? ? ? ? ? ?key=5? ? ? ? ? ? ? ? ? ? ? ? ??^prev? ?? ? ? ?? ? ? ? ? |
<4>
? ? ?重復步驟<2>,<3>,直到cur完成遍歷
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^cur? ? ? ? ? ? ? ? ? ? ? ?key=5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^prev? ?? ? ? ?? ? ? ? ? |
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 交換3和7
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^cur? ? ? ? ? ? ? ? ? ? ? ?key=5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??^prev? ?? ? ? ?? ? ? ? ? |
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?交換4和7
? ? ? ? ? ? ? ? ? ? ?key=5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^prev? ?? ? ? ?? ? ? ? ? |
?
<5>
? ? ?cur完成遍歷后,將prev與key進行交換,返回key的下標
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? key=5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??^prev? ?? ? ? ?? ? ? ? ? |
?以下是代碼實現:
int PastSort(int *arr,int left,int right){
int key=left;
int prev=left;
int cur=left+1;
while(cur<=right){
if(arr[cur]<=arr[key]&&++prev!=cur){
swap(&arr[cur],&arr[prev];
}
cur++;
}
swap(&arr[key],&arr[prev]);
return prev;
}
?其實快速排序最核心的代碼就是單趟排序,以上三種是單趟排序的三種方法,大家任選一種牢記就好,主要函數的代碼如下(遞歸實現)
void QuickSort(int *arr,int begin,int end){
if(begin>=end){
return;
}
int key=PartSort(arr,begin,end);
QuickSort(arr,begin,key-1);
QuickSort(arr,key+1,end);
}