题目描述

原题

题目大意&链接

给定一个长度为n的乱序数列，用快速排序将数列排成有序数列。

输入输出样例：
输入:

5
3 1 2 4 5

输出：

1 2 3 4 5

详情：ac_785快速排序

解题思路

快速排序主要就是分治思想，将数列以枢轴x为标准，划分为两个区间（i<=x 和 j>=x），划分好后重新选取枢轴x依次递归处理其左右区间。

  1. 枢轴选取：
    共有四种选取方式：左端点q[l]，右端点q[r]，中间索引q[l + r >> 1] 和 随机索引（这里我一般取中间索引作枢轴）

    int x = q[l + r >> 1], i = l - 1, j = r + 1;

  2. 调整区间：
    定义i和j两个指针，i指向<=x的区间，j指向>=x的区间

    int x = q[l + r >> 1], i = l - 1, j = r + 1;

  3. 递归处理左右区间

    quick_sort(q, l, j);
    quick_sort(q, j+1 ,r);

完整代码

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

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &q[i]);
	
	quick_sort(q, 0, n-1);
	bool flag = true;
	for(int i=0;i<n;i++) 
	{
	    if(flag){
	        printf("%d", q[i]);
	        flag = false;
	    }else{
	        printf(" %d", q[i]);
	    }
	}
	
	return 0;
}

时间和空间复杂度

时间复杂度：O(nlogn)
空间复杂度：O(logn) 取决于快速排序形成的递归树调用栈的深度