前言

一种将无序数组进行排序的方法。

快速排序，参杂了冒泡排序的交换思想。

wiki参考：
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

本文只提及了递归方式的实现，该算法整体类似于二叉树，普通的迭代方法反而更加复杂。

环境

编辑器：vs2019
文件：.c类型

正文

代码参考：

#include <stdio.h>

// 快速排序，主要思想：1. 取基值。2. 分割（基值左小右大）

void swap(int* x, int* y) {
    int t = *x;
    *x = *y;
    *y = t;
}


// start: 起始索引
// end: 结束索引
void quick_sort_recursive(int source_array[], int start, int end)
{
    if (start >= end)
    {
        return 0;
    }

    // 取基值
    // source_array[end];

    // 确定分割数组的索引
    int left = start;
    int right = end - 1;

    // 开始分割
    while (left < right)
    {
        // 从左向右找到比基值大的数
        while (source_array[left] < source_array[end])
        {
            left++;
        }

        // 从右向左找到比基值小的数
        while (source_array[right] > source_array[end])
        {
            right--;
        }

        // 交换两个元素
        if (left < right)
        {
            swap(&source_array[left], &source_array[right]);
            left++;
            right--;
        }

    }
    // 最后移动基值。循环结束以后，left指向 从左向右,第一个大于等于基值的值
    if (left < end)
    {
        swap(&source_array[left], &source_array[end]);
    }

    quick_sort_recursive(source_array, start, left - 1);
    quick_sort_recursive(source_array, left + 1, end);
}


int main()
{
    // 生成随机测试列表
    int test_list[30];
    int test_list_length = sizeof(test_list) / sizeof(int);
    printf("测试列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        test_list[i] = rand() % 100;
        printf("%d ", test_list[i]);
    }
    printf("\n");


    // 递归快速排序
    quick_sort_recursive(test_list, 0, test_list_length - 1);
    printf("递归快速排序结果： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    return 0;
}

执行结果参考：

image.png