快排優(yōu)化的三種思路：
選擇的軸樞元素娘赴，是否可以挑選的更好一些？
遞歸調(diào)用排序的時(shí)候挎挖，是否可以少一些調(diào)用这敬？
partion操作是否可以優(yōu)化一些？
一蕉朵、基準(zhǔn)值選取優(yōu)化
如果基準(zhǔn)值選取的不合理崔涂，可能會(huì)導(dǎo)致快排的時(shí)間復(fù)雜度達(dá)到O(n2) 這個(gè)量級(jí)，只有當(dāng)基準(zhǔn)值的選擇剛好將數(shù)據(jù)進(jìn)行平分的時(shí)候始衅，時(shí)間復(fù)雜度才是O(nlogn)冷蚂。
因?yàn)槲覀兒茈y在一個(gè)無(wú)序的數(shù)組中缭保，使用O(1)的時(shí)間復(fù)雜度找到可以把數(shù)組均分的基準(zhǔn)值，那么有沒(méi)有什么方法可以大概率找到這個(gè)值呢蝙茶？
這個(gè)方法就是三點(diǎn)取中法
即在一個(gè)數(shù)組中艺骂，取數(shù)組的第一個(gè)元素，中間一個(gè)元素隆夯，最后一個(gè)元素钳恕，然后排序后，將中間值作為基準(zhǔn)元素蹄衷，然后對(duì)數(shù)組進(jìn)行partiton操作忧额。
如下圖所示： 取5，2愧口，8然后排序后： 2睦番，5，8耍属，以5作為基準(zhǔn)元素然后進(jìn)行數(shù)據(jù)partion操作托嚣。
代碼實(shí)現(xiàn)：
說(shuō)明： 查看之前快排的代碼中partition部分
int pivot = nums[left];是將nums[left]作為了基準(zhǔn)值，所以要將計(jì)算得出的中間值厚骗，賦值給基準(zhǔn)值
// 1. 基準(zhǔn)值選擇優(yōu)化
public static void baseValueChooseOptimize(int[] nums, int left, int right){
int pivot;
if(left < right) {
pivot = baseValueChoosePartition(nums, left, right);
baseValueChooseOptimize(nums, left, pivot-1);
baseValueChooseOptimize(nums, pivot+1, right);
}
}
public static int baseValueChoosePartition(int[] nums, int left, int right) {
//計(jì)算并獲得3個(gè)數(shù)中示启，軸樞元素的坐標(biāo)
// 獲取中間元素的下標(biāo)
int m = left + (right - left)/2;
if(nums[left] > nums[right]) { //保證左邊較小
swap(nums, left, right);
}
if(nums[m] > nums[right]) {
swap(nums, m, right); //保證中間較小
}
if(nums[m] > nums[left]) { //保證左端是中間值
swap(nums, left, m);
}
// 為啥這里要用的是nums[left]呢？
// 因?yàn)榭炫砰_(kāi)始執(zhí)行的時(shí)候是將第一個(gè)元素作為軸樞元素開(kāi)始分割的领舰，需要將三個(gè)元素中丑搔，中間的那個(gè)放到left的位置上。
int pivot = nums[left];
System.out.println("基準(zhǔn)值為：" + pivot);
while(left < right) {
while (left < right && nums[right] >= pivot) {
right--;
}
nums[left] = nums[right];
while (left < right && nums[left] <= pivot) {
left++;
}
nums[right] = nums[left];
}
nums[left] = pivot;
return left;
}
二提揍、單邊遞歸優(yōu)化
看下圖代碼，每次完成一次partition操作后煮仇，就會(huì)對(duì)基準(zhǔn)值左右兩側(cè)進(jìn)行了遞歸調(diào)用劳跃，從程序運(yùn)行的過(guò)程來(lái)看，每遞歸調(diào)用一次方法浙垫，都會(huì)有耗時(shí)刨仑。
則考慮減少函數(shù)調(diào)用的方式，來(lái)縮短程序運(yùn)行時(shí)間夹姥。
解決方法： 在每次完成partition操作后杉武，直接在本層直接完成基準(zhǔn)值左邊的partition操作（需要一個(gè)循環(huán)），而基準(zhǔn)值右邊的操作辙售，放到下一輪partition操作來(lái)完成轻抱。
代碼示例：
// 2、單邊遞歸優(yōu)化
public void singleRecursionOptimize(int[] nums, int left, int right) {
int middle = 0;
while(left < right) {
middle = partition(nums, left, right);
// 對(duì)分界值分隔的兩個(gè)數(shù)組;
// middle左邊的數(shù)組在一個(gè)循環(huán)里旦部，繼續(xù)執(zhí)行partion操作
// middle右邊的數(shù)組在下一次遞歸中再進(jìn)行調(diào)用祈搜。
quickSort(nums, middle+1, right);
right = middle -1;
}
}
三较店、partition操作優(yōu)化
暫時(shí)沒(méi)太理解，待后續(xù)補(bǔ)充...
詳細(xì)代碼見(jiàn)：algorithm_java
