四川
分享至
排序算法一直是c语言重点，各个算法适应不用的环境，同时，在面试时，排序算法也是经常被问到的。今天我们介绍下快速排序，简称就是快排。
1.快速排序思想:
快排使用分治法(Divide and conquer)策略，将一个序列分为两个子序列。(快排算法中使用到了递归，对递归不太熟的，可以参考我前一篇文章)。具体步骤如下:
①从数列中挑出一个元素，称为"基准"(Pivot)；
②重新排序数列，所有元素比基准小的摆放在最前面，所有元素比基准值大的放在基准的后面(相同的数可以放在任意一边)。在这个分区结束之后，该基准就处于数列的中间位置。如上操作便称为"分区(Partition)"操作。
③递归的把小于基准值元素的子数列和大于基准值的子数列排序。
2.快速排序注意点:
①递归的最底部情形，是数列的大小是0或1，也就是永远都已经被排序好了。
②虽然一直会递归，但是不用担心，这个算法总会结束。毕竟在每次迭代中，至少会把一个元素摆到它最后的位置去。
③快排时间复杂度为：O(nLog n);
3.快速排序代码实现:
①数据结构部分:
② 快速排序递归部分:
③寻找"基准"部分:
④ main函数调用:
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
