快速排序入门（C语言学习笔记）

前言

这篇文章面向刚刚入门编程的同学，我将尽可能地简化我的表述，让这篇文章内容变得清晰易懂。

在进入到正文之前，我们要首先明白，编程是为了解决问题的。为了高效地处理某些特定类型、结构的问题，各种各样的“算法”应运而生。排序算法也是如此，它们要解决的是将一个混乱（不单调）的数列整理成一个整齐（单调递增或单调递减）的数列。

快速排序思想介绍

本来打算让文心一言写一下这一块内容的，但改了几次 prompt 都写不好，还是算了。
H
排序算法有很多种，比如冒泡排序、选择排序、桶排序、归并排序等等，但这些排序没有一个敢在名字里宣称自己“快速”。那么我们可想而知，快速排序自然有他的奇特之处。在这里，我们先不研究凭啥快速排序能拿下“快速”的名号，我们来仔细看看他奇妙的思想。

快速排序以分治思想为基础，分治是计算机解决问题（当然人也是）的一个重要手段。所以在介绍快速排序之前，我们要先简单了解一下分治思想。

分治思想

分治，也即“分而治之”。顾名思义，就是把一个问题拆解成几个小问题去解决。当一个任务过于复杂的时候，我们可以尝试对他进行拆解。拆解一遍不够，就再拆一遍，直到拆解出来的问题能够轻而易举地解决。举个例子，对一个数列进行排序，看起来确实很复杂，但我们可以把这个数列拆解成两个数列，将他们分别排序，再进行合并；拆解出来的两个数列再进行拆解，这个操作一直进行下去，最后就变成了两个数之间的比较，这就是分治思想在发挥作用（上面提到的这个想法其实是归并排序的思路）。

需要注意的是，分治过程中，问题的形式一般不会发生变化，我们往往是在减小问题的规模（像上面这个例子，同样是对数列进行排序，但是数列的长度在不断减小，直到变成了两个数的比较，这个时候所谓的排序就变成了单纯的比较，这就是量变引起质变）。

快速排序思想

排序的目的是让整个数列变得有序，“有序”，也就是单调递增或者单调递减。这是很严格的结果，因为对于任意位置都需要满足“前一个数小于等于他”和“后一个数大于等于他”（以单调递增为例）。

我们不妨尝试着把目光集中在整个数列中的一个数上。对于一个单调递增有序数列中的某个数来说，他左边的数都小于他，他右边的数都大于他。假如我们倒过来想呢？

对于一个数列，我们研究它中间的某个数。如果这个数左边的数都比它小，而这个数右边的数都比它大，那么它就有可能是一个单调递增的数列。我们规定对于数列 $a{i} i = mid a{mid - 1} \leq a{mid} \leq a{mid + 1} MM$ 是数列单调递增的必要不充分条件。

量变引起质变的理论在这里又发挥了它的作用：当这个数列足够短（数列中只有3个数字）的时候，性质 将会成为该数列单调递增的充分必要条件，这点是显然的。也就是说，只要这个数列的规模足够小，我就可以轻而易举地完成这个问题。于是分治思想就可以派上用场了：我们不妨来思考下怎么把大问题拆解成小问题。

我们已经知道：对于一个长度为3的数列，如果它满足性质 ，那么它就是一个单调递增数列。假设我们现在有两个数列，均满足性质 ，如下：

数列一 1 2 3
数列二 5 6 7

假如我们再找一个中间数 4 ,然后把数列一和数列二放在它的两侧（1 2 3 在左侧，5 6 7 在右侧），这个时候，这个新形成的数列也满足性质

我们不难发现这个新数列是一个单调递增的数列。在这个过程中我们会获得启发：如果一个数列满足性质 ，把它从中间劈开，它左右两个子数列也满足性质 ，再把左右两个子数列劈开……直到最后形成的子数列也满足性质 ，我们就可以说这个数列是单调递增的。

于是我们就可以得到分治的策略：对于一个数列，先把他从中间劈开，把所有比它中间数大的数移到右侧，把所有比它中间数小的数移到左侧，然后再对中间数左右两个数列进行同样的操作，直到最后需要进行操作的数列长度为3，将它整理完成后，这个数列就是单调递增的了。

我们通过一个例子来更清晰地了解这个过程：

:::tip EXAMPLE
对数列一 13 9 1 5 7 3 12 6 17 执行快速排序
原始数列一 13 9 1 5 7 3 12 6 17
首先找到中间数字（中间指的是位置在中间）为 7 那么把比 7 大的都移到右边，把比 7 小的都移到左边：
整理数列一 3 6 1 5 7 13 12 17 9
这个时候数列一显然已经满足性质 了，现在我们要继续整理 7 左右的子数列：

原始数列二 3 6 1 5
找到中间数字 6 （当然选取 1 也行，这个无伤大雅，不影响结果）
整理数列二 3 1 5 6
我们发现这里 6 左侧还剩下 3 1 5 ，显然再进行整理就能得到 1 3 5 这样一个有序数列

原始数列三 13 12 17 9
找到中间数字 12
整理数列三 9 12 17 9 13
我们发现这里 12 右侧还剩下 17 9 13 ， 显然再进行整理就能得到 9 13 17 这样一个有序数列

那么把每一步整理汇总回去就能得到一个完全有序的数列了。
:::

快速排序参考代码

#include <stdio.h>  
  
// 交换两个元素的位置  
void swap(int* a, int* b) {  
    int temp = *a; 
    *a = *b;  
    *b = temp;  
}  
  
// 找到基准元素的正确位置  
int partition(int arr[], int low, int high) {  
    int pivot = arr[high];  // 选择数组的最后一个元素作为基准  
    int i = (low - 1);  // 定义指向低位的指针i，初值为low-1  
    for (int j = low; j <= high - 1; j++) {  // 遍历数组，从低位到高位  
        if (arr[j] < pivot) {  // 如果当前元素小于基准  
            i++;  // 将i指针后移一位  
            swap(&arr[i], &arr[j]);  // 将arr[j]和arr[i]交换位置，保证比基准小的元素都在基准的左侧  
        }  
    }  
    swap(&arr[i + 1], &arr[high]);  // 最后将基准元素放到正确的位置上  
    return (i + 1);  // 返回基准的索引位置  
}  
  
// 递归实现快速排序  
void quickSort(int arr[], int low, int high) {  
    if (low < high) {  // 如果低位不等于高位，说明还有待排序的元素  
        int pi = partition(arr, low, high);  // 对数组进行分割，并得到基准的索引位置pi  
        quickSort(arr, low, pi - 1);  // 对基准左边的部分进行递归排序  
        quickSort(arr, pi + 1, high);  // 对基准右边的部分进行递归排序  
    }  
}  
  
int main() {  
    int arr[] = {10, 7, 8, 9, 1, 5};  // 定义待排序的数组  
    int n = sizeof(arr) / sizeof(arr[0]);  // 计算数组的元素个数n  
    quickSort(arr, 0, n - 1);  // 对数组进行快速排序  
    printf("Sorted array: ");  // 打印排序结果的前缀  
    for (int i = 0; i < n; i++) {  // 遍历数组，逐个打印元素  
        printf("%d ", arr[i]);  // 打印当前元素和一个空格  
    }  
    printf("\n");  // 打印换行符，结束输出  
    return 0;  // 主函数返回0，表示程序正常结束  
}