蓝桥杯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 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

7565
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

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

java.sql.SQLException: connection holder is null

java.sql.SQLException: connection holder is null

1341
来自专栏WOLFRAM

向日葵中的数学之美

1843
来自专栏Petrichor的专栏

Dataset 列表:机器学习研究

In computer vision, face images have been used extensively to develop face recog...

1521
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2322
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9784
来自专栏c#开发者

XML Encryption in .Net

XML Encryption in .Net One of the new features being introduced with the Whidbey...

4377
来自专栏marsggbo

Udacity并行计算课程 CS344 编程作业答案

832

扫码关注云+社区