思想:从待排序记录序列中选取一个记录(通常选取第一个记录)为枢轴其关键字设为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]中,就完成了一次划分过程。最后对子表进行递归调用排序函数进行排序。
测试代码如下所示:
- #include<stdio.h>
- int QuikPos(int a[],int low,int high)
- {
- int t=a[low];
- while(low<high)
- {
- while(low<high&&a[high]>=t)//high从右到左找小于t的记录
- high--;
- if(low<high)//找到小于t的记录则进行交换
- {
- a[low]=a[high];
- low++;
- }
- while(low<high&&a[low]<t)//low从左向右找大于t的记录
- low++;
- if(low<high) //找到则交换
- {
- a[high]=a[low];
- high--;
- }
- }
- a[low]=t; //将基准元素保存到low=high的位置
- return low;
- }
- void QuikSort(int a[],int low,int high)
- {
- int pos;
- if(low<high)
- {
- pos=QuikPos(a,low,high);
- QuikSort(a,low,pos-1);
- QuikSort(a,pos+1,high);
- }
-
- }
- int main()
- {
- int i;
- int a[100];
- int length;
- printf("请输入元素个数 :\n");
- scanf("%d",&length);
- printf("请输入元素 :\n");
- for(i=0;i<length;i++)
- scanf("%d",&a[i]);
- printf("\n");
- printf("输入的元素如下所示 :\n");
- for(i=0;i<length;i++)
- printf("%3d",a[i]);
- printf("\n");
- QuikSort(a,0,length-1);
- printf("则经过排序后的元素如下所示 :\n");
- for(i=0;i<length;i++)
- printf("%3d",a[i]);
- printf("\n");
- return 0;
- }
阅读(915) | 评论(0) | 转发(0) |