定义
快速排序是一种分治策略的排序算法，其核心思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
具体实现过程如下：
1、选择一个基准元素（通常选择第一个或者最后一个元素），将待排序数据分成小于等于基准元素的部分和大于基准元素的部分； 2、对小于等于基准元素的部分和大于基准元素的部分分别递归调用快速排序函数，直到只剩下一个元素或者没有元素。
示例代码1：
// 快速排序的递归函数 left数组最左边的索引，right数组最右边的索引
void quickSort(int arr[], int left, int right) {
// 如果左边界大于右边界，则退出递归
if (left >= right) {
return;
}
// 设置左边界和右边界
int i = left;
int j = right;
// 设置基准值为数组的第一个元素
int t = arr[left];
// 循环条件为左边界小于右边界
while (i < j) {
// 从右边界开始查找小于基准值的元素
while (i < j && arr[j] >= t) {
j--;
}
// 将小于基准值的元素移动到左边界的位置
arr[i] = arr[j];
// 从左边界开始查找大于基准值的元素
while (i < j && arr[i] <= t) {
i++;
}
// 将大于基准值的元素移动到右边界的位置
arr[j] = arr[i];
}
// 将基准值放到中间位置
arr[i] = t;
// 对基准值左边的数组进行快速排序
quickSort(arr, left, i - 1);
// 对基准值右边的数组进行快速排序
quickSort(arr, i + 1, right);
}
案例
题目描述
利用快速排序算法将读入的N个数从小到大排序后输出。 快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（请不要试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。）
输入格式
第1行为一个正整数N，第2行包含N个空格隔开的正整数ai，为你需要进行排序的数，数据保证了Ai不超过1000000000。
输出格式
将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。
输入输出样例
输入
5
4 2 4 5 1
输出
1 2 4 4 5
说明/提示
对于20%的数据，有N≤1000；
对于100%的数据，有N≤100000。
参考代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[1000001];
void quickSort(int arr[], int left, int right) {
// 如果左边界大于右边界，则退出递归
if (left >= right) {
return;
}
// 设置左边界和右边界
int i = left;
int j = right;
// 设置基准值为数组的第一个元素
int t = arr[left];
// 循环条件为左边界小于右边界
while (i < j) {
// 从右边界开始查找小于基准值的元素
while (i < j && arr[j] >= t) {
j--;
}
// 将小于基准值的元素移动到左边界的位置
arr[i] = arr[j];
// 从左边界开始查找大于基准值的元素
while (i < j && arr[i] <= t) {
i++;
}
// 将大于基准值的元素移动到右边界的位置
arr[j] = arr[i];
}
// 将基准值放到中间位置
arr[i] = t;
// 对基准值左边的数组进行快速排序
quickSort(arr, left, i - 1);
// 对基准值右边的数组进行快速排序
quickSort(arr, i + 1, right);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
//left = 1 right = n
quickSort(a,1,n);
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}