【C/C++】快速按大小排序数组的函数

阅读原文：【C/C++】快速按大小排序数组的函数

概要

C/C++ 中有时候需要对数组进行排序，而使用 #define 定义 MAX() 这一方法并不明智。因此在这里列出一个简要的解决方案，备忘后续使用。

排序数组中升序和降序排序在同一函数中，但在本段代码同时存在升序和降序的调用。

代码片段

使用变量说明

• 在下面的代码中，pivot 定义了数组元素最右侧为基准点。
• i 变量用于记录比基准点小（或大）的元素的索引；确保交换后的数组中，i 左边的元素都比基准点小（或等于），i 右边的元素都比基准点大（或等于）。
• pi 变量存储 partition 函数返回的基准点索引。目的是用于递归调用 quickSort 函数，对基准点两侧的子数组进行排序。
• low 和 high 变量表示数组的起始和结束索引。它们控制排序范围，确保递归进行时子数组的边界。
• ascending 变量用于选择使用升序或降序对数组进行排列。ascending 非零时为升序，为零时为降序。

使用函数说明

sizeof 函数

sizeof 是一个运算符，用于计算变量占用的字节空间大小。在本段代码中，sizeof(arr) 计算整个数组 arr 的大小（以字节为单位）。arr[0] 代表数组 arr 的第一个元素。其中，类似 sizeof(arr[0]) 的表达计算数组中单个元素的大小（以字节为单位）。

而本段代码利用 sizeof 避开在使用中因需求而不断修改表示数组大小的变量 n，而是使用程序自动计算引用比较大小的数组内元素数量。

下面主函数中使用的公式，sizeof(arr) / sizeof(arr[0]) 表示数组的总大小除以单个元素的大小，从而得到数组中元素的个数。

【举例】如果 sizeof(arr) 是 24 字节，sizeof(arr[0]) 是 4 字节，那么 24 / 4 = 6，因此 n 的值是 6，即数组中有6个元素。

片段解读

首先是一个快速划分函数，通过以最右侧元素为基准点，以较小元素为索引，快速划分整个数组为两部分，随后运用循环代码对两部分数组进行分别排序。

int partition(int arr[], int low, int high, int ascending) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if ((ascending && arr[j] <= pivot) || (!ascending && arr[j] >= pivot)) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

然后是快速排序函数，通过递归算法将整个数组完成排序：

void quickSort(int arr[], int low, int high, int ascending) {
    if (low < high) {
        int pi = partition(arr, low, high, ascending);
        quickSort(arr, low, pi - 1, ascending);
        quickSort(arr, pi + 1, high, ascending);
    }
}

在主函数中定义或引用数组，调用 QuickSort 函数进行排序。在调用过程中，ascenting 为 1 时函数按升序排序，为 0 时按降序排序：

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 排序数组，升序
    quickSort(arr, 0, n - 1, 1);

    // 输出排序后的数组
    printf("升序排列：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 排序数组，降序
    quickSort(arr, 0, n - 1, 0);

    // 输出排序后的数组
    printf("降序排列：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

完整代码

完整代码如下：

#include <stdio.h>

// 快速排序中的划分函数
int partition(int arr[], int low, int high, int ascending) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if ((ascending && arr[j] <= pivot) || (!ascending && arr[j] >= pivot)) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

// 快速排序函数
void quickSort(int arr[], int low, int high, int ascending) {
    if (low < high) {
        int pi = partition(arr, low, high, ascending);
        quickSort(arr, low, pi - 1, ascending);
        quickSort(arr, pi + 1, high, ascending);
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 排序数组，升序
    quickSort(arr, 0, n - 1, 1);

    // 输出排序后的数组
    printf("升序排列：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 排序数组，降序
    quickSort(arr, 0, n - 1, 0);

    // 输出排序后的数组
    printf("降序排列：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}