快速排序分区法

// 通过指针交换两个元素的值
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
/****************************************************************
 * name；subzone
 * function：part zone
 * parameter；
 *              @int arr[]
 *              @int left
 *              @int right
 * ReValue；int j
 * author；小北blog
 * attention；none
 * date；2024.06.01
 * history；
 * version；
 * Copyright(c) 2024 [email protected] All rights reserved
 *****************************************************************/
// 分区方案
int subzone(int arr[], int left, int right)
{
    int fir_ele = arr[left]; // 使用第一个元素作为基准
    int i = left;
    int j = right + 1;
    // 循环找到比基准值大小的值
    while (i < j)
    {
        // 从右侧找到第一个比基准值小的值
        do
        {
            j--;
        } while (arr[j] > fir_ele);
        // 从左侧找到第一个比基准值大的值
        do
        {
            i++;
        } while (arr[i] < fir_ele);
        // 如果i和j相遇，则分区完成
        if (i < j) // 条件不满足交换基准值和arr[j]
        {
            // 交换arr[i]和arr[j]
            swap(&arr[i], &arr[j]);
        }
    }
    // 交换基准值和arr[j]
    swap(&arr[left], &arr[j]);
    return j;
}

/****************************************************************
 * name；quickSort
 * function：sort
 * parameter；
 *              @int arr[]
 *              @int left
 *              @int right
 * ReValue；none
 * author；小北blog
 * attention；none
 * date；2024.06.01
 * history；
 * version；
 * Copyright(c) 2024 [email protected] All rights reserved
 *****************************************************************/
// 快速排序函数
void quickSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int j = subzone(arr, left, right);
        quickSort(arr, left, j - 1);
        quickSort(arr, j + 1, right);
    }
}

// 打印数组
void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数
int main()
{
    int arr[] = {66, 77, 44, 11, 99, 55};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原来的数组: \n");
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

运行结果：

总结：首先要确定的是快速排序的思路，就是以一个数组为一个区，第一个元素为基准值，通过操作两端的数值交换来实现快速排序的目的。
QuickSort的函数的思想，在调用分区函数subzone的时候，利用基准值最后交换后数组中所占的位置为返回值，对原数组进行分区，在利用该参数进行分左右区。
既然分区就要知道分区需要的三个参数，已知数组+数组首元素位置+数组为元素位置（数组大小-1）。
而分区函数的思想就是该空间的第一个元素的值作为基准值，从右侧找到第一个比基准值小的值，从左侧找到第一个比基准值大的值，让其交换。直到左右的值的位置也就是下标相遇，则退出该循环，基准值归位，返回基准值下标作为下次分区左区的尾元素下标和作为下次分区右区的首元素下标。最后交给QuickSort函数循环调用自身。
但是该函数递归使用的内存资源过大，属于空间换时间的例子，空间复杂度根据排列数组的，相对于该代码而言，左值越多越大，那么空间复杂度就越高，所以该代码稳定性差，理想的空间复杂度为O(logN)