
C++快速排序
快速排序是基于分治思想的排序算法,通过这种策略把列表分为两个子列,重复该过程。是由东尼·霍尔提出,在平均状况下,排序N个数据要O(nlogn)次比较,在最坏情况下则需要O(n^2),但退化成冒泡的情况比较少见,快速排序比其他排序算法通常情况是最佳的,因为内部使用的循环在很多平台都有优化。
快速排序的步骤很简单:
- 选择一个基准
- 遍历列表,将小于基准的放在列表左边,大于基准的放在列表右边
- 递归这个操作
在维基百科上的这张图可以很直观的展示快速排序的过程。
代码实现:
首先需要一个返回基准的函数,该函数负责从指定的范围中挑选一个位置作为基准,并对范围内列表进行排序,并返回基准所在的位置。
int Division(int a[], int left, int right) { |
Division函数只做了最简单的事,找一个基准,并交换左右的元素,使列表左侧均小于基准元素,使右侧均大于基准元素,接下来需要一个函数,使列表趋向最小,直至列表元素剩一(这里我感觉其实有点极限的思想)。
void quick_sort(int a[], int left, int right) { |
配合上方的gif,就可以很清楚的了解快速排序是如何使用分治法来排序的,通过将大任务拆分成小任务,最终达成完整的排序.
本文是原创文章,采用CC BY-NC-SA 4.0协议,完整转载请注明来自小竹's blog
评论 ()