[数据结构与算法]快速排序算法（C或者C++）

快速排序算法

1. 算法介绍

该算法的实现可分为以下几步：

1. 在数组中选一个基准数（通常为数组第一个）；

2. 将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边,即将数组一分为二，一般右边均大于基准数，左边均小于基准数；

3. 运用递归，对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素（递归出口），即为全部有序。

2. 模板代码

（代码来源于AcWing第785题）

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int n;
int nums[N];
//快速排序算法
void quick_sort(int nums[], int l, int r){
    if(l >= r) return ;//递归出口
    //基准数以及双指针
    int x = nums[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j ){
    //指针向中间移动，找到不符的点就交换
        do i ++; while(nums[i] < x);
        do j --; while(nums[j] > x);
        if(i < j) swap(nums[i], nums[j]);
    }
    //将分好的两组分别排序，需注意分界点
    quick_sort(nums, l, j);
    quick_sort(nums, j+1, r);
}

int main(){
	//输入
    scanf("%d",&n);
    for(int i = 0; i < n; i ++) scanf("%d",&nums[i]);
    //排序
    quick_sort(nums, 0, n-1);
    //输出
    for(int i = 0; i < n; i ++) printf("%d ",nums[i]);
    return 0;
}

3. 总结

需要注意分界点！设计的临界值的位置和两个新的数组需要注意！