轉(zhuǎn)：微信公眾號(hào)：程序員小灰
快排算法 是按分治算法的思路進(jìn)行排序的。
選定參照元素后匹颤，每次比較都按分治算法將小的移到绞灼，
最壞情況時(shí)間復(fù)雜度：n(n*n)
平均時(shí)間復(fù)雜度：n(nlog2n)
最快情況時(shí)間復(fù)雜度：n(n-1)
實(shí)現(xiàn)的2種方法：
1.挖坑法
譬如：5（坑）唱蒸，1钉答，7础芍，6，2数尿，8仑性，3，4右蹦，9
以5為基準(zhǔn)元素：
提示：
right<基準(zhǔn)元素才會(huì)位置不動(dòng)去填坑诊杆，
left>基準(zhǔn)元素才會(huì)位置不動(dòng)去填坑
最左邊5為left,最右邊9為right
先從右邊right開(kāi)始比較，right=9 > 5, 不需要填坑嫩实，
繼續(xù)左移動(dòng)刽辙，right = 4 <5,則需要用9去填5這個(gè)坑，right移動(dòng)之后到left移動(dòng)(此時(shí)right還是=4甲献，原地不動(dòng)宰缤，同時(shí)right=4=坑)，此時(shí)列表應(yīng)為：：
4晃洒，1慨灭，7，6球及，2氧骤，8，3吃引，4（坑）筹陵，9
原坑5被填，故left自動(dòng)右移一位镊尺，
left=1 < 5, 繼續(xù)右移一位朦佩，
left = 7 > 5, 用7去填坑4，
left停留在7, 7同時(shí)也變成了坑庐氮，
此時(shí)列表為：
4语稠，1，7（left,坑）弄砍，6仙畦，2，8音婶，3慨畸，7(right)，9
right左移一位衣式，right=3 < 5,
用3 去填坑7先口，同時(shí)3也變成了坑型奥，
列表：
4，1碉京，3（left）厢汹，6，2谐宙，8烫葬，3（right,坑），7凡蜻，9
left右移一位搭综，left=6,
6>5,用5去填坑3,
列表：
4，1划栓，3兑巾，6（left,坑），2忠荞，8蒋歌，6（right），7委煤，9
right左移一位堂油，right=8,8>5,
繼續(xù)左移一位，right = 2, 2<5,
用2填坑6,
列表：
4碧绞，1府框，3，2（left）讥邻，2（right迫靖，坑），8兴使，6袜香，7，9
left右移一位鲫惶，
left=2=right
列表：
4，1实抡，3欠母，2，2（left, right吆寨，坑）赏淌，8，6啄清，7六水，9
由于left=2=right,
所以將一開(kāi)始的基準(zhǔn)元素5替換掉坑
列表：
4俺孙，1，3掷贾，2睛榄，5，8想帅，6场靴，7，9
此時(shí)5左邊都是小于5港准，右邊都是大于5
2.交換地址發(fā)法：
4旨剥，8，2浅缸，6轨帜，1，3衩椒，9蚌父，5，7
基準(zhǔn)元素4烟具，列表
4（left）梢什，8，2朝聋，6嗡午，1，3冀痕，9荔睹，5，7（right）
right=7 > 4 ,左移一位言蛇，
right=5>4 ,左移一位僻他，
right=9>4, 左移一位，
right=3 <4,不動(dòng)腊尚，記住位置
列表：
4（left）吨拗，8，2婿斥，6劝篷，1，3（right），9，5金麸，7
left=4=4,left右移一位餐塘，
left=8>4,left不動(dòng)，記住位置啊楚，
然后left和right呼喚位置
列表：
4霸株，3（left）掺喻，2着绷，6蛔钙，1，8（right）蓬戚，9夸楣，5，7
right左移一位子漩，right=1<4,不動(dòng)豫喧，記住位置
left右移一位，left=2<4,
left右移一位幢泼，left=6>4, 不動(dòng)紧显，記住位置
left和right位置呼喚，
列表：
4缕棵，3孵班，2，1（left）招驴，6（right）篙程，8，9别厘，5虱饿，7
right左移一位，right=left=1触趴，
列表：
4氮发，3，2冗懦，1（left爽冕，right），6披蕉，8颈畸，9，5没讲，7
第一輪呼喚位置完畢
拓展：
是否只能用遞歸實(shí)現(xiàn)快排呢眯娱？
不是，還可以用stack的方法?
定義一個(gè)一個(gè)map類型的集合棧
map有startindex和endindex
然后把map壓進(jìn)棧?
再一個(gè)循環(huán)食零，棧空則跳出
不停pop出map寂屏，map里的startindex和endindex可以定義新的pivot基準(zhǔn)元素
if判斷（左邊分區(qū)要小于pivot基準(zhǔn)元素）
是則map出一個(gè)新的集合贰谣，然后push進(jìn)去stack
右邊也類似娜搂！
代碼:
package quickSort;
import java.util.Arrays;
public class quickSort {
//第一輪分區(qū)交換數(shù)據(jù)
private static int? partition(int[] arr, int startIndex, int endIndex){
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while(left != right){
//arr[right]>=pivot基準(zhǔn)元素時(shí)，左移一位
while(left < right && arr[right] >= pivot){
right--;
}
//arr[left]<=pivot基準(zhǔn)元素時(shí)吱抚，右移一位
while(left < right && arr[left] <= pivot){
left++;
}
//交換位置
if(left < right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
//跳出循環(huán)時(shí)百宇，left==right,替換pivot和指針重合元素
int temp = arr[left];
arr[left] = arr[startIndex];
arr[startIndex] = temp;
return left;
}
//對(duì)數(shù)組進(jìn)行多輪分區(qū)，迭代
public static void quicksort(int[] arr, int startIndex, int endIndex) {
//遞歸約束條件秘豹，startIndex>endIndex
if (startIndex > endIndex) {
return;
}
int pivotIndex = partition(arr, startIndex, endIndex);
quicksort(arr, startIndex, pivotIndex-1);
quicksort(arr, pivotIndex+1, endIndex);
}
public static void main(String[] args) {
int[] arr = new int[]{3,8,2,4,1,3,3,5,7,8,9,4,2,845,4,14,8,6,814,};
quicksort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
