快速排序

快速排序是对冒泡排序的一种改进。基本思想：通过一趟排序将待排序记录分割成两部分，一部分记录的关键字比另一部分的关键字小，然后继续对这两部分继续排序，达到整个有序。
通常选取第一个作为枢轴（支点），其他记录与这个值进行比较。

#include<stdio.h>
#define MAXSIZE 20
#define N 10
typedef int KeyType;
typedef char InfoType;
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ReadType;
typedef struct
{
    ReadType r[MAXSIZE+1];
    int length;
}Sqlist;
void InitSq(Sqlist * L);
void QuickSort(Sqlist *L);
void main()
{
    Sqlist Sqlist1;
    int i;
    InitSq( &Sqlist1);
    printf("请输入%d个数字用插入法进行排序\n",N-1);
    for(i=1;i<N;i++)//第i=0位留着作为哨兵
    {
        scanf("%d",&Sqlist1.r[i].key);
        Sqlist1.length++;
    }
    printf("排序前：\n");
        for(i=1;i<N;i++)
    {
        printf("%d ",Sqlist1.r[i].key);
    }

    QuickSort(&Sqlist1);

    printf("\n排序后：\n");
    for(i=1;i<N;i++)
    {
        printf("%d ",Sqlist1.r[i].key);
    }
    system("pause");
}
void InitSq(Sqlist * L)
{
    int i;
    for(i=0;i<=MAXSIZE;i++)
    {
        L->r[i].key=0;
        L->length=0;

    }
}

int Partition(Sqlist *L,int low,int high)
{
    int pivotkey;
    L->r[0]=L->r[low];//用第一个记录做枢轴记录
    pivotkey=L->r[low].key;

    while(low<high)
    {

        while((low<high)&&(L->r[high].key>=pivotkey))
         --high;
       L->r[low]=L->r[high];//比枢轴小的移动到低端

     while((low<high)&&(L->r[low].key<=pivotkey))
         ++low;
       L->r[high]=L->r[low];//比枢轴大的移动到高端
    }
    L->r[low]=L->r[0];//把最后空的位置赋值为枢轴记录

    return low;//返回枢轴位置

}
void QSort(Sqlist * L,int low,int high)
{
    int pivotloc;
    if(low<high)
    {
        pivotloc=Partition(L,low,high);
        QSort(L,low,pivotloc-1);
        QSort(L,pivotloc+1,high);
    }
}
void QuickSort(Sqlist *L)
{
    QSort(L,1,L->length);
}