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

相关文章

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

156. 合并区间先排序再处理

给出若干闭合区间,合并所有重叠的部分。 样例 给出的区间列表 => 合并后的区间列表:

1413
来自专栏程序员互动联盟

八大排序算法

排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说...

3578
来自专栏chenjx85的技术专栏

leetcode-166-分数到小数(用余数判断有没有出现小数的循环体)

给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以字符串形式返回小数。

4675
来自专栏玄魂工作室

Python算法与数据结构--求所有子数组的和的最大值

题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。

1132
来自专栏人工智能LeadAI

排序算法:Python 实现

import sys print (sys.version) # 3.5.2 |Continuum Analytics, Inc.| (default, J...

36910
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度中经常看到的一...

36411
来自专栏AI派

Numpy 修炼之道 (2)—— N维数组 ndarray

ndarray中的每个元素在内存中使用相同大小的块。 ndarray中的每个元素是数据类型对象的对象(称为 dtype)。

3486
来自专栏chenjx85的技术专栏

leetcode-908-最小差值 I

给定一个整数数组 A,对于每个整数 A[i],我们可以选择任意 x 满足 -K <= x <= K,并将 x 加到 A[i] 中。

1572
来自专栏老九学堂

常用排序算法总结

一种是比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。

1373
来自专栏TensorFlow从0到N

讨厌算法的程序员 7 - 归并排序的时间复杂度分析

? 递归树 上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度...

2496

扫码关注云+社区