实现给定数组的快速排序

题目描述

内容要求：

1. 以菜单的形式作为用户界面，接收待排序的输入序列，使用快速排序的方法对输入序列进行快速排序。
2. 测试数据：
   80，43，18，21，30，13，52，51，75

题目分析

快速排序是通过递归或非递归实现的，其中对于单趟PartSort也有三种不同的算法，这三种不同的算法效率没有差异，通常是通过递归实现快速排序，非递归需要借助栈或队列，这里展示的是递归版、前后指针法实现快速排序，如果有其他需求可以看此文章自行寻找所需算法

数据结构---手撕图解排序(含动图演示)

#include <stdio.h>
#include <stdlib.h>

void PrintArrey(int* a, int n)
{
   
    for (int i = 0; i < n; i++)
    {
   
        printf("%d ", a[i]);
    }
    printf("\n");
}

void Swap(int* a, int* b)
{
   
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int PartSort(int* a, int left, int right)
{
   
    int cur = left + 1;
    int prev = left;
    int keyi = left;
    while (cur <= right)
    {
   
        if (a[cur] < a[keyi])
        {
   
            ++prev;
            Swap(&a[prev], &a[cur]);
        }
        cur++;
    }

    Swap(&a[prev], &a[keyi]);

    return prev;
}


void QuickSort(int* a, int begin, int end)
{
   
    if (begin >= end)
    {
   
        return;
    }
    int keyi = PartSort(a, begin, end);

    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

void menu()
{
   
    printf("*****************************\n");
    printf("********* 1. Sort **********\n");
    printf("********* 0. exit  **********\n");
    printf("*****************************\n");
}

void CheckCapacity(int* a, int num, int* capacity)
{
   
    if (num > *capacity)
    {
   
        int* tmp = (int*)realloc(a, sizeof(int) * num);
        if (tmp == NULL)
        {
   
            perror("realloc fail");
            return;
        }
        a = tmp;
        *capacity = num;
    }
    else
    {
   
        return;
    }
}

void Sort()
{
   
    int capacity = 10;
    int* a = (int*)malloc(sizeof(int) * capacity);
    if (a == NULL)
    {
   
        perror("malloc fail");
        return;
    }
    int num;
    printf("输入要输入元素的个数->");
    scanf("%d", &num);
    CheckCapacity(a, num, &capacity);
    printf("输入对应个数的元素->");
    for (int i = 0; i < num; i++)
    {
   
        scanf("%d", &a[i]);
    }
    QuickSort(a, 0, num - 1);
    printf("排序完成:\n");
    PrintArrey(a, num);
    free(a);
    a = NULL;
}

int main()
{
   
    int input = 0;
    do
    {
   
        menu();
        scanf("%d", &input);
        switch (input)
        {
   
        case 1:
            Sort();
            break;
        case 0:
            break;
        default:
            printf("输入错误 重新输入\n");
        }
    } while (input);
}