王道數據結構 之 快速排序算法系列 *****

wellzhi 2022-07-23 21:04:40 阅读数:531

王道快速排序算法法系

簡單總結:

快速排序 = 劃分 + 遞歸

樞軸元素:

通常選擇順序錶第一個元素,用於劃分順序錶為兩部分,左邊部分值小於樞軸,右邊部分值大於樞軸

算法步驟:

  1. 確定樞軸pivot,並用一個新變量存儲:int pivot = A[low]
  2. high: 依次從後往前掃描,如果 元素值 A[high] < pivot,則 A[low] = A[high],否則high--
  3. low: 依次從前往後掃描,如果 元素值 A[low] > pivot,則 A[high] = A[low],否則low++

算法實現

int Partition(int A[], int low, int high) {

int pivot = A[low];
while (low < high) {

while (low < high && A[high] >= pivot) {

high--;
}
A[low] = A[high]; // 比樞軸元素小的元素移動到左端
while (low < high && A[low] <= pivot) {

low++;
}
A[high] = A[low]; // 比樞軸元素大的元素移動到右端
}
A[low] = pivot; // 樞軸元素放到最終比特置
return low; // 樞軸元素的最終比特置,左邊元素小於樞軸元素,右邊元素大於樞軸元素
}
void QuickSort(int A[], int low, int high) {

if (low < high) {

int pivotPos = Partition(A, low, high); // 進行一次劃分
QuickSort(A, low, pivotPos - 1); // 遞歸劃分左邊部分
QuickSort(A, pivotPos + 1, high); // 遞歸劃分右邊部分
}
}
版权声明:本文为[wellzhi]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/204/202207232104173692.html