目錄

前言

快速排序

?基本思路

?非遞歸代碼實現

---

前言

? ? ? ? 很久沒跟新數據結構與算法這一欄了，因為數據結構與算法基本上都發布完了，哈哈，那今天我就把前面排序算法那一塊的快速排序完善一下，前面只發布了快速排序遞歸算法，那這一次就去用非遞歸來去實現。（遞歸算法：排序算法-----快速排序（遞歸）_快排遞歸_Gretel?Tade的博客-CSDN博客）

快速排序

?快速排序（Quicksort），計算機科學詞匯，適用領域Pascal，C++等語言，是對冒泡排序算法的一種改進。

? ? ? ? 快速排序采用的是分治思想，即在一個無序的序列中選取一個任意的基準元素pivot，利用pivot將待排序的序列分成兩部分，前面部分元素均小于或等于基準元素，后面部分均大于或等于基準元素，然后采用遞歸的方法分別對前后兩部分重復上述操作，直到將無序序列排列成有序序列。

?基本思路

現在給定一個數組初始?[25,24,6,65,11,43,22,51] ，然后進行快速排序

?第一步，先選取一個參考數字temp，一般選取第一個即temp=25，然后標記最左邊和最右邊數字的位置分別為i, j

?25? ? ? ? 24? ? ? ? 6? ? ? ? 64? ? ? ? 11? ? ? ? 43? ? ? ? 22? ? ? ? 51

? i? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?j

temp

?第二步，先去向左移動j 的位置，當j指向的數字小于temp時候，就停止移動，然后開始向右移動i?

當i 移動到比temp要大的數字時，停止移動，此時將i 和 j 指向的數字進行交換，如下所示：

?25? ? ? ? 24? ? ? ? 6? ? ? ? 64? ? ? ? 11? ? ? ? 43? ? ? ? 22? ? ? ? 51

temp? ? ? ? ? ? ? ? ? ? ? ? ? ? ?i? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?j

交換后：

?25? ? ? ? 24? ? ? ? 6? ? ? ? 22? ? ? ? 11? ? ? ? 43? ? ? ? 65? ? ? ?51

temp? ? ? ? ? ? ? ? ? ? ? ? ? ? ?i? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?j

?第三步，此時，開始接著移動 j，當j 移動到比temp要小的數字的時候，停止移動, 如下所示：

?25? ? ? ? 24? ? ? ? 6? ? ? ? 22? ? ? ? 11? ? ? ? 43? ? ? ? 65? ? ? ?51

temp? ? ? ? ? ? ? ? ? ? ? ? ? ? ?i? ? ? ? ? ?j

?然后開始移動i ，當i 移動到與j 相遇的位置時，i停止移動（如果i 移動到比temp要大的數字的時候就執行上面的第二步，i與j 進行數字交換）

?25? ? ? ? 24? ? ? ? 6? ? ? ? 22? ? ? ? 11? ? ? ? 43? ? ? ? 65? ? ? ?51

temp? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ?i,j

第四步，此時，i與j指向的數字與temp指向的數字進行數字交換

?11? ? ? ? 24? ? ? ? 6? ? ? ? 22? ? ? ? 25? ? ? ? 43? ? ? ? 65? ? ? ?51

temp? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ?i,j

這時候我們會發現，此時i和j指向的數字的位置，左邊的都比這個數字要小，右邊的都比這個數字要大，于是我們就可以去進入到遞歸，分別對左邊和右邊的數字進行以上步驟的遞歸，最后兩邊的數字都會被排好序。

動態圖

?非遞歸代碼實現

#include<stdio.h>
#include<stdlib.h>
//每一趟排序
int sort(int* arr, int left, int right) {int i = left;int j = right;int temp = arr[left];while (i != j) {while (temp <= arr[j] && i < j)//j左移j--;while (temp >= arr[i] && i < j)//i向右移i++;if (i < j) {//i與j都停止移動的時候，交換數字int t = arr[i];arr[i] = arr[j];arr[j] = t;}}//此時i與j相遇，進行數字交換arr[left] = arr[i];arr[i] = temp;return i;//返回這個交匯點
}void quick_sort(int* arr, int left, int right) {int* stack = (int*)malloc(sizeof(int) * right);//創建一個數組棧for (int i = 0; i < right; i++)stack[i] = -1;//初始化為-1int count = 0;//當前棧數據的個數if (left < right) {//入棧stack[count++] = left;stack[count++] = right;}while (count) {//當棧為非空的時候//出棧操作int r_pop = stack[count-1];int l_pop = stack[count-2];stack[count - 1] = stack[count - 2] = -1;//出棧后，清空已出棧數據，設置為-1count -= 2;int i = sort(arr, l_pop, r_pop);//如果這個交匯點前面數據的下標比當前最左邊的數據下標要大的話，就入棧if (l_pop < i - 1) {stack[count++] = l_pop;stack[count++] = i - 1;}//如果這個交匯點后面一個數據的下標比當前最右邊數據的下標要小的話，入棧if (r_pop > i + 1) {stack[count++] = i + 1;stack[count++] = r_pop;}}//釋放空間free(stack);stack = NULL;
}int main() {int array[8] = { 25,24,6,65,11,43,22,51 };printf("排序前:");for (int i = 0; i < sizeof(array) / sizeof(int); i++) {printf("%d ", array[i]);}printf("\n排序后：");quick_sort(array, 0, sizeof(array) / sizeof(int) - 1);for (int i = 0; i < sizeof(array) / sizeof(int); i++) {printf("%d ", array[i]);}
}

運行結果：

以上就是本期的全部內容了，喜歡的話給個贊吧！

分享一張壁紙：?