快速排序：一种高效的排序算法

禁默

发布于 2025-12-20 18:47:08

330

前言

排序是最基本和最常用的操作之一。无论是数据处理、搜索优化，还是各种应用程序的内部逻辑，排序算法的选择都直接影响到程序的性能。快速排序（Quick Sort）作为一种典型的分治算法，以其平均时间复杂度 O(n log n) 和优越的实际表现，成为了现代编程中最常用的排序算法之一。本篇博客将详细讲解快速排序。

一、快速排序的基本思想

快速排序采用了分治的策略。基本思想如下： 1.从数组中选择一个“基准元素”（通常选择数组的第一个元素、最后一个元素，或者随机选择一个元素）。 2.将数组分成两部分：小于基准元素的部分和大于基准元素的部分。 3.分别对这两部分继续递归进行排序。 4.最终得到一个有序数组。

二、快速排序的算法步骤

假设我们有一个数组，快速排序的过程如下：

1.选择基准元素：选择一个元素作为基准，通常是数组的第一个元素（或最后一个，或随机选取）。 2.分割过程：对数组进行重新排列，使得所有比基准元素小的元素排在基准元素的左侧，所有比基准元素大的元素排在右侧。 3.递归排序：递归地对基准元素左边和右边的子数组进行排序，直到子数组大小为1。

三、C++实现快速排序

代码展示

#include <iostream>
#include <vector>

using namespace std;

// 分割函数，将数组分成两部分，左边小于基准，右边大于基准
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选择基准元素为最后一个元素
    int i = low - 1; // i指向小于基准的区域的最后一个元素
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]); // 将小于基准的元素交换到左边
        }
    }
    swap(arr[i + 1], arr[high]); // 将基准元素放到正确的位置
    return (i + 1); // 返回基准元素的最终位置
}

// 快速排序函数
void quickSort(vector<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() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    
    cout << "原数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    
    quickSort(arr, 0, n - 1);
    
    cout << "排序后的数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

代码解析

1.partition函数：这个函数负责将数组根据基准元素分割成两部分，返回基准元素的最终位置。在分割过程中，数组的两部分分别由小于基准元素和大于基准元素的元素构成。

pivot = arr[high]：选择最后一个元素作为基准元素。 for (int j = low; j <= high - 1; j++)：遍历数组，将小于基准元素的元素交换到数组的左侧。 swap(arr[i + 1], arr[high])：最后，将基准元素放到正确的位置，确保它左边的元素都小于它，右边的元素都大于它。

2.quickSort函数：这个函数实现了递归过程。它会对分割后的左右子数组继续调用 quickSort 函数，直到子数组的大小为1时递归停止。

3.main函数：这里定义了一个包含整数的数组，调用 quickSort 函数进行排序，并输出排序前后的数组。

四、C语言实现快速排序

代码展示

#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指向小于基准的区域的最后一个元素
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);  // 将小于基准的元素交换到左边
        }
    }
    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]);
    
    printf("原数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    quickSort(arr, 0, n - 1);
    
    printf("排序后的数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

代码解析 1.swap函数：用于交换两个元素的位置。在快速排序中，经常需要交换数组中的元素，因此这是一个非常常用的辅助函数。

2.partition函数：这是快速排序的核心函数。它将数组重新排列，使得所有小于基准元素的元素位于基准元素的左侧，所有大于基准元素的元素位于右侧。 pivot = arr[high]：选择数组的最后一个元素作为基准元素。 for (int j = low; j <= high - 1; j++)：遍历数组，将小于基准元素的元素交换到左边。 swap(&arr[i + 1], &arr[high])：将基准元素放到正确的位置，确保它左边的元素都小于它，右边的元素都大于它。 3.quickSort函数：实现了递归排序的功能。它会递归地对基准元素左边和右边的子数组进行排序，直到子数组的大小为1时停止递归。

4.main函数：定义了一个包含整数的数组，调用 quickSort 函数进行排序，并输出排序前后的数组。