中年C/C++编程笔记：快速排序的思路与优化改进 |编程|笔记|

本文中的代码适用于对数组元素进行排序（以整型数据为例）。
自定义的方法在排序方法之前，定义了三个不同的方法，以便于对数组元素进行比较和交换。为了适用于不同的数据类型，这里使用到了 void 指针以及指针类型的转换，也就是 C 语言中范型的概念。如果需要对不同元素类型的数组进行排序，只修改 LessArr() 方法和 Less() 方法即可。

本文插图
未改进的快速排序基本快速排序
基本快速排序的切分方法中，针对于切分的标志元素（这里是数组的首元素），通过自身与数组中其他元素不断交换位置来达到切分目的。

本文插图
后交换快速排序
后交换快速排序同样是使用了很多次交换方法，不过对于基本快速排序来说，交换次数明显减少。因为切分的标志元素总是在大循环结束之后进行的，也就是说在前面的交换里，没有将自身加进来，这样就达成了使用更少的交换次数得到同样效果的目的。

本文插图
非交换快速排序
非交换快速排序中并没有使用到前面的交换方法，它是通过事先保存切分标志元素的内容，重复进行前后赋值来实现的。

本文插图
几种改进的策略
乱序处理
为了确保数组中数据的随机性，我们可以对数组进行乱序处理。或者随机在数组中选取一个元素作为枢轴（pivot）来对数组进行划分。
三取样切分快速排序
三取样切分也就是三位取中的方法，一般是将数组的首、尾以及中间元素的中位数作为切分元素。为了达到更好的切分效果，也可以选择随机在数组中寻找三个元素，用它们的中位数元素作为枢轴（pivot）进行数组元素的切分。这里我选择了将首、尾以及中三个元素进行比较，将中位元素置于首位，再调用之前完成的未改进方法。

本文插图
三向切分快速排序（熵最优的排序）
在实际应用中可能会出现数据重复次数很多的情况，这就具有很大的改进潜力，我们可以将当前实现的线性对数级的性能提高到线性级别。一个简单的思路就是将数组切分为三个部分。

本文插图
排序方法的调用

本文插图
完整代码

本文插图

本文插图

本文插图

本文插图

本文插图

本文插图
本次文章的分享就到这里了，希望对大家有帮助！
自学C/C++编程难度很大，不妨和一些志同道合的小伙伴一起学习成长！