c语言实现快速排序迭代法

相对于前面我们了解了归并排序发算法，其分为迭代法和递归法。

那么这次来了解下快速排序，快速排序也分为迭代法和递归法。

那么今天的主角是迭代法。同样是迭代法，快速排序的迭代法可以说是比归并排序的迭代法要容易懂的多了。

快速排序

在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。

过程演示：

那么迭代法其实现如：

#include

typedef struct _Range {

int start, end;

} Range;

Range new_Range(int s, int e) {

Range r;

r.start = s;

r.end = e;

return r;

}

void swap(int *x, int *y) {

int t = *x;

*x = *y;

*y = t;

}

void quick_sort(int arr[], const int len) {

if (len

return; // 避免len等於負值時引發段錯誤（Segment Fault）

// r[]模擬列表(數組類型的結構躰)

Range r[len];

int p = 0;

//最初的排序範圍

r[p] = new_Range(0, len - 1);

p=p+1;

while (p) {

p=p-1;

//每次獲取上一個排序範圍

Range range = r[p];

if (range.start >= range.end){

 continue;

}

// 選取中間點為基準點

int mindex=(range.start + range.end) / 2;

int mid = arr[mindex];

int left = range.start, right = range.end;

printf("\n左索引:%d,中索引:%d,右索引:%d\n",left,mindex,right);

printf("\n左值:%d,中值:%d,右值:%d\n",arr[left],mid,arr[right]);

printf("\n左範圍:");

for(int z=left;z

if(z==mindex-1){

printf("%d",arr[z]);

}

else{

printf("%d,",arr[z]);

}

}

printf("\n");

printf("\n");

printf("左到右：");

for(int zy=left;zy

if(zy==right){

printf("%d",arr[zy]);

}

else{

printf("%d,",arr[zy]);

}

}

printf("\n右範圍：");

for(int y=mindex+1;y

if(y==right){

printf("%d",arr[y]);

}

else{

printf("%d,",arr[y]);

}

}

printf("\n");

printf("\n");

printf("\n");

do

{

printf("\n %-8s left:%d,right:%d","",left,right);

// 檢測基準點左側是否符合要求

//循環1：遍歷當前隊列，從左到右，檢查每個小于中間值的值對應的索引

while (arr[left] < mid) {

printf("\n %-8s 檢查左側基准:%d小于%d,left加1=%d","",arr[left],mid,left+1);

//++left;

left=left+1;

}

//循環2：遍歷當前隊列，從右向左，檢查每個大于中間值的值對應的索引

while (arr[right] > mid){

//--right;

printf("\n %-8s 檢查右側基准:%d大于%d,right減1=%d","",arr[right],mid,right-1);

right=right-1;

}

/*

由于循環1的終止條件，則循環1結束后（即便循環1，一次都沒有執行過），left對應的值一定大于等于中間值

同理，此時循環2（無論執行還是沒有執行），那麽right對應的值一定小于等于中間值

那麽此時對于索引left和right而言，left若小于right，那麽豈不是左邊的值小于右邊的值，這樣不就是反了，所以下面要進行交換

*/

if (left

{

printf("\n %-8s left(%d)小于等于right(%d)準備交換\n","",left,right);

printf("\n %-8s 交換前arr整體隊列：","");

for(int jh=0;jh

if(jh==len-1){

printf("%d",arr[jh]);

}

else{

printf("%d,",arr[jh]);

}

       }

printf("\n %-8s 交換前的左右值：left:arr[%d]=%d,right:arr[%d]=%d","",left,arr[left],right,arr[right]);

printf("\n");

printf("\n %-8s 交換前的左值：arr[%d]=%d","",left,arr[left]);

swap(&arr[left],&arr[right]);

printf("\n %-8s 交換后的左值：arr[%d]=%d","",left,arr[left]);

printf("\n %-8s 交換后arr整體隊列：","");

for(int jh=0;jh

if(jh==len-1){

printf("%d",arr[jh]);

}

else{

printf("%d,",arr[jh]);

}

}

printf("\n");

// 移動指針以繼續

/*

交換以後也未必就能保證隊列從左到右邊是從小到大自增的

例如：

8，7,1，5，2

這裏中間值假比如為1，那麽8比2大，則交換之後就是：

2,7,1,5,8

但是2,7,1,5,8中

7又比5大，所以兩邊都需要向中間值進一步進行再次比較

*/

left=left+1;

right=right-1;

printf("\n %-8s 下一個左右 left:%d,right:%d\n","",left,right);

}

}

/*

如果左邊索引還是小于右邊索引，則表示，從左向右與從右向左這兩個指針還沒有碰面

*/

while (left

/*

上面的do循環是進行某個子序列中進行交換比較的

那麽儅right還大于上個序列（有可能是原始序列，也有可能是原始序列被中分n次后的某個子序列（中分的叫法可能不太合適，準確的來説就是從兩邊向中間推n次之後的剩餘空間的序列））的開始位置

則説明還有剩餘的局部序列還沒有被比較到

*/

if (range.start < right) {

r[p] = new_Range(range.start, right);

p=p+1;

}

//這個和range.start < right是同理，上面是從右邊看向左邊的角度是，這個是從左邊看向右邊的角度。想想其它情況下則都是原始序列就到此爲止全部排序完成了

if (range.end > left){

r[p] = new_Range(left, range.end);

p=p+1;

}

}

}

void main(){

int arr[]=;

int len=9;

quick_sort(arr,len);

for(int x=0;x

printf("%d\n",arr[x]);

}

}