博客

用c语言建立顺序表，实现快速排序。

这里是用了两个函数实现的，一个分割函数，一个递归。

#include<stdio.h>
#define ListSize 20
typedef int DataType;
typedef struct{
	DataType data[ListSize];
	int length;
}Seqlist;

Seqlist CreateList(Seqlist L)  //结构体变量作为函数的参数，修改之后的成员值不能返回到主调函数，不过可以return返回它
{
    int n;
    L.length=0;
    printf("输入顺序表的数据：输入-1结束\n");
	while(1)
    {
        scanf("%d",&n);
        if(n==-1) break;
        L.data[L.length]=n;
        L.length++;
    }
    return L;
}

void DisplayList(Seqlist *L)
{
    int i;
    for(i=0;i<L->length;i++)
    {
        printf("%d,",L->data[i]);
    }
    printf("\n");
}

int Patition(Seqlist *L,int low,int high)  //把顺序表一分为二，并且返回枢轴位置
{
    DataType pivotvalue=L->data[low];    //用第一个数作为枢轴，pivotvalue保存枢轴的值
    while(low<high)   //当low==high时两边相遇了，结束一趟排序
    {
        while(low<high&&L->data[high]>=pivotvalue)  //先从右往左找比pivotvalue小的数， 
                                                    //注意等号
            high--;
        L->data[low]=L->data[high];             //找到后放到前边

        while(low<high&&L->data[low]<=pivotvalue)  //从前往后找比pivotvalue大的数
            low++;
        L->data[high]=L->data[low];   //放到后边

    }
    L->data[low]=pivotvalue; //枢轴此时放到low和high相遇的地方
    return low;  //返回枢轴位置

}
void ListQSort(Seqlist *L,int low,int high)  //快排
{

    if(low<high)
    {
        int pivotlocation = Patition(L, low, high);
        ListQSort(L,low,pivotlocation-1);
        ListQSort(L,pivotlocation+1,high);
    }

}

int main()
{
    int i,n;
    Seqlist mylist;
    mylist=CreateList(mylist);

	DisplayList(&mylist);
	printf("长度：%d\n",mylist.length);
	ListQSort(&mylist,0,mylist.length-1);
	DisplayList(&mylist);
}

接着用一个函数来实现吧，原理是一样的，但是要注意low和high的初始值得保留。

void QuickSort(Seqlist *L,int low,int high)
{
    int i=low,j=high;  //low和high的位置待会递归的时候要用到，所以不能和上边一样直接修改
    DataType pivotvalue=L->data[i];  //注意这里要用data[i]
    if(low>=high)  //一趟排序结束
        return;   
    while(i<j)
    {
        while(i<j&&L->data[j]>=pivotvalue)
            j--;
        L->data[i]=L->data[j];
        while(i<j&&L->data[i]<=pivotvalue)
            i++;
        L->data[j]=L->data[i];
    }
    L->data[i]=pivotvalue;
    QuickSort(L,low,i-1);
    QuickSort(L,i+1,high);
}