快排改进算法
最近研究快排，对快排对低熵数据的效率很不满意，于是研究了对快排平均效率的提高的问题。
快排处理有序数据时，仍需要进行划分，一分到底，尤其是大部分数据集中在一个集合中，使快排退化为了冒泡。传统做法是在数据中任取一数作为划分轴，该法确实大大提高了快排的平均效率，但是这样仍不能达到对于已排序数据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[low] >= data[high]){
if (data[low] > data[(low + high) / 2]) swap(&data[low], &data[(low + high) / 2]); else if(data[high] > data[(low + high) / 2]) swap(&data[low], &data[high]); }
else{
if(data[high] < data[(low + high) / 2]) swap(&data[low], &data[high]); else if(data[low] < data [(low + high) / 2]) swap(&data[low], &data[(low + high) /2]); }//对data[low],data[high],data[(low + high) / 2]取中值与data[low]交换
//此处不推荐使用时间随机函数，因为好的随机函数本身有很大的时间复杂度
int key = data[low], countl = 0, counth = 0, n = high, m = low;//countl,counth分别对
low子表与high子表数据交换情况计数
int *temh = boh, *teml = bol;
while(low < high){
while(low < high && data[high] >= key){
if(high < n)
if(data[high] > data[high + 1]){
//进行冒泡操作
swap(&data[high], &data[high + 1]);
//对交换操作进行计数
counth = 1;
}
--high;//移动指针
}
data[low] = data[high];//交换高低指针数据
while(low < high && data[low] <= key){
if(low > m)
if(data[low - 1] > data[low]){
//进行冒泡操作
swap(&data[low - 1], &data[low]);
//对交换操作进行计数
countl = 1;
}
++low;//移动指针
}
data[high] = data[low];//交换高低指针数据
}
data[low] = key;
*temh = counth;
*teml = countl;
return low;
}
void qsort(int data[], int low, int high){
//定义递归实现qsort函数
if(low == high) return;//递归终点
else{
int bol,boh;
int key = partition(data, low, high, &bol, &boh);
if(bol ^ 0) qsort(data, low, key - 1);//根据标记判断是否对low子表进行操作 if(boh ^ 0) qsort(data, key + 1, high);//根据标记判断是否对high子表进行操作 return;
}
}
本文档为【快排改进算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483