快排沒啥好講的障癌，主要是看到劍指offer上說求第K大個數(shù)混弥，能達到時間O(N),表示不理解。
同時蝗拿，以下代碼中partition的返回值是每次分組排序得到的一個正確的最終坐標
public class Partition {
// 方便得到每次partition的一個位置，可能在做“尋找特定位置的值”問題上能夠優(yōu)化
public int partition(int[] array,int start, int end){
int i = (int)Math.random()*(end-start);
i += start;
swap(array, i, end);
//small是一個坐標惦辛，始終代表的是比那個對比值小并且右邊一定是比對比值大的數(shù)的位置坐標胖齐。因此最終for之后++small,是將對比值放入它在排序中的最終位置,對比值左邊全是比它小的嗽冒，右邊全是比它大的
int small = start - 1;
for (int index = start; index < end; index++) {
if (array[index] < array[end]) {
++small;
//一旦small，index不同步向前添坊，說明++small此時指向的數(shù)比那個對比值大贬蛙，然后調(diào)換位置
if (small != index) {
swap(array, small, index);
}
}
}
++small;
swap(array, small, end);
return small;
}
public void swap(int[] array, int head, int trail) {
if(head >= 0 && trail < array.length){
int tmp = array[trail];
array[trail] = array[head];
array[head] = tmp;
}
return;
}
public void quickSort(int[] array, int start, int end){
if (start == end) {
return;
}
int mid = partition(array, start, end);
// 無論mid是什么都要分別執(zhí)行左右兩邊的子問題阳准，所以不能用else
if (mid > start) {
quickSort(array, start, mid-1);
}
if (mid < end) {
quickSort(array, mid+1, end);
}
}
public static void main(String[] args) {
int[] array = {3,0,1,2,5,6};
Partition partition = new Partition();
partition.quickSort(array, 0, 5);
// 親測有效
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
}
