STM32的HAL库开发系列 - 常用的用户库代码 - 快速排序

快速排序算法

快速排序是一种高效的排序算法，它的基本思想是分治。分治的思想是将一个复杂的问题分成两个或更多的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

快速排序的基本思想是，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

在快速排序算法中，选取基准元素是非常重要的。一般来说，我们可以选取第一个元素作为基准元素，也可以选取最后一个元素作为基准元素，也可以选取中间元素作为基准元素，还可以随机选取一个元素作为基准元素。

算法过程

在快速排序中，选取第一个元素作为基准元素，然后使用两个指针i和j将数组分成三部分，其中左边部分的元素都小于基准元素，右边部分的元素都大于基准元素，中间部分的元素等于基准元素。

具体的实现过程如下：

首先在数组中选取一个基准元素，通常是第一个元素。
使用两个指针i和j，分别指向数组的第一个元素和最后一个元素。
从右往左扫描，如果发现比基准元素小的元素，就把它交换到左边的位置。
从左往右扫描，如果发现比基准元素大的元素，就把它交换到右边的位置。
重复上述过程直到i和j相遇。
把基准元素放到i和j相遇的位置。

这样，就把原数组分成了三部分，其中第一部分小于基准元素，第三部分大于基准元素，第二部分等于基准元素。

接下来，对第一部分和第三部分分别进行快速排序，递归地对子数组进行排序，直到整个数组有序。

详细的代码如下：

void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) 
                j--;  
            if(i < j) 
                s[i++] = s[j];
            while(i < j && s[i] < x) 
                i++;  
            if(i < j) 
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1); 
        quick_sort(s, i + 1, r);
    }
}

该代码中，参数s[]为待排序数组，l和r分别为数组的左右边界。首先判断数组长度是否为0或1，若是则无需排序。否则，选取数组的第一个元素作为基准元素x，然后使用两个指针i和j将数组分成三部分，其中左边部分的元素都小于x，右边部分的元素都大于x，中间部分的元素等于x。最后递归地对左边和右边的子数组进行快速排序，直到整个数组有序。

在上述代码中，第一重循环是主要的排序过程，其中i指针从左向右移动，j指针从右向左移动，当s[i]大于等于x时，j指针向左移动，当s[j]小于x时，i指针向右移动，当i<j时，交换s[i]和s[j]的值，继续移动i和j。循环结束后，s[i]的值一定等于x，这样就把数组分成了两部分，一部分元素小于x，一部分元素大于等于x。

然后递归地对左边和右边的子数组进行快速排序，直到整个数组有序。

总的来说快排的时间复杂度为 O(nlogn)，是一种高效的排序算法。

那么如何让代码更加简洁一些呢？可以参考接下来我的这段代码

void Quick_Sort(int16_t q[], int16_t l, int16_t r, bool_t order)
{
    if (l >= r) return;
    int16_t i = l - 1, j = r + 1, x = q[(l + r) >> 1];
    while (i < j) {
        if (order) {
            do i ++ ; while (q[i] < x);
            do j -- ; while (q[j] > x);
        } else {
            do i ++ ; while (q[i] > x);
            do j -- ; while (q[j] < x);
        }
        if (i < j) {
            int16_t k = q[i];
            q[i] = q[j];
            q[j] = k;
        }
    }
    Quick_Sort(q, l, j, order), Quick_Sort(q, j + 1, r, order);
}