快速排序
简介
快速排序是计算机领域最经典的算法之一，简称快排，最早由 C.A.R.Hoare 提出。在平均状况下，排序n个元素要次比较O(nlogn)次。在最坏状况下的时间复杂度是O(n²)，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，所以名字叫快速排序。
流程
快速排序是分治思想的一个应用场景。
快速排序首先选择一个基准数，因为后面我们需要根据基准数，把所有代排序的数字分为比基准数大或者比基准数小两部分，大的位于右侧，小的位于左侧。所以基准数最好选择中位数附近的数字，当然由于我们事先并不知道中位数位于什么位置，根据随机理论，中位数出现在任何一个位置出现的概率均相等，所以我们一般选择第一个或者最后一个数字作为基准数。
假如选择第一个数字作为基准数，那我们首先使用最后一个数字和基准数比较，我们使用aj表示，如果该数字比基准数大，则该数字应该位于基准数的右侧，则不做任何处理，j的位置左移一位，如果该数字比基准数小，该数字会位于基准数左侧，所以将该数字和基准数交换。
当基准数交换到右侧之后，我们从左侧继续和基准数比较，当然刚才交换过来的数字已经明确比基准数小，所以我们从被交换过来的位置i+1之后进行比较，同理，如果比基准小则右移一位，反之则和基准数交换。
从上述流程中我们可以分析出来以下特点：
快速排序每次移动一位，或者是右侧左移一位，或者是左侧右移一位。
移动的过程或者伴随着基准数和其他位置数字的交换。
快速排序过程中，基准数的左侧和右侧始终有一侧保持着全部比基准数小或者全部比基准数大的状态。
快速排序会在左侧指标大于等于右侧指针的时候结束一轮循环，而此轮循环结束之后，基准侧左侧的所有数字均小于基准数，右侧反之。
每轮循环结束之后，基准数左侧部分和右侧部分都分别进行以上操作。直到分治的数组长度为一的时候结束。
代码
#include<iostream>
using namespace std;
void print(int a[], int n)
{
for(int j= 0; j<n; j++)
{
cout<<a[j] <<" ";
}
cout<<endl;
}
void quickSort(int a[], int low ,int high)
{
if(low<high) //循环的中止条件
{
int i = low, j = high; //初始化；
int x = a[low]; //将待排序数组的第一个元素作为基准数，将数组划分为大于或者小于基准数的两部分
while(i<j)
{
while(i<j && a[j] >= x) j--;
if(i<j) a[i++] = a[j];
while(i<j && a[i] <= x) i++;
if(i<j) a[j--] = a[i];
}
a[i] = x;
quickSort(a, low ,i-1);
quickSort(a, i+1 ,high);
}
}
int main()
{
int a[10] = {8,1,9,7,2,4,5,6,10,3};
cout<<"初始序列：";
print(a,10);
quickSort(a,0,9);
cout<<"排序结果：";
print(a,10);
system("pause");
}
算法分析
快速排序的时间复杂度是O(n*lgn)，我们可以进行朴素的进行分析，因为每一轮循环需要比较n次，但是因为每轮循环之后，快速排序均能把数据分为左小右大相对有序的两部分，所以下次比较的数据规模就变为了½，有点类似二叉树，而二叉树的高度为lg(n)，所以快排的数据复杂度为O(n*lgn)。