【排序算法】快速排序的基本算法

        快速排序是应用最广泛的排序算法，流行的原因是它实现简单，适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。快速排序引人注目的特点是原地排序，只需要一个很小的辅助栈，且将长度为N的数组排序所需时间和NlgN成正比。另外，快速排序的内循环比其他大多数排序算法都要短小。它的主要缺点是非常脆弱，在实现时需要非常小心才能避免低劣的性能。

        快速排序是一种分治的排序算法。它将一个数组分为两个子数组，将两部分单独排序。快速排序和归并排序是互补的：归并排序将数组分为两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就有序了。

        在快速排序中，切分的位置取决于数组的内容。

        快速排序的关键在于切分，切分过程使得数组满足一下三个条件：

        1、对于某个j，a[j]已经排定

        2、a[lo]到a[j-1]中所有元素都不大于a[j]

        3、a[j+1]到a[hi]中所有元素都不小于a[j]

        通过递归地调用切分来排序。

        算法的实现：

import java.util.Arrays;
import java.util.Collections;
public class Quick {
    private static int partition(int[] a,int lo,int hi)
    {
        int i=lo,j=hi+1;
        int v=a[lo];
        while (true)
        {
            while (a[++i]<v)if(i==hi) break;
            while (v<a[--j])if(j==lo) break;
            if (i>=j) break;
            list_deal.exch(a,i,j);
            list_deal.printArray(a);
        }
        list_deal.exch(a,lo,j);
        list_deal.printArray(a);
        return j;
    }
    private static void sort(int[] a,int lo,int hi)
    {
        if (hi<=lo) return;
        int j=partition(a,lo,hi);
        sort(a,lo,j-1);
        sort(a,j+1,hi);
    }
    public static void sort(int[] a)
    {
        list_deal.randomshuffle(a);
        list_deal.printArray(a);
        sort(a,0,a.length-1);
    }
    public static void main(String[] args) {
        int[] a={534,745,264,864,136,967,254,746,734,269,538,265,825,158,139,100};
        sort(a);
        list_deal.printArray(a);
    }
}

排序过程（因为有随机排序，所以每次执行的过程可能都不一样）：

158 734 100 534 967 864 825 746 136 139 264 269 745 265 254 538 
158 139 100 534 967 864 825 746 136 734 264 269 745 265 254 538 
158 139 100 136 967 864 825 746 534 734 264 269 745 265 254 538 
136 139 100 158 967 864 825 746 534 734 264 269 745 265 254 538 
136 100 139 158 967 864 825 746 534 734 264 269 745 265 254 538 
100 136 139 158 967 864 825 746 534 734 264 269 745 265 254 538 
100 136 139 158 538 864 825 746 534 734 264 269 745 265 254 967 
100 136 139 158 538 254 825 746 534 734 264 269 745 265 864 967 
100 136 139 158 538 254 265 746 534 734 264 269 745 825 864 967 
100 136 139 158 538 254 265 269 534 734 264 746 745 825 864 967 
100 136 139 158 538 254 265 269 534 264 734 746 745 825 864 967 
100 136 139 158 264 254 265 269 534 538 734 746 745 825 864 967 
100 136 139 158 254 264 265 269 534 538 734 746 745 825 864 967 
100 136 139 158 254 264 265 269 534 538 734 746 745 825 864 967 
100 136 139 158 254 264 265 269 534 538 734 746 745 825 864 967 
100 136 139 158 254 264 265 269 534 538 734 746 745 825 864 967 
100 136 139 158 254 264 265 269 534 538 734 745 746 825 864 967 
100 136 139 158 254 264 265 269 534 538 734 745 746 825 864 967 
100 136 139 158 254 264 265 269 534 538 734 745 746 825 864 967 

快速排序算法需要注意的点：

1、原地切分：如果使用一个辅助数组，很容易实现切分，但将切分后的数组复制回去的开销很大。

2、别越界：如果切分元素是数组中最大或最小的元素，需要小心别让扫描指针跑出数组的边界。

3、保持随机性：数组元素的顺序是被随机打乱的，这对预测算法的运行时间很重要

4、终止循环：正确的检测指针是否越界需要一些技巧

5、处理切分元素时需要注意有重复的情况

6、终止递归地方法。