基本思想：与归并排序一样，快速排序也采用了分治法。将原问题分解成几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。在快速排序中，因为子数组都是原址排序的，所以不需要合并操作。
----------
/*排序算法：快速排序
时 间：2018年1月14日
时间复杂度：最好情形O(nlgn)，平均情形O(nlgn)，最差情形O(n^2)
空间复杂度：O(lgn)
稳 定 性：不稳定
by Ingran*/
----------
#include<iostream>
#include<time.h>
#include<iomanip>
void Swap(int A[], int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
int Partition(int A[], int p, int r)//对子数组进行原址重排
{
int x = A[r]; //储存数组最后一个元素最为“主元”
int i = p - 1;
for (int j = p; j < r; j++)
{
if (A[j] <= x)
{
i = i + 1;
Swap(A, i, j);//把小于主元的数值放在左边
}
}
Swap(A, i + 1, r);//把r放在相对于（左边是比r小的，右边是比r大的）中间的位置
return i + 1;//返回当前主元位置的下标
}
void Quick_Sort(int A[], int p, int r)//快速排序，参数为数组A，数组A的首元素下标和最后一个元素的下标
{
int q = 0;
if (p < r)
{
q = Partition(A, p, r);
Quick_Sort(A, p, q - 1);
Quick_Sort(A, q + 1, r);
}
}
int main()
{
int *p = nullptr;
int n = 0;
srand((unsigned)time(NULL));
std::cout << "请输入随机数个数：" << std::endl;
std::cin >> n;
p = new int[n];
std::cout << "排序前：" << std::endl;
for (int i = 0; i < n; i++)
{
p[i] = rand() % 101;
std::cout << std::setw(3) << p[i] << " ";
if (i % 10 == 9)
std::cout << std::endl;
}
Quick_Sort(p, 0, n - 1);
std::cout << std::endl << "排序后：" << std::endl;
for (int i = 0; i < n; i++)
{
std::cout << std::setw(3) << p[i] << " ";
if (i % 10 == 9)
std::cout << std::endl;
}
system("pause");
return 0;
}