坐井以观天
分类: C/C++
2013-10-07 15:28:07
前两天在看算法时,在一本算法书上看到快排的一种优化算法,觉得不错,这里就摘下来供大家分享和自个儿今后参考
之前我先说一下为什么有了这么一种算法,这种优化的算法是针对键值重复率比较高的序列,它会减少交换的次数
比如:性别,等级等
代码:
int QuikSort(int a[],int m,int n){
if( m >= n){
return 0;
}
key = a[m];
lt = m;
eq = m+1;
gt = n;
while( eq <= gt){
if( a[eq] > key){
a[eq] <-> a[gt];
gt--;
}
else if(a[eq] < key){
a[eq] <-> a[lt];
lt++;
eq++;
}
else{
eq++;
}
}
QuikSor(a,m,lt - 1);
QuikSort(a,gt+1,n);
}
< Key的区间 |
= key的区间 |
> key的区间 |