先说两种最常见的快速排序，左右指针法，填坑法。
这两种快排极其相似，思路我就不说了，网上写的又详细又好的人太多了。
我就记录一下几个关键点。
第一个：
为什么 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博主的原话，说的很好。
递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。 一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。
