注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天涯倦客的博客

祝福你朋友永远快乐!

 
 
 

日志

 
 

装载:C/C++:编程实现快速排序  

2011-03-08 14:40:01|  分类: C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
源代码如下:
void quick_sort(int a[], int low, int high)
{
int i, j, pivot;
if (low < high)
{
pivot = a[low];
i = low;
j = high;
while(i<j)
{
while(i<j && a[j]>=pivot)
j--;

if(i<j)
a[i++]=a[j];     //将比pivot小的元素移到低端

while(i<j && a[i]<=pivot)
i++;

if(i<j)
a[j--] = a[i];    //将比pivot大的元素移到高端
}
a[i] = pivot;             //pivot移到最终位置
quick_sort(a, low, i-1);   //对左区间递归排序
quick_sort(a, i+1, high);  //对右区间递归排序
}
    }

这里pivot代码基准值,它的初始值为a[low]。局部变量i和j分别代表low和high的位置。接着按照下面的步骤进行一趟交换
    (1)把比pivot的元素移到低端(low)
    (2)把比pivot大的元素移到高端(high)
    (3)pivot移到最终位置,此时这个位置的左边元素的值都比pivot小,而其右边元素的值都比pivot大。
    (4)对左、右区间分别进行递归排序。从而把前三步的粗排序逐渐的细化,直至最终low和high交汇。
    测试程序如下:
int main() 
{
  int data[9]={54,38,96,23,15,72,60,45,83};
    quick_sort(data, 0, 8); //快速排序
   
for(int i=0;i<9;i++)
              cout<<data[i]<< " ";//打印排序后的数组
return 0;
}
  评论这张
 
阅读(422)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017