专栏首页小文博客蓝桥杯C语言知识点补充——快速排序详解

蓝桥杯C语言知识点补充——快速排序详解

今天刚准备更新一道习题的,结果发现有些知识点生疏了不少,今天就更新2个知识点吧。

可以说是非常好的算法

快速排序

简介

快速排序(Quicksort)是对冒泡排序的一种改进。

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

原理图

在快速排序算法中,使用了分治策略。首先把序列分成两个子序列,递归地对子序列进行排序,直到整个序列排序结束。

步骤如下:

在序列中选择一个关键元素做为轴;

对序列进行重新排序,将比轴小的元素移到轴的前边,比轴大的元素移动到轴的后面。在进行划分之后,轴便在它最终的位置上;

递归地对两个子序列进行重新排序:含有较小元素的子序列和含有较大元素的子序列。

下面的动画展示了快速排序算法的工作原理。

代码

void sort(int *a, int left, int right) {     if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/     {         return ;     }     int i = left;     int j = right;     int key = a[left];           while(i < j)                               /*控制在当组内寻找一遍*/     {         while(i < j && key <= a[j])         /*而寻找结束的条件就是,1,找到一个小于或者大于key的数(大于或小于取决于你想升         序还是降序)2,没有符合条件1的,并且i与j的大小没有反转*/          {             j--;/*向前寻找*/         }                   a[i] = a[j];         /*找到一个这样的数后就把它赋给前面的被拿走的i的值(如果第一次循环且key是         a[left],那么就是给key)*/                   while(i < j && key >= a[i])         /*这是i在当组内向前寻找,同上,不过注意与key的大小关系停止循环和上面相反,         因为排序思想是把数往两边扔,所以左右两边的数大小与key的关系相反*/         {             i++;         }                   a[j] = a[i];     }           a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/     sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/     sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/                        /*当然最后可能会出现很多分左右,直到每一组的i = j 为止*/ }

1234567891011121314151617181920212223242526272829303132333435363738

void sort(int *a, int left, int right){    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/    {        return ;    }    int i = left;    int j = right;    int key = a[left];         while(i < j)                               /*控制在当组内寻找一遍*/    {        while(i < j && key <= a[j])        /*而寻找结束的条件就是,1,找到一个小于或者大于key的数(大于或小于取决于你想升        序还是降序)2,没有符合条件1的,并且i与j的大小没有反转*/         {            j--;/*向前寻找*/        }                 a[i] = a[j];        /*找到一个这样的数后就把它赋给前面的被拿走的i的值(如果第一次循环且key是        a[left],那么就是给key)*/                 while(i < j && key >= a[i])        /*这是i在当组内向前寻找,同上,不过注意与key的大小关系停止循环和上面相反,        因为排序思想是把数往两边扔,所以左右两边的数大小与key的关系相反*/        {            i++;        }                 a[j] = a[i];    }         a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/                       /*当然最后可能会出现很多分左右,直到每一组的i = j 为止*/}

视频详解

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 素数对猜想——《C语言代码笔记》

    神无月
  • 十进制转换二进制(C语言)

    神无月
  • WordPress友链排序插件——链接排序(已汉化)

    神无月
  • 聊聊nacos的TcpSuperSenseProcessor

    nacos-1.1.3/naming/src/main/java/com/alibaba/nacos/naming/healthcheck/TcpSuperSe...

    codecraft
  • 聊聊nacos的TcpSuperSenseProcessor

    nacos-1.1.3/naming/src/main/java/com/alibaba/nacos/naming/healthcheck/TcpSuperSe...

    codecraft
  • wepy框架入门

    使用微信开发者工具新建项目,本地开发选择dist目录。 微信开发者工具 --> 项目 --> 关闭ES6转ES5。 本地项目根目录运行wepy build ...

    达达前端
  • 软体机器人或可由“喷墨打印”制造

    美国普渡大学的科研人员日前利用喷墨打印技术制造出液体合金设备,这一新工艺可用于大规模生产柔性可伸展导体,直至软体机器人。 ? 据物理学家组织网站4月8日(北京时...

    机器人网
  • C#线程的使用(二):检测线程的结束

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    bering
  • Python之递归

    3.递归效率不高,递归层次过多会导致栈溢出(在计算机中,函数调用时通过栈(stack)这种结构数据实现的,每当进入一个函数调用栈就会多一层栈帧,每当函数返回,栈...

    py3study
  • redis的repl-ping-slave-period和repl-ping-replica-period

    网上很多Redis方面的文章,会涉及到repl-ping-slave-period和repl-ping-replica-period这两个重要参数,从一些中...

    一见

扫码关注云+社区

领取腾讯云代金券