quick_sort

快速排序

快速排序的思路：1.选择一个节点作为分界点。 2.以这个分界点将数组分为左右两边，左边小于等于节点数，右边则是大于等于
3.递归排序左右两边，需要注意递归的终点。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

const int N = 1e6+10;
int a[N];

using namespace std;

void quickSort(int a[],int l,int r)
{
    if(l >= r) return;//先判断边界
    
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while(i < j)
    {
        do i++; while(a[i] < x);
        do j--; while(a[j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    
    quickSort(a,l,j);//递归调用
    quickSort(a,j+1,r);
}

int main()
{
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i ++ )
        scanf("%d", &a[i]);
    
    quickSort(a,0,n-1);
    
    for (int i = 0; i < n; i ++ )
        cout << a[i] <<" ";
        
    return 0;
}