Chinaunix首页 | 论坛 | 博客
  • 博客访问: 629958
  • 博文数量: 140
  • 博客积分: 2635
  • 博客等级: 少校
  • 技术积分: 1353
  • 用 户 组: 普通用户
  • 注册时间: 2010-06-04 15:46
文章分类
文章存档

2015年(2)

2014年(12)

2013年(10)

2012年(10)

2011年(85)

2010年(21)

分类:

2012-05-30 09:44:25

原文地址:快速排序算法 作者:hfm_honey

思想:从待排序记录序列中选取一个记录(通常选取第一个记录)为枢轴其关键字设为k1,然后将其余关键字小于k1的记录移到前面去,而将关键字大于k1的记录移到后面,结果将待排序序列分成了两个子表最后将关键字为k1的记录查到其分界线的位置处.
算法步骤:假设待划分序列为r[left],r[left+1],.......r[right],具体实现上述划分过程时,可以设两个指针i和j,他们的初值分别为left,right.首先将基准记录r[left]移至变量x中,是r[left],即r[i]相当于空单元,然后反复进行如下两个扫描过程,直到i和j相遇
(1)j从右向左扫描,直到r[j].key
(2)i从左向后扫描,直到r[i].key>x.key时,将r[i]移至空单元r[j],此时r[i]相当于空单元。
当i和j相遇时,r[i](或r[j])相当与空单元,且r[i]左边所有记录的关键字均不大于基准记录的关键字,而r[i]右边所有记录的关键字均不小于基准记录的关键字,最后将基准记录移至r[i]中,就完成了一次划分过程。最后对子表进行递归调用排序函数进行排序。
测试代码如下所示:

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. int QuikPos(int a[],int low,int high)
  3. {
  4.     int t=a[low];
  5.     while(low<high)
  6.     {
  7.         while(low<high&&a[high]>=t)//high从右到左找小于t的记录
  8.             high--;
  9.         if(low<high)//找到小于t的记录则进行交换
  10.         {
  11.             a[low]=a[high];
  12.             low++;
  13.         }
  14.         while(low<high&&a[low]<t)//low从左向右找大于t的记录
  15.             low++;
  16.         if(low<high) //找到则交换
  17.         {
  18.             a[high]=a[low];
  19.             high--;
  20.         }
  21.     }
  22.     a[low]=t; //将基准元素保存到low=high的位置
  23.     return low;

  24. }
  25. void QuikSort(int a[],int low,int high)
  26. {
  27.     int pos;
  28.     if(low<high)

  29.     {
  30.         pos=QuikPos(a,low,high);
  31.         QuikSort(a,low,pos-1);
  32.         QuikSort(a,pos+1,high);
  33.     }
  34.     
  35. }
  36. int main()
  37. {
  38.     int i;
  39.     int a[100];
  40.     int length;
  41.     printf("请输入元素个数 :\n");
  42.     scanf("%d",&length);
  43.     printf("请输入元素 :\n");
  44.     for(i=0;i<length;i++)
  45.     scanf("%d",&a[i]);
  46.     printf("\n");


  47.     printf("输入的元素如下所示 :\n");
  48.     for(i=0;i<length;i++)
  49.         printf("%3d",a[i]);
  50.     printf("\n");

  51.     QuikSort(a,0,length-1);
  52.     printf("则经过排序后的元素如下所示 :\n");
  53.     for(i=0;i<length;i++)
  54.         printf("%3d",a[i]);
  55.     printf("\n");
  56.     return 0;
  57. }

阅读(915) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~