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

c语言实现快速排序遞歸法

发布时间：2021-04-28 20:51:57编辑：雪饮阅读（）

 上次了解了快速排序的迭代法，那么这次来了解下快速排序的递归法。

递归法总体来说还是有一些难度的。
那么快速排序递归法其演示也是和之前的递归法其实是一样的。

同样的效果可以有不同的实现方式，我想这个在做web前端的童鞋应该是不陌生了。
那么这里具体快速排序递归法实现如：
#include <stdio.h>
void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = arr[end];
    int left = start, right = end - 1;
       int left_o=start,right_o=right;
       printf("\n本次序列:");
       for(int x=left;x<=right;x++){
              if(x==right){
                     printf("%d",arr[x]);
              }
              else{
                     printf("%d,",arr[x]);
              }
       }
       printf("\n");
       printf("\n本次序列中間值:%d \n",mid);
      
    while (left < right) {
        //循環結束后左邊大于等于中間值，或者左邊索引大于等于右邊（找到不屬于左邊的值（距離中間值最近））
              while (arr[left] < mid && left < right){
                     printf("\n %-8s left=>%d,增加條件觸發\n","",left);
                     left=left+1;
                    
              }
        //循環結束后右邊小于或等于中間值，或者左邊索引大于等于右邊 （找到不屬于右邊的值（距離中間值最近））
        while (arr[right] >= mid && left < right){
                     printf("\n %-8s right=>%d,減少條件觸發\n","",right);
                     right=right-1;
              }
              int before_swap_left_index=left,before_swap_right_index=right;
              int before_swap_left=arr[left],before_swap_right=arr[right];
             
       printf("\n %-4s left與right交換:arr[left]=>%d,arr[right]=>%d \n","",arr[left],arr[right]);
              /*
              對于上面的循環條件arr[left] < mid && left < right和arr[right] >= mid && left < right循環條件
              條件1：儅left >=right時候，要麽左邊過界到了右邊，要麽右邊過界到了左邊。
                        那麽如果是左邊過界，則説明有比中間小的數在右邊，所以這裏調換位置理所當然
                        那麽右邊過界，則説明有比中間數大的數在左邊，那麽也是理所當然需要調換位置了
                        由于左邊向右邊移動指針，同時右邊也向左邊移動指針，這樣就形成了每兩個進行比較交換的效果，
                        一般常見的就是這兩個指針中間只間隔一個數，但是由于數列縂不都是順序排列，所以有可能間隔多個數，這點需要自己想象了，不怎麽好描述
                        儅left==right的時候，這兩個位置交換則也不影響排序（兩個指針到同一個位置上了）
              條件2：對于條件arr[left] < mid，
                        儅arr[left] >mid時候，同樣是左邊值大于中間值，那麽這個值同樣是需要交換到右邊的。
                        儅arr[left]==mid時候，此時：
                                                                      右邊值若大于中間值，那麽交換位置后arr[left]將會在中間值右邊，由于arr[left]==mid，所以無論換在中間值前面或者中間值後面，則都是無所謂的
                                                                      右邊值若等于中間值，那麽相當于左右值都一樣，則交換位置也是無所謂的
                                                                      右邊值若小于中間值，那麽左右交換后，也形成了右邊這個小值到了左邊，而左邊這個相對于右邊的大值就進入到了右邊的位置，這也符合排序要求
              條件3：arr[right] >= mid，與條件2正好相反，但是道理都是一樣的。
             
                       
                           
                           
              */
        swap(&arr[left], &arr[right]);
              printf("\n %-4s arr[%d]=>%d與arr[%d]=>%d交換后:","",before_swap_left_index,before_swap_left,before_swap_right_index,before_swap_right);
             
              for(int x=left_o;x<=right_o;x++){
                     if(x==right_o){
                            printf("%d",arr[x]);
                     }
                     else{
                            printf("%d,",arr[x]);
                     }
              }
              printf("\n");
    }
       printf("\n本次序列内部交換后:");
       for(int x=left_o;x<=right_o;x++){
              if(x==right_o){
                     printf("%d",arr[x]);
              }
              else{
                     printf("%d,",arr[x]);
              }
       }
       printf("\n");
       /*
       上面循環外層循環結束后，最後一個左值與最後一個中值（最右邊那個值，不在數列中的值進行比較）
       上面的外層循環結束時候，最低條件就是left=right
       則此時，左邊指針到了最右邊，但是這裏每輪子序列都比上一個序列的最右邊少一個數字
       所以還有可能進行比較當前序列最後一個數字和上一個序列比當前數列多出來的那一個數字並進行交換
       */
       printf("\n %-8s arr[end]==%d,mid==%d \n","",arr[end],mid);
    if (arr[left] >= arr[end]){
              swap(&arr[left], &arr[end]);
       }
    //如果最後一個左值和小于等于本輪序列比上一輪序列少的那個值（最後那個值）   
    else{
              left++;
       }
    printf("\n本次序列處理結束準備進入下一個遞歸:left=>%d \n",left); 
       /*
       上面的嵌套循環結束后則left指針應該會指向離中間值最近的索引上，他的意圖是依次比較距離中間值最近的左值與右值、次近的左值與右值、次次近的左值與右值、次次次近的左值與右值...
       但，實現過程正好反向來，即從兩邊向中間靠攏（其實只是看的角度不同）
       中間值左移
       本輪序列只要有左邊數小于中間值的，則left都會自增，到這裏的時候left已經是最後一個滿足左值小于中間值的索引了
       left初始值和start一樣為0是假，若這裏還是假，則説明第0個元素就大于中間值，就不用繼續向後繼續找下一個值和中間值相比了
       */
    if (left){
              /*
              但是若這裏left大于0，那就説明符合左值小於中間值的不止一個，因爲這裏中間值是設置的最右邊的值，所以中間值要向左移動，以獲取下一個中間值，而從左到右最後一個小于中間值的值是離它最近的一個位置選擇
              上面arr[left] >= arr[end]時則交換位置，則left是最後那個值，而left-1則是end
              但如果arr[left] >= arr[end]不成立時即else時候left++則也使得left指向了最後那個值
              所以這裏選擇下一個中間值的時候就直接使用了最後的left-1
              然後繼續對數組arr從開始位置到這個新的中間值之間進行對比
              */
               quick_sort_recursive(arr, start, left - 1);
       }
       /*
       上面這一步驟相當于將當前序列中間值的左邊再不斷的排序，直到左邊都排序ok之後，
       接下來就是左邊最後一個小于中間值的位置，繼續開始向著中間位置繼續排序
       */
      
    quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}
void main(){
       int arr[]={2,1,4,6,8,3,9,5,7};
       int len=9;
       quick_sort(arr,len);
       //輸出
       printf("\n完成排序后結果：");
       for(int x=0;x<len;x++){
              if(x==len-1){
                     printf("%d",arr[x]);
              }
              else{
                     printf("%d,",arr[x]);
              }
             
       }
}
最后呢这里推荐一篇csdn上面比较好的关于快速排序的文章
https://blog.csdn.net/qq_49422279/article/details/113817697
该文章没有具体讲解快速排序的某个实现方法，但是其所讲的两端查找法比较有利于对快速排序的了解更深入一层。