C语言编码实现快速排序算法

快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略。它的基本思想是：

从数列中挑出一个元素作为基准（pivot）。
将所有比基准小的元素移到基准的左边，所有比基准大的元素移到基准的右边。
对基准左右两边的子序列重复上述步骤，直到整个序列有序。

下面是一个使用 C 语言实现快速排序算法的示例：

#include <stdio.h>

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 分区操作，返回基准的索引
        int pivotIndex = partition(arr, low, high);
        
        // 递归对基准左边的子数组进行快速排序
        quickSort(arr, low, pivotIndex - 1);
        
        // 递归对基准右边的子数组进行快速排序
        quickSort(arr, pivotIndex + 1, high);
    }
}

// 分区函数，选择最后一个元素作为基准
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择基准
    int i = low - 1; // 小于基准的元素的最右边索引

    for (int j = low; j < high; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++; // 增加索引
            // 交换 arr[i] 和 arr[j]
            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 printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: \n");
    printArray(arr, size);
    
    quickSort(arr, 0, size - 1);
    
    printf("排序后的数组: \n");
    printArray(arr, size);
    return 0;
}

代码解释

quickSort 函数：

接受数组 arr、起始索引 low 和结束索引 high。
首先检查 low < high 是否成立，确保至少有两个元素需要排序。
调用 partition 函数分区数组，并获取基准元素的正确位置 pivotIndex。
然后递归调用 quickSort 对基准左边和右边的子数组进行排序。
partition 函数：

选择数组的最后一个元素作为基准（也可以选择其他策略，例如随机选择或中位数）。
使用索引 i 来标记小于或等于基准的区域的最后一个位置。
遍历数组，将小于或等于基准的元素移到左边。
最后，将基准元素放到正确的位置，并返回该位置的索引。
printArray 函数：

辅助函数，用于打印数组元素。
main 函数：

定义一个整数数组并初始化。
打印原始数组。
调用 quickSort 进行排序。
打印排序后的数组。

示例输出

原始数组:
10 7 8 9 1 5
排序后的数组:
1 5 7 8 9 10

注意事项

时间复杂度：

平均情况下，快速排序的时间复杂度为 O(n log n)。
最坏情况下（例如，数组已经是有序的，并且每次选择的基准都是最大或最小元素），时间复杂度为 O(n²)。为避免这种情况，可以使用随机化快速排序，即随机选择基准元素。
空间复杂度：

快速排序是一个原地排序算法，空间复杂度为 O(log n)（递归调用栈的深度）。
稳定性：

快速排序不是一个稳定的排序算法，因为相等元素的相对位置可能会改变。
该博文为原创文章，未经博主同意不得转载。本文章博客地址：https://pythonking.blog.csdn.net/article/details/144964544