0.算法解决的问题
快速排序算法被评做二十世纪十大算法之一。
相比于其他排序算法，快速排序在 时间复杂度和空间复杂度 综合的层面上略高一筹。
快速排序的空间复杂度是O(1)（相比于归并排序O(n)），时间复杂度为O(nlogn).这是其他排序算法做不到的。
1.输入与输出
- 输入：乱序的数组
- 输出：有序的数组
2.算法思想
快速排序依然采用了分治的思想;但是其与归并排序存在差异：
归并排序是先把大数组分为小数组，然后将其排序，合并，直到合并到原来的数组，合并完成，排序完成。
递归调用发生在排序之前.
快速排序是先将大数组搞成一个略微有序的状态（大于标记值的元素放右边，小于标记值的元素放左边）然后再分别排两个小数组，分解完成，排序完成。
递归调用发生在排序之后
图片来自维基百科
3.伪代码及注释
本段代码有五个函数：main,qsort,partition,swap,show
main（String［］ args）
用作测试执行
swap（数组，int值，int值）
将输入数组的两输入下标的值进行交换。
show（数组）
将数组值一一打印出来。
qsort（数组，首元素下标，末元素下标）
这是排序函数的主体，先对本数组执行分区(patition)操作，获得分区值的下标。然后递归的排序左右两边的数组。
patition(数组，首元素下标，末元素下标)
取末元素作为标记值，建立两个指针对应首末，开始扫描。
｛从右向左找比标记值大的数
从左向右找比标记值小的数
若两者位置不正确，交换｝
扫描完成，将标记值交换到正确的位置，返回标记值的位置，结束。
图片来自维基百科
4.java代码实现
public class quicksort{
public static void main(String args[])
{
int[] a = {5,7,3,4,1,6,8,2};
show(a);
qsort(a);
show(a);
}
public static void qsort(int[] a )
{
qsort(a,0,a.length-1);
}
public static void qsort(int[]a,int first,int last)
{
if(first>=last)
return;
int q = partition(a,first,last);
qsort(a,first,q-1);
qsort(a,q+1,last);
}
public static int partition(int[]a,int first,int last)
{
int temp = a[last];
int i,j;
i = first-1;
j = last;
while(true)
{ //扫描。
show(a);
while(a[++i] <= temp) if(i == last) break;
while(a[--j] >= temp) if(j == first) break;
if(i>=j) break;
swap(a,i,j);
}
swap(a,last,i);
return i;
}
public static void swap(int[] l,int a,int b)
{
int temp = l[a];
l[a] = l[b];
l[b] = temp;
}
public static void show(int []a)
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
5.复杂度
空间复杂度是O(1)
时间复杂度为O(nlogn).
但是消耗时间长短受到标记值在数组中的大小的影响，如果每次标记值都是数组中最小的或者最大的，甚至会出现O(n平方)的情况，因此其不稳定。
6.优缺点及适用范围
优点：不需要占用额外的空间，这对于大数据排序很有帮助。时间复杂度低，算法简单。可以用作动态数据库排序所需。
缺点：时间较不稳定，需要进一步优化（例如取3个样本的中位数作为标记值。。。）
