最近研究快排，对快排对低熵数据的效率很不满意，于是研究了对快排平均效率的提高的问题。
快排处理有序数据时，仍需要进行划分，一分到底，尤其是大部分数据集中在一个集合中，使快排退化为了冒泡。传统做法是在数据中任取一数作为划分轴，该法确实大大提高了快排的平均效率，但是这样仍不能达到对于已排序数据O(n)的时间效率。那么，还有什么办法改进呢？
我们发现，主要问题集中在传统快排无法对数据整体进行判断，所有情况都按照熵最高处理，那么，只要在快排中加入数据分析，就可以避免遇到低熵数据仍进行大量运算。
那么，我们在划分函数中，在high与low移动至中间时，比较相邻两个数据大小，并按照顺序进行交换，类似于冒泡法，并定义两个变量，对low与high是否交换过进行计数。若没有交换过，则表明该部分数据已经有序，在qsort函数递归时，不必再对low或high进行操作，即不必对low或high进行递归。这样，就大大减少了递归次数，降低了时间复杂度。如此一来，传统情况下的最差情况，似乎就成了最好情况，由O(n^2)变成了O(n)。
c版源代码：
void swap(int *px, int *py){
//定义交换函数
int temp;
temp = *px;
*px = *py;
*py = temp;
}
int partition(int data[], int low, int high, int *bol, int *boh){
//定义划分函数
if(data >= data){
if (data > data[(low + high) / 2]) swap(&data, &data[(low + high) / 2]);
else if(data > data[(low + high) / 2]) swap(&data, &data);
}
else{
if(data < data[(low + high) / 2]) swap(&data, &data);
else if(data < data [(low + high) / 2]) swap(&data, &data[(low + high) /2]);
}//对data,data,data[(low + high) / 2]取中值与data交换
//此处不推荐使用时间随机函数