您当前的位置： 首页 > 慢生活 > 程序人生 网站首页程序人生

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

发布时间：2021-04-27 21:17:58编辑：雪饮阅读（）

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

那么这次来了解下快速排序，快速排序也分为迭代法和递归法。
那么今天的主角是迭代法。同样是迭代法，快速排序的迭代法可以说是比归并排序的迭代法要容易懂的多了。
快速排序
在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。
过程演示：

那么迭代法其实现如：
#include <stdio.h>
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 <= 0)
        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<mindex;z++){
                     if(z==mindex-1){
                            printf("%d",arr[z]);
                     }
                     else{
                            printf("%d,",arr[z]);
                     }
              }
              printf("\n");
              printf("\n");
              printf("左到右：");
              for(int zy=left;zy<=right;zy++){
                     if(zy==right){
                            printf("%d",arr[zy]);
                     }
                     else{
                            printf("%d,",arr[zy]);
                     }
              }
             
              printf("\n右範圍：");
              for(int y=mindex+1;y<=right;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 <= right)
            {
                            printf("\n %-8s left(%d)小于等于right(%d)準備交換\n","",left,right);
                            printf("\n %-8s 交換前arr整體隊列：","");
                            for(int jh=0;jh<len;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<len;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 <= right);
              /*
              上面的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[]={9,2,5,7,3,1,6,8,4};
       int len=9;
       quick_sort(arr,len);
       for(int x=0;x<len;x++){
              printf("%d\n",arr[x]);
       }
}