快速排序算法

思想：从待排序记录序列中选取一个记录(通常选取第一个记录)为枢轴其关键字设为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;
}

阅读(4237) | 评论(0) | 转发(3) |

0

上一篇：堆排序算法

下一篇：二分查找排序