打开网易新闻 查看精彩图片

排序算法一直是c语言重点，各个算法适应不用的环境，同时，在面试时，排序算法也是经常被问到的。今天我们介绍下快速排序，简称就是快排。

1.快速排序思想:

快排使用分治法(Divide and conquer)策略，将一个序列分为两个子序列。(快排算法中使用到了递归，对递归不太熟的，可以参考我前一篇文章)。具体步骤如下:

①从数列中挑出一个元素，称为"基准"(Pivot)；

②重新排序数列，所有元素比基准小的摆放在最前面，所有元素比基准值大的放在基准的后面(相同的数可以放在任意一边)。在这个分区结束之后，该基准就处于数列的中间位置。如上操作便称为"分区(Partition)"操作。

③递归的把小于基准值元素的子数列和大于基准值的子数列排序。

2.快速排序注意点:

①递归的最底部情形，是数列的大小是0或1，也就是永远都已经被排序好了。

②虽然一直会递归，但是不用担心，这个算法总会结束。毕竟在每次迭代中，至少会把一个元素摆到它最后的位置去。

③快排时间复杂度为：O(nLog n);

3.快速排序代码实现:

①数据结构部分:

打开网易新闻 查看精彩图片

② 快速排序递归部分:

打开网易新闻 查看精彩图片

③寻找"基准"部分:

打开网易新闻 查看精彩图片

④ main函数调用:

打开网易新闻 查看精彩图片