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个样本的中位数作为标记值。。。）