C语言递归实现快速排序

Question

递归法快速排序

有些测试用例可以正确输出，有些不可以

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

int fun(int a[], int i, int j)
{
    int num = a[0];
    int t;
    int r = j;
    i = i + 1;
    if (i < j) 
    {
        while (i < j)
        {
                while ((a[i] <= num )&& (i < j))
                {
                    i++;                
                }
                while ((a[j] >= num )&& (j > i))
                {
                    j--;
                }
                t = a[i];
                a[i] = a[j];
                a[j] = t;
        }
        if (a[0] >= a[i])
        {
            a[0] = a[i];
            a[i] = num;
        }
        else
        { 
            a[0] = a[i-1];
            a[i-1] = num;
        }
            fun(a, 0, i);
            fun(a, j+1 , r);
            return a[i];    
    }
    else
        return;
        
}
int main()
{
    int a[20]={ 0 };
    int i = 0;
    printf("递归排序\n");
    int MAX;
    printf("请输入数字的个数");
    scanf_s("%d", &MAX);
    for (i = 0; i < MAX; i++)
    {
        printf("第%d个数：", i + 1);
        scanf_s("%d", &a[i]);
    }
    fun(a, 0, MAX - 1);
    printf("排列后数组为\n");
    for (i = 0; i < MAX; i++)
        printf("%d", a[i]);
    system("pause");
    return 0;
}

两个测试用例一个错（1）一个对(2)
1递归排序
请输入数字的个数5
第1个数：4
第2个数：7
第3个数：8
第4个数：1
第5个数：4
排列后数组为
14874请按任意键继续. . .

2递归排序
请输入数字的个数5
第1个数：8
第2个数：5
第3个数：7
第4个数：4
第5个数：1
排列后数组为
14578请按任意键继续. . .

我已经改崩溃了，实在不知道哪里错了，请大家帮忙看一看。

Answer 1

#include <iostream>
#include <ctime>
#include <vector>
using namespace std;

class MySort
{
public:
    //快速排序递归实现
    void static QuickSortRecursion(vector<int> &nums)
    {
        if (nums.empty())
            return;
        QuickSort(nums, 0, nums.size() - 1);
    }

    //快速排序迭代实现
    void static QuickSortIteration(vector<int> &nums)
    {
        if (nums.empty())
            return;
        //定义一个数组用来存储数组的左右边界
        //模拟栈存储的过程
        int *stack = new int[nums.size()];
        int left = 0;
        int high = nums.size() - 1;
        int cursor = 0;
        int pivot = 0;
        //模拟向栈里面存储数组的左右边界
        //指针cursor始终指向下一个要存储的位置
        stack[cursor++] = left;
        stack[cursor++] = high;
        while (cursor != 0)
        {
            //由于指针始终指向下一个存储位置，因此这里要先--后才能得到正确的数据
            high = stack[--cursor];
            left = stack[--cursor];
            if (left < high)
            {
                pivot = Partition(nums, left, high);
                if (pivot - 1 > left)
                {
                    stack[cursor++] = left;
                    stack[cursor++] = pivot - 1;
                }
                if (pivot + 1 < high)
                {
                    stack[cursor++] = pivot + 1;
                    stack[cursor++] = high;
                }
            }
        }
        delete[] stack;
    }

private:
    //快速排序递归实现，具体过程
    void static QuickSort(vector<int> &nums, int left, int right)
    {
        if (left >= right)
            return;
        int pivot = Partition(nums, left, right);

        //以下操作就将支点处的值从以后的排序中剔除
        QuickSort(nums, left, pivot - 1);
        QuickSort(nums, pivot + 1, right);
    }

    //划分数据段，使左侧数据小于支点处数据，右侧数据大于支点处数据
    //真正实现的排序的核心部分，其余部分只是在划分排序的区间
    //处理的数据区间为闭区间[left,right]
    int static Partition(vector<int> &nums, int left, int right)
    {
        int index = rand() % (right - left) + left;
        int low = left;
        int high = right;
        swap(nums[index], nums[right]);
        while (low < high)
        {
            while (low < high && nums[right] >= nums[low])
            {
                ++low;
            }
            while (low < high && nums[right] <= nums[high])
            {
                --high;
            }
            if (low < high)
            {
                swap(nums[low], nums[high]);
            }
        }
        //支点处的值不需要再进行排序了，交换完成后，支点处的值就处于正确的位置上。
        swap(nums[high], nums[right]);
        //返回的支点所在的索引
        return high;
    }
};

int main(void)
{
    srand((unsigned int)time(NULL));
    int arr[20] = {};
    //随机生成长度为20的数组
    for (int i = 0; i < 20; ++i)
    {
        arr[i] = rand() % 20;
    }
    vector<int> nums(arr, arr + sizeof(arr) / sizeof(int));
    //MySort::QuickSortIteration(nums);
    MySort::QuickSortRecursion(nums);
    for (auto item : nums)
    {
        cout << item << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}

试试这个