题目描述

blablabla

样例

//2023.2.13 取中点且x=q[l+r>>1]时，不能用i
//0 1 2 3 4 5 6 7 (3为枢轴量位置)
//0 8 2 3 4 5 6 7
//* i * j * * * *(8 3不符合条件)
//0 3 2 8 4 5 6 7 (8 3交换，第一个while完成)
//* * j i * * (2 8不符合条件，且i>j，不会交换)
//第一轮完成时，下标3左侧都小于等于3，右侧都大于3
//恰好进入下一轮
//while中如果有一侧全部符合条件，另一侧有一个不符合条件，则先交换，交换完成后i、j相向推进

//0 1 2 3 4 5 6 7 (3为枢轴量位置)
//0 8 9 3 4 5 6 7
//* i * j * * * *(8 3不符合条件)
//0 3 9 8 4 5 6 7 (8 3交换，第一个while完成)
//* j i * * (3 9不符合条件，且i>j，不会交换)
//第一轮完成时，下标3左侧都小于等于3，右侧都大于3
//恰好进入下一轮
#include<iostream>

using namespace std;

const int N=1e6+10;

int n;
int q[N];

void quick_sort(int q[],int l,int r)
{
    if(l>=r) return;

    int x=q[l+r>>1],i=l-1,j=r+1; //x取下取整为枢轴量，i迁就do-while从l-1开始，j迁就do-while从r+1
    while(i<j)
    {
        do i++;while(q[i]<x); //i右移
        do j--;while(q[j]>x); //j左移
        if(i<j) //将不符合条件的两边的数交换位置
        {
            int temp=q[i];
            q[i]=q[j];
            q[j]=temp;
        }
    }

    //递归调用
    quick_sort(q,l,j); //j恰好为左半部分的右边界
    quick_sort(q,j+1,r); //j+1恰好为右半部分的左边界
    //不能用i
}

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;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla