目錄

前言

快速排序

?基本思路

?非遞歸代碼實(shí)現(xiàn)

算法分析

空間復(fù)雜度

時(shí)間復(fù)雜度

穩(wěn)定性

---

前言

? ? ? ? 很久沒(méi)跟新數(shù)據(jù)結(jié)構(gòu)與算法這一欄了，因?yàn)閿?shù)據(jù)結(jié)構(gòu)與算法基本上都發(fā)布完了，哈哈，那今天我就把前面排序算法那一塊的快速排序完善一下，前面只發(fā)布了快速排序遞歸算法，那這一次就去用非遞歸來(lái)去實(shí)現(xiàn)。（遞歸算法：排序算法-----快速排序（遞歸）_快排遞歸_Gretel?Tade的博客-CSDN博客）

快速排序

?快速排序（Quicksort），計(jì)算機(jī)科學(xué)詞匯，適用領(lǐng)域Pascal，C++等語(yǔ)言，是對(duì)冒泡排序算法的一種改進(jìn)。

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

?基本思路

現(xiàn)在給定一個(gè)數(shù)組初始?[25,24,6,65,11,43,22,51] ，然后進(jìn)行快速排序

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

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

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

temp

?第二步，先去向左移動(dòng)j 的位置，當(dāng)j指向的數(shù)字小于temp時(shí)候，就停止移動(dòng)，然后開始向右移動(dòng)i?

當(dāng)i 移動(dòng)到比temp要大的數(shù)字時(shí)，停止移動(dòng)，此時(shí)將i 和 j 指向的數(shù)字進(jìn)行交換，如下所示：

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

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

交換后：

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

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

?第三步，此時(shí)，開始接著移動(dòng) j，當(dāng)j 移動(dòng)到比temp要小的數(shù)字的時(shí)候，停止移動(dòng), 如下所示：

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

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

?然后開始移動(dòng)i ，當(dāng)i 移動(dòng)到與j 相遇的位置時(shí)，i停止移動(dòng)（如果i 移動(dòng)到比temp要大的數(shù)字的時(shí)候就執(zhí)行上面的第二步，i與j 進(jìn)行數(shù)字交換）

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

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

第四步，此時(shí)，i與j指向的數(shù)字與temp指向的數(shù)字進(jìn)行數(shù)字交換

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

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

這時(shí)候我們會(huì)發(fā)現(xiàn)，此時(shí)i和j指向的數(shù)字的位置，左邊的都比這個(gè)數(shù)字要小，右邊的都比這個(gè)數(shù)字要大，于是我們就可以去進(jìn)入到遞歸，分別對(duì)左邊和右邊的數(shù)字進(jìn)行以上步驟的遞歸，最后兩邊的數(shù)字都會(huì)被排好序。

動(dòng)態(tài)圖

?非遞歸代碼實(shí)現(xiàn)

#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都停止移動(dòng)的時(shí)候，交換數(shù)字int t = arr[i];arr[i] = arr[j];arr[j] = t;}}//此時(shí)i與j相遇，進(jìn)行數(shù)字交換arr[left] = arr[i];arr[i] = temp;return i;//返回這個(gè)交匯點(diǎn)
}void quick_sort(int* arr, int left, int right) {int* stack = (int*)malloc(sizeof(int) * right);//創(chuàng)建一個(gè)數(shù)組棧for (int i = 0; i < right; i++)stack[i] = -1;//初始化為-1int count = 0;//當(dāng)前棧數(shù)據(jù)的個(gè)數(shù)if (left < right) {//入棧stack[count++] = left;stack[count++] = right;}while (count) {//當(dāng)棧為非空的時(shí)候//出棧操作int r_pop = stack[count-1];int l_pop = stack[count-2];stack[count - 1] = stack[count - 2] = -1;//出棧后，清空已出棧數(shù)據(jù)，設(shè)置為-1count -= 2;int i = sort(arr, l_pop, r_pop);//如果這個(gè)交匯點(diǎn)前面數(shù)據(jù)的下標(biāo)比當(dāng)前最左邊的數(shù)據(jù)下標(biāo)要大的話，就入棧if (l_pop < i - 1) {stack[count++] = l_pop;stack[count++] = i - 1;}//如果這個(gè)交匯點(diǎn)后面一個(gè)數(shù)據(jù)的下標(biāo)比當(dāng)前最右邊數(shù)據(jù)的下標(biāo)要小的話，入棧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]);}
}

運(yùn)行結(jié)果：

算法分析

空間復(fù)雜度

快速排序算法沒(méi)有涉及到空間的開辟，使用的空間是原數(shù)組空間，空間復(fù)雜度為O(1)

時(shí)間復(fù)雜度

快速排序之所以比較快，是因?yàn)榕c冒泡排序相比，每次的交換時(shí)跳躍式的，每次排序的時(shí)候設(shè)置一個(gè)基準(zhǔn)點(diǎn)，將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊，將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的右邊。這樣整體交換次數(shù)和比較次數(shù)就少很多，?故排序速度就提高了許多，當(dāng)然如果是最壞的情況下時(shí)間復(fù)雜度還是為O(n^2)，其平均的時(shí)間復(fù)雜度為 O(nlog2?n)

穩(wěn)定性

?俗話說(shuō)得好：有得必有失?？焖倥判螂m然排序速度快了很多，但是其缺犧牲了穩(wěn)定性，當(dāng)出現(xiàn)相同大小元素的時(shí)候，相同大小元素的相對(duì)位置會(huì)發(fā)生改變，每次遞歸都會(huì)發(fā)生變化，這就導(dǎo)致了快速排序的穩(wěn)定性不好，這是因?yàn)榭焖倥判蚋淖兞私粨Q的規(guī)則，使用跳躍式交換，沒(méi)有進(jìn)行數(shù)字大小的一一比較，故快速排序是不穩(wěn)定的，所以選擇排序算法的時(shí)候要慎重選擇，充分考慮到穩(wěn)定性

以上就是本期的全部?jī)?nèi)容了，喜歡的話給個(gè)贊吧！

分享一張壁紙：?