快速排序

题目描述

将读入的 N 个数从小到大排序后输出。

输入格式

第一行为一个正整数 N。

第二行包含 N 个空格隔开的正整数 ，为你需要进行排序的数。

输出格式

将给定的 N 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入 #1

5
4 2 4 5 1

输出 #1

1 2 4 4 5

说明/提示

一、 左右指针法

#include<iostream>
using namespace std;

void swap(int &a,int &b){
    int t;t = a;a = b;b = t;
}

int sort(int i,int j,int num[]){
    int key = i;
    while(i < j){
        while(i < j && num[j] >= num[key]) j--;  //这里右指针先动
        while(i < j && num[i] <= num[key]) i++;  
        //右指针碰到比基准小的之后左指针动，直到左指针遇到比基准大的
        
        swap(num[i],num[j]);
        //j--;  交换完之后直接下一轮while，不需要让右指针再往左一次
    }
    swap(num[j],num[key]);
    return j;  //返回此次sort基准的位置，以便分割快排
}

void quickSort(int i,int j,int num[]){
    if(i >= j) return;
    int key = sort(i,j,num);
    quickSort(i,key-1,num);
    quickSort(key+1,j,num);
}

int main(){
    int n;cin >> n;
    int num[n];
    for (int i = 0; i < n; i++)  cin >> num[i];
    quickSort(0,n-1,num);
    for (int i = 0; i < n - 1; i++)  cout << num[i] << " ";
    cout << num[n-1];
}

二、挖坑法（王道演示的就是这种）