快速排序

先说两种最常见的快速排序，左右指针法，填坑法。
这两种快排极其相似，思路我就不说了，网上写的又详细又好的人太多了。
我就记录一下几个关键点。
第一个：
为什么 if(start >= end) return;中是>=？
答：首先>肯定是必备的，毋庸置疑。写等于是因为，当start和end相等的时候不就指向一个数吗，无需在将这个一个数的子数组快排。
第二个：
为什么是while(array[j]>=key && i < j) 和 while(array[i]<=key && i < j)？
答：先说array[j]>=key和array[i]<=key中为什么要有等于，因为避免进入死循环。如果数组是一个全是相等的数(比如全是1)的数组，那么不加等于的话，i和j不会加减，循环不会跳出。
好，那现在加上等于了，还是哪个例子，下标越界了。因为i==j==0的时候，j继续减1，自然下标越界。所以要加上 && i < j 。

public class QuickSort {

    /**
     * 左右指针法
     * @param array
     * @param start
     * @param end
     */
    public static void sort(int []array, int start, int end) {
        if(start >= end)
            return;
        int i = start;
        int j = end;
        int key = array[start];
        while(i < j) {
            while(array[j]>=key && i < j) 
                j--;
            while(array[i]<=key && i < j) 
                i++;
            swap(array, i, j);
        }
        swap(array, start, j);
        sort(array, start, j-1);
        sort(array, j+1, end);
    }
    
    /**
     * 填坑法
     * @param array
     * @param start
     * @param end
     */
    public static void sort2(int []array, int start, int end) {
        if(start >= end)
            return;
        int i = start;
        int j = end;
        int key = array[start];
        while(i < j) {
            while(array[j]>=key && i < j) 
                j--;
            array[i] = array[j];
            while(array[i]<=key && i < j) 
                i++;
            array[j] = array[i];
        }
        array[j] = key;
        sort2(array, start, j-1);
        sort2(array, j+1, end);
    }
    
    public static void main(String[] args) {
        int[] array = {10,7,2,4,7,62,3,4,2,1,8,9,19};
//      int[] array = {1,1,1,1,1,1,1,1};
        sort2(array, 0, array.length-1);
        for (int k = 0; k < array.length; k++) {
            System.out.print(array[k] + " ");
        }
        System.out.println();
    }
    
    public static void swap(int []array,int i,int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

还有一种前后指针法，和非递归(用栈实现)的快排方法。
前后指针法的优势在于可以对链表排序。
非递归的快排用栈实现。这里引用一名CSDN博主的原话，说的很好。
递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。 一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。