排序（四）排序优化

几种排序算法

排序算法的选择

虽然线性排序时间复杂度比较低，但是适用场景特殊条件苛刻，所以不能选用线性排序作为通用排序算法。

对于小规模数据可以选择时间复杂度为O(n2)的算法，在小规模数据面前，O(n2) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长；对于大规模的数据，可以选用时间复杂度为O(nlogn)的算法。为了兼顾任意规模的数据，会选择时间复杂度为O(nlogn)的算法，其中包括：归并排序、快速排序、堆排序等。

归并排序在平均、最坏时间复杂度上都为O(nlogn),但是归并排序不是原地排序，当需要排序的数据比较大时，就为占用额外过多内存，显然不合适。快速排序是原地排序，但最坏情况时间复杂度退化为O(n2)。

优化快速排序

分区点：选取分区点不够合理，导致数据全部分到一边，时间复杂度就会变为O(n2)，所以优化的关键在于分区点的选取。

• 三数取中法：取开头、结尾和中间数据，求平均值作为分区点
• 随机发：从概率学的角度，不太可能出现每次都选到最差分区点的情况

递归问题：快速排序是用递归实现的，递归过程中可能出现堆栈溢出。

• 限制递归深度
• 在堆上手动模拟一个函数调用栈，手动模拟递归入栈出栈，这样就没有栈大小限制（堆是内存中最大的一块）

排序（四）排序优化

原文：https://www.cnblogs.com/leduoi/p/13363551.html