切换到宽版
  • 21323阅读
  • 26回复

[原创]快排改进算法 [复制链接]

上一主题 下一主题
离线大壮
 
只看楼主 正序阅读 0 发表于: 2007-03-11
最近研究快排,对快排对低熵数据的效率很不满意,于是研究了对快排平均效率的提高的问题。

快排处理有序数据时,仍需要进行划分,一分到底,尤其是大部分数据集中在一个集合中,使快排退化为了冒泡。传统做法是在数据中任取一数作为划分轴,该法确实大大提高了快排的平均效率,但是这样仍不能达到对于已排序数据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;
}
}

好不容易调出来了,因为疏忽,把l和h搞反了,调了两晚上才弄出来,无语……再也不犯低级错误了!·¥#%!

在ms vs 2003 vc++下调试通过,时间问题没有与改进前算法比较效率,有兴趣的测试一下吧
离线yonghu86cs
只看该作者 26 发表于: 2008-02-21
??????
离线绝世衰神
只看该作者 25 发表于: 2008-02-01
高手,顶~
天生我材必有用
老鼠儿子会打洞
离线xyj
只看该作者 24 发表于: 2008-01-06
楼上的,不要搞之乎者也了~~
实际上真正比赛时如果都可以的话我肯定会用选择,因为很好记~
离线sai901013
只看该作者 23 发表于: 2008-01-06
回 21楼(xyj) 的帖子
冒泡乃不可取者也........插排吧...
离线sai901013
只看该作者 22 发表于: 2008-01-06
恭喜LZ....被 谷型所殺.........

管理員...........還要貼齣 CPU.內存....
离线xyj
只看该作者 21 发表于: 2008-01-04
个人感觉要看做题时的数据量,如果数据量太大用快速排序、希尔可能更好,如果一般的话用选择、冒泡应付一下也可以了。
离线tzwangzy
只看该作者 20 发表于: 2007-12-08
FPC里有现成的程序
离线tzwangzy
只看该作者 19 发表于: 2007-12-08
不过,快排很好
离线tzwangzy
只看该作者 18 发表于: 2007-12-08
不懂
快速回复
限100 字节
 
上一个 下一个