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

 

今天刚准备更新一道习题的,结果发现有些知识点生疏了不少,今天就更新2个知识点吧。
可以说是非常好的算法

快速排序

简介

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

原理图

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

步骤如下:

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

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

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

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

 

代码

 

视频详解


点赞

发表评论

在发表评论前请确认您的言论中没有违反中国各项法律、法规和违背社会道德的内容。任何无意义的留言内容都会被直接删除。

上传图片