C++

$\color{#cc33ff}{— > 算法基础课题解}$

思路：

快速排序

$模板题$

$基本思想：$

$1、在待排序的n个元素任取一个元素作为基准，把该元素放入最终位置后，整个数据序列被基准分为两个子序列。$

$2、所有小于基准的元素放在前子序列中，所有大于基准的元素放在后子序列中，并把基准放在这两个子序列的中间。$

$3、然后分别对两个子序列重复上述过程，直到每个子序列只有一个元素或空为止。$

$时间复杂度：O(nlog_2n)$

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n,q[N];

// 快排取分界点
// 取 中间点 情况1：

void quick_sort(int q[], int l, int r){
    // 快排 基于 分治 思想
    if (l >= r) return ;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];

    while(i < j){
        do i ++; while (q[i] < x);
        do j --; while (q[j] > x);
        if (i < j) swap (q[i], q[j]);
    }
    quick_sort (q, l, j);
    quick_sort (q, j + 1, r);
}

// 取 中间点 情况2

// void quick_sort(int q[], int l, int r){
//     // 快排 基于 分治 思想
//     if (l >= r) return ;
//     int i = l - 1, j = r + 1, x = q[(l + r + 1) / 2];

//     while(i < j){
//         do i ++; while (q[i] < x);
//         do j --; while (q[j] > x);
//         if (i < j) swap (q[i], q[j]);
//     }
//     quick_sort (q, l, i - 1);
//     quick_sort (q, i, r);
// }

// 取左节点

// void quick_sort(int q[], int l, int r){
//     // 快排 基于 分治 思想
//     if (l >= r) return ;
//     int i = l - 1, j = r + 1, x = q[l];

//     while(i < j){
//         do i ++; while (q[i] < x);
//         do j --; while (q[j] > x);
//         if (i < j) swap (q[i], q[j]);
//     }
//     quick_sort (q, l, j);
//     quick_sort (q, j + 1, r);
// }

//取右节点

// void quick_sort(int q[], int l, int r){
//     // 快排 基于 分治 思想
//     if (l >= r) return ;
//     int i = l - 1, j = r + 1, x = q[r]; 

//     while(i < j){
//         do i ++; while (q[i] < x);
//         do j --; while (q[j] > x);
//         if (i < j) swap (q[i], q[j]);
//     }
//     quick_sort (q, l, i - 1);
//     quick_sort (q, i, r);
// }

int main(){
    scanf("%d", &n);

    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);

    quick_sort(q, 0 , n - 1);

    for (int i = 0; i < n; i ++) printf("%d ", q[i]);

    return 0;
}

建议

取分界点的时候取中间点为分界点，取 左右边界点 可能会TLE（时间超限）