C++ 快速排序算法实现及实验分析

快速排序是一种高效的排序算法，它利用分治的思想，将一个数组分成两个子数组，然后对子数组进行排序，最后合并起来得到有序数组。

实验步骤

定义一个快速排序函数，函数名为 quickSort，参数为一个整数数组和数组的起始索引和结束索引。
在 quickSort 函数中，选择一个基准元素（一般选择数组的第一个元素），将数组分为两部分，小于等于基准元素的放在左边，大于基准元素的放在右边。
递归调用 quickSort 函数对左右两部分进行排序。
重复步骤 2 和步骤 3，直到每个子数组只剩下一个元素，即结束递归。
在主函数中，定义一个整数数组，并初始化。
调用 quickSort 函数对整个数组进行排序。
打印排序后的数组。

C++ 代码示例

#include <iostream>
using namespace std;

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = arr[low]; // 设定基准元素
        int i = low, j = high;
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = pivot; // 将基准元素放入正确的位置
        quickSort(arr, low, i - 1); // 递归调用对左半部分进行排序
        quickSort(arr, i + 1, high); // 递归调用对右半部分进行排序
    }
}

int main() {
    int arr[] = {9, 5, 7, 2, 1, 6, 3, 8, 4}; // 定义并初始化整数数组
    int n = sizeof(arr) / sizeof(arr[0]); // 数组长度

    cout << "原始数组：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    quickSort(arr, 0, n - 1); // 调用快速排序函数进行排序

    cout << "排序后的数组：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

实验总结

通过实验可知，快速排序是一种高效的排序算法，利用分治的思想，将一个数组分成两个子数组，然后对子数组进行排序，最后合并起来得到有序数组。快速排序的时间复杂度为 O(nlogn)，在平均情况下具有较好的性能。实验中的代码实现了快速排序算法，并对一个整数数组进行了排序。