Chinaunix首页 | 论坛 | 博客
  • 博客访问: 622899
  • 博文数量: 108
  • 博客积分: 46
  • 博客等级: 民兵
  • 技术积分: 1279
  • 用 户 组: 普通用户
  • 注册时间: 2012-08-16 11:36
个人简介

坐井以观天

文章分类

全部博文(108)

文章存档

2014年(13)

2013年(90)

2012年(6)

分类: 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);
}



 
lt 和 gt之间的就是下面中间花色区域 

 

< Key的区间


 

 

          = key的区间


 

 


        > key的区间


 

阅读(6456) | 评论(4) | 转发(2) |
0

上一篇:整理几道算法题

下一篇:B-树与mysql索引

给主人留下些什么吧!~~

joepayne2013-10-11 09:57:02

所以才有了针对“重复率较高”的快排优化算法    

回复 | 举报

mj8989172013-10-08 14:34:05

文明上网,理性发言...