快捷導(dǎo)航

C語(yǔ)言之快速排序案例詳解

更新時(shí)間：2021年07月30日 08:43:44 作者：小尹同學(xué)⁣

這篇文章主要介紹了C語(yǔ)言之快速排序案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

快速排序：是對(duì)冒泡排序算法的一種改進(jìn)。

它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

例如有一個(gè)數(shù)字序列： 5 0 1 6 8 2 3 4 9 7
對(duì)其進(jìn)行快速排序變?yōu)椋? 1 2 3 4 5 6 7 8 9

思路如下：首先將要排序的序列的首個(gè)數(shù)字5定位比較數(shù)，這是一個(gè)參考對(duì)象！

然后的方法很簡(jiǎn)單：分別從序列的兩端進(jìn)行比較。先從右邊往左邊找比5小的數(shù)，再?gòu)淖筮呁疫呎掖笥?的數(shù)。當(dāng)他們找到以后就需要停下來(lái)，然后交換它們。
在這里我們?yōu)榱朔奖?，將i定為左邊，j為右邊。

在這里插入圖片描述

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

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

這個(gè)時(shí)候，直接將比較數(shù)與相遇的數(shù)進(jìn)行交換

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

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

這個(gè)時(shí)候其實(shí)就是第一輪排序結(jié)束了。

下面的排序就是將左邊與右邊分別看成兩個(gè)序列，然后與上面的一樣進(jìn)行排序。這里其實(shí)就是應(yīng)用到了遞歸！

完整代碼如下：

#include<stdio.h>
int a[100];//這里將數(shù)組a定義為全局變量，方便后面使用
void kspx(int left,int right)
{
    int i,j;
    int t,bjs;//bjs就是指開(kāi)頭的比較數(shù)
    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)//當(dāng)i,j還沒(méi)有相遇的時(shí)候
        {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    a[left]=a[i];//將比較數(shù)換到i,j相遇的位置
    a[i]=bjs;
    kspx(left,i-1);//下面使用遞歸進(jìn)行下面的排序
    kspx(i+1,right);//使其排好
}
int main()
{
    int i,j;
    int n;
    scanf("%d",&n);//首序列長(zhǎng)度
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    kspx(1,n);//快速排序函數(shù)
    for(i=1;i<=n;i++)//驗(yàn)證結(jié)果
        printf("%d ",a[i]);
    return 0;
}

結(jié)果如下：

在這里插入圖片描述