第十一天、快速排序

一、题目:用快速排序法对一组数据由小到大进行排序,数据分别为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 条评论
登录 后参与评论

相关文章

来自专栏窗户

有限域(3)——多项式环的商环构造有限域

  接着上两章内容,我们还是得继续寻找有限域的构造方法。上章证明矩阵环是个单环,自然是没戏了,但我们还可以考虑多项式环。

34820
来自专栏数据结构与算法

字符串hash入门

简单介绍一下字符串hash 相信大家对于hash都不陌生 hash算法广泛应用于计算机的各类领域,像什么md5,文件效验,磁力链接 等等都会用到hash算法 在...

76450
来自专栏aCloudDeveloper

公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 ...

1.1K90
来自专栏大数据学习笔记

Java程序设计(Java9版):第3章 流程控制

第3章 流程控制 学习要点 掌握三种流程控制 掌握简单的输入输出 了解三种循环设计方法 掌握数组、字符串和枚举类型 3.1 面向过程介绍...

40870
来自专栏PPV课数据科学社区

【学习】基本排序算法及其在MapReduce的应用

 1 文档说明   该文档为学习基本排序算法过程中的学习笔记,大部分内容从网络上其他渠道也能得到,仅用于记录备忘之用。   冒泡、选择、插入三种作为基本的排序...

36360
来自专栏Java开发者杂谈

遍历算法(1)

遍历算法主要用在在处理迷宫问题,图,最短路径,以及枚举所有可能等问题上。下面我们通过一个简单的例子,来入门深度优先和广度优先算法: 1 package co...

39860
来自专栏dalaoyang

递归基础思想

18930
来自专栏C/C++基础

打印1到最大的n位数

这道题是面试过可能会遇到的手写代码题。如n为3时,那么需要打印1到999。需要注意的是当输入的n很大时,最大的n位数是不能通过int或者long long in...

7210
来自专栏决胜机器学习

《编程之美》读书笔记(一)——中国象棋将帅有效位置

《编程之美》读书笔记(一) ——中国象棋将帅有效位置 (原创内容,转载请注明来源,谢谢) 一、问题 ? 如上述棋盘,假设将为点A,帅为点B。将只能在d10...

42760
来自专栏Python小屋

哈夫曼编码原理与Python实现代码(附手动推导过程原稿真迹)

哈夫曼编码依据字符出现概率来构造异字头(任何一个字符的编码都不是其他字符的前缀)的平均长度最短的码字,通过构造二叉树来实现,出现频次越多的字符编码越短,出现频次...

78980

扫码关注云+社区

领取腾讯云代金券