快速排序

快速排序，平均时间复杂度为O(nlogn)，最坏的情况下，时间复杂度为O(n²)

【输入描述】

输入两行。第一行输入数组大小 n ，第二行输入 n 个数字。

【输出描述】

输出一行。输出排序后的数字。

【输入样例】

8
7 13 4 5 8 1 11 9
【输出样例】

1 4 5 7 8 9 11 13
【参考程序】

//小牛编程
#include <iostream>
using namespace std;
int arr[10001];

// 升序：数组划分为两部分，返回基准元素索引
int partition(int arr[], int left, int right) {
    int base = arr[left];
    while (left < right) {
        // right指针从右向左进行比较
        while (left < right && arr[right] > base) { //降序改成 <
            right--;
        }
        arr[left] = arr[right];

        // left指针从左向右进行比较
        while (left < right && arr[left] < base) { //降序改成 >
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = base;
    return left;
}

// 函数用于实现快速排序
void quickSort(int arr[], int left, int right) {
    if (left < right) {
        // 划分数组，获取基准元素的索引
        int baseIndex = partition(arr, left, right);

        // 对基准元素左右两侧的子数组递归排序
        quickSort(arr, left, baseIndex - 1);
        quickSort(arr, baseIndex + 1, right);
    }
}

int main() {
    int n;
    cin >> n;

    // 输入数组元素
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 快速排序（升序）
    quickSort(arr, 0, n - 1);

    // 排序结果
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

经典算法

快速排序