第十一天、快速排序

一、题目:用快速排序法对一组数据由小到大进行排序,数据分别为99、45、12、36、69、22、62、796、4、696。 二、排序演示(摘自百度百科):     快速排序(Quicksort)是对冒泡排序的一种改进。     假设用户输入了如下数组:

下标

0

1

2

3

4

5

数据

6

2

7

3

8

9

    创建变量i=0(指向第一个数据), j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。     我们要把所有比k小的数移动到k的左面,所以我们可以开始寻找比6小的数,从j开始,从右往左找,不断递减变量j的值,我们找到第一个下标3的数据比6小,于是把数据3移到下标0的位置,把下标0的数据6移到下标3,完成第一次比较:

下标

0

1

2

3

4

5

数据

3

2

7

6

8

9

     i=0 j=3 k=6      接着,开始第二次比较,这次要变成找比k大的了,而且要从前往后找了。递加变量i,发现下标2的数据是第一个比k大的,于是用下标2的数据7和j指向的下标3的数据的6做交换,数据状态变成下表:

下标

0

1

2

3

4

5

数据

3

2

6

7

8

9

     i=2 j=3 k=6      接着,再递减变量j,不断重复进行上面的循环比较。     在本例中,我们进行一次循环,就发现i和j“碰头”了:他们都指向了下标2。于是,第一遍比较结束。得到结果如下,凡是k(=6)左边的数都比它小,凡是k右边的数都比它大:

下标

0

1

2

3

4

5

数据

3

2

6

7

8

9

    如果i和j没有碰头的话,就递加i找大的,还没有,就再递减j找小的,如此反复,不断循环。注意判断和寻找是同时进行的。     然后,对k两边的数据,再分组分别进行上述的过程,直到不能再分组为止。 注意:第一遍快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边。为了得到最后结果,需要再次对下标2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果。      示意图:

三、代码实现: 1、C语言代码:

/*第十一天、快速排序*/
#include <stdio.h>
#include <stdlib.h>
/*Quick_Sort函数声明*/
void Quick_Sort(int* pDataArray,int iDataStart,int iDataEnd);

void main(void)
{
    int a[10],i;
    printf("请输入10个数:\n");
    for(i = 0;i < 10;i++)
        scanf_s("%d",&a[i]);
    Quick_Sort(a,0,9);
    printf("排序后的顺序是:\n");
    for(i = 0;i < 10;i++)
        printf("%5d",a[i]);
    printf("\n");
    system("pause");
}

/*************************************
*函数名称:Quick_Sort                 *
*参数说明:pDataArray 无序数组       *
*          iDataStart 无序数组元素首 *
*           iDataEnd   无序数组元素尾 *
*说明:    快速排序                     *
**************************************/ 
void Quick_Sort(int* pDataArray,int iDataStart,int iDataEnd)
{
    int i,j;
    int iDataTemp;
    i = iDataStart;                                     //将每组首个元素赋给i
    j = iDataEnd;                                       //将每组末尾元素赋给j
    iDataTemp = pDataArray[iDataStart];                 //设置基准值
    while(i < j)
    {
        while((i < j) && (iDataTemp < pDataArray[j]))   //挑出比基准值还要小的元素的索引值
            j--;                                        //位置左移
        if(i < j)                                       //交换元素位置
        {
            pDataArray[i] = pDataArray[j];              //互换位置
            i++;                                        //位置右移
        }
        while((i < j) && (pDataArray[i] <= iDataTemp))  //挑出比基准值大于或者等于的元素的索引值
            i++;                                        //位置右移
        if(i < j)
        {
            pDataArray[j] = pDataArray[i];              //互换位置
            j--;                                        //位置左移
        }
    }
    pDataArray[i] = iDataTemp;                          //将基准值放入指定位置
    if(iDataStart < i)
        Quick_Sort(pDataArray,iDataStart,j - 1);        //对分割出的左边部分递归调用Quick_Sort函数
    if(i < iDataEnd)
        Quick_Sort(pDataArray,j + 1,iDataEnd);          //对分割出的右边部分递归调用Quick_Sort函数
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

map按key和按value排序

看一个题: 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 例示: jack 70...

2853
来自专栏python3

python 递归与高阶函数

在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。

944
来自专栏一个会写诗的程序员的博客

《一切皆是映射》哈希算法 (Hash)

「The Algorithm Design Manual」一书中提到,雅虎的 Chief Scientist ,Udi Manber 曾说过:

972
来自专栏Android知识点总结

06--图解数据结构之并查集

973
来自专栏mathor

KMP(1)

993
来自专栏小詹同学

Leetcode打卡 | No.22 括号生成

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

761
来自专栏华章科技

新手上路必学的Python函数基础知识,全在这里了(多段代码举例)

导读:函数是Python中最重要、最基础的代码组织和代码复用方式。根据经验,如果你需要多次重复相同或类似的代码,就非常值得写一个可复用的函数。通过给一组Pyth...

732
来自专栏java架构师

Stream篇(1)

最近在看一个写的很好的博客,为了加深记忆,把自认为重要的东西,一边看,一边记在这里 一、什么是流、字节序列、字节 一条河中有一条鱼游过,这条鱼就是一个字节,这个...

2847
来自专栏Java帮帮-微信公众号-技术文章全总结

Java 8 Lambda函数编程【面试+工作】

链接:https://pan.baidu.com/s/1q_S2URG8mWKI1nTvPVvDzg 密码:2als

1233
来自专栏机器学习从入门到成神

牛客网刷题汇总(一)附解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1702

扫码关注云+社区