C语言之快速排序案例详解

时间:2022-06-02 02:36:22

快速排序:是对冒泡排序算法的一种改进。

它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

例如有一个数字序列: 5 0 1 6 8 2 3 4 9 7
对其进行快速排序变为:0 1 2 3 4 5 6 7 8 9

思路如下:首先将要排序的序列的首个数字5定位比较数,这是一个参考对象!

然后的方法很简单:分别从序列的两端进行比较。先从右边往左边找比5小的数,再从左边往右边找大于5的数。当他们找到以后就需要停下来,然后交换它们。
在这里我们为了方便,将i定为左边,j为右边。

C语言之快速排序案例详解

C语言之快速排序案例详解

接下来继续前进,还是先从右边。
接下来得到的序列如下:
5 0 1 4 3 2 8 6 9 7

当它继续下去的时候我们可以知道这时,i,j相遇了。

这个时候,直接将比较数与相遇的数进行交换

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

可以看出,在右边的数都比比较数5大,左边的数都比比较数5小。

这个时候其实就是第一轮排序结束了。

下面的排序就是将左边与右边分别看成两个序列,然后与上面的一样进行排序。这里其实就是应用到了递归!

完整代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}

结果如下:

C语言之快速排序案例详解

总结:快速排序的优点是速度快,缺点是不稳定。

到此这篇关于C语言之快速排序案例详解的文章就介绍到这了,更多相关C语言之快速排序内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!

原文链接:https://blog.csdn.net/qq_52988578/article/details/115024035