一、快速排序算法的基本特性
时间复杂度：O（n*lgn）
最坏：O（n^2）
空间复杂度：O（n*lgn）
不稳定。
快速排序是一种排序算法，对包含n个数的输入数组，平均时间为O（nlgn），最坏情况是O（n^2）。
通常是用于排序的最佳选择。因为，基于比较的排序，最快也只能达到O（nlgn）
二、快速排序算法的描述
算法导论，第7章
快速排序时基于分治模式处理的，
对一个典型子数组A[p...r]排序的分治过程为三个步骤：
1.分解：
A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得
A[p ..q-1] <= A[q] <= A[q+1 ..r]
2.解决：通过递归调用快速排序，对子数组A[p ..q-1]和A[q+1 ..r]排序。
3.合并。
三、快速排序算法
#include<iostream>
#include <assert.h>
using namespace std;
void quicksort(int *a, int begin, int end)
{
assert(a!=nullptr);
int key = a[begin];
int i = begin, j = end;
if (i==j)
{
return;
}
while(i<=j&&i>=0&&j>=0)
{
while (key<=a[j]&&i<j)
{
j--;
}
if (i<j)
{
swap(a[i],a[j]);
i++;
}
while(a[i]<=key)
{
i++;
}
if (i<j)
{
swap(a[j],a[i]);
j--;
}
}
if(j > 1)
quicksort(a, begin,j-1);
if(end - j > 1)
quicksort(a, j+1, end);
}
int main()
{
int a[10] = {11, 25, 10, 4, 88, 2, 108, 3, 2, 21};
quicksort(a, 0, 9);
for(int i = 0; i < 10; i++)
{
cout << a[i] <<endl;
}
return 0;
}