第十一天、快速排序

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

相关文章

来自专栏和蔼的张星的图像处理专栏

174. 删除链表中倒数第n个节点双指针

给定一个链表,删除链表中倒数第n个节点,返回链表的头节点。 样例 给出链表1->2->3->4->5->null和 n = 2. 删除倒数第二个节点之后,...

502
来自专栏决胜机器学习

PHP数据结构(二十二) ——快速排序

PHP数据结构(二十二)——快速排序 (原创内容,转载请注明来源,谢谢) 一、概述 前面的插入排序,都是以移动的方式进行排序。快速排序,则是以交换的方式进行...

3569
来自专栏desperate633

详解排序算法--堆排序选择排序堆排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩...

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

几种有关排序的常见面试问题

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

672
来自专栏Python专栏

浅尝Python快速排序

964
来自专栏IT可乐

Java数据结构和算法(九)——高级排序

  春晚好看吗?不存在的!!!   在Java数据结构和算法(三)——冒泡、选择、插入排序算法中我们介绍了三种简单的排序算法,它们的时间复杂度大O表示法都是O(...

3436
来自专栏恰同学骚年

数据结构基础温故-7.排序

排序(Sorting)是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序,特别是高效率地进行排序时计算...

611
来自专栏决胜机器学习

PHP数据结构(二十) ——其他插入排序

PHP数据结构(二十)——其他插入排序 (原创内容,转载请注明来源,谢谢) 注:本文是衔接直接插入排序的,因此直接插入排序的相关内容请点击——PHP...

3127
来自专栏静默虚空的博客

单链表的C++实现(采用模板类)

采用模板类实现的好处是,不用拘泥于特定的数据类型。就像活字印刷术,制定好模板,就可以批量印刷,比手抄要强多少倍! 此处不具体介绍泛型编程,还是着重叙述链表的定义...

1917
来自专栏用户画像

7.4.2 选择排序之堆排序

堆排序是一个树形选择排序方法,它的特点是:在排序过程中,将L[1...n]看成是一棵完全二叉树的顺序存储结构,

504

扫码关注云+社区