C語言之快速排序案例詳解

更新時間：2021年07月30日 08:43:44 作者：小尹同學⁣

這篇文章主要介紹了C語言之快速排序案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下

快速排序：是對冒泡排序算法的一種改進。

它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

例如有一個數字序列： 5 0 1 6 8 2 3 4 9 7
對其進行快速排序變?yōu)椋? 1 2 3 4 5 6 7 8 9

思路如下：首先將要排序的序列的首個數字5定位比較數，這是一個參考對象！

然后的方法很簡單：分別從序列的兩端進行比較。先從右邊往左邊找比5小的數，再從左邊往右邊找大于5的數。當他們找到以后就需要停下來，然后交換它們。
在這里我們?yōu)榱朔奖?，將i定為左邊，j為右邊。

在這里插入圖片描述

接下來繼續(xù)前進，還是先從右邊。
接下來得到的序列如下：
5 0 1 4 3 2 8 6 9 7

當它繼續(xù)下去的時候我們可以知道這時,i,j相遇了。

這個時候，直接將比較數與相遇的數進行交換

得到如下序列：2 0 1 4 3 5 8 6 9 7

可以看出，在右邊的數都比比較數5大，左邊的數都比比較數5小。

這個時候其實就是第一輪排序結束了。

下面的排序就是將左邊與右邊分別看成兩個序列，然后與上面的一樣進行排序。這里其實就是應用到了遞歸！

完整代碼如下：

#include<stdio.h>
int a[100];//這里將數組a定義為全局變量，方便后面使用
void kspx(int left,int right)
{
    int i,j;
    int t,bjs;//bjs就是指開頭的比較數
    if(left>right)
        return;
    bjs=a[left];
    i=left;
    j=right;
    while(i!=j)
    {
        while (a[j]>=bjs&&i<j)//這里是從右往左走
            j--;
        while(a[i]<=bjs&&i<j)//這里是從左往右走
            i++;
        if(i<j)//當i,j還沒有相遇的時候
        {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    a[left]=a[i];//將比較數換到i,j相遇的位置
    a[i]=bjs;
    kspx(left,i-1);//下面使用遞歸進行下面的排序
    kspx(i+1,right);//使其排好
}
int main()
{
    int i,j;
    int n;
    scanf("%d",&n);//首序列長度
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    kspx(1,n);//快速排序函數
    for(i=1;i<=n;i++)//驗證結果
        printf("%d ",a[i]);
    return 0;
}

結果如下：

在這里插入圖片描述