【数据结构】快速排序

这个实验其实在课本上写得蛮详细的,稍微看看就能理解。

#include <stdio.h>

#define MAXSIZE 20
typedef struct {
    int r[MAXSIZE + 1];
    int length;
}SqList;//定义排序列表

//交换任意a和b的值
void Exchange(int &a, int &b)
{
    int c = a;
    a = b;
    b = c;
}

//确定枢轴,并且进行以枢轴为界对列表进行分割
int Partition(SqList &L, int low, int high)
{
    L.r[0] = L.r[low];//为监视哨赋值
    while (low < high)
    {
        while (low < high&&L.r[high] >= L.r[0])high--;
        Exchange(L.r[low], L.r[high]);
        while (low < high&&L.r[low] <= L.r[0])low++;
        Exchange(L.r[low], L.r[high]);
    }
    L.r[high] = L.r[0];
    return low;//返回分割点(枢轴)
}

//递归缩小列表的分割长度,直至排序完毕
void QSort(SqList &L, int low, int high)
{
    if (low < high)
    {
        int pivotloc = Partition(L, low, high);
        QSort(L, low, pivotloc - 1);
        QSort(L, pivotloc + 1, high);
    }
}

//对整个列表执行快速排序
void QuickSort(SqList &L)
{
    QSort(L, 1, L.length);
}

void main()
{
    SqList L;
    printf("请输入要排序的数组长度:(1~20)\n");
    scanf("%d", &L.length);
    printf("请依次输入要排序的数组元素:(用逗号隔开)\n");
    //数组的第一个元素为监视哨,应无实际值,所以这里要从1开始赋值
    for (int i = 1; i < L.length + 1; i++)scanf("%d,", &L.r[i]);
    QuickSort(L);
    printf("排序结果:\n");
    for (int i = 1; i < L.length + 1; i++)
    {
        printf("%d,", L.r[i]);
    }
    putchar('\n');
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据