快速排序
思路：
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分潭袱，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小病梢，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行造虎，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列块攒。
復(fù)雜度分析：
其平均時(shí)間復(fù)雜度與歸并排序均為O(nlogn)，但是歸并排序除了遞歸調(diào)用間接使用了輔助空間棧南蹂，還需要額外的O(n)空間進(jìn)行臨時(shí)存儲(chǔ)犬金。從此角度歸并排序略遜于快速排序，但是歸并排序是一種穩(wěn)定的排序算法六剥，快速排序則不然晚顷。
所謂穩(wěn)定排序，表示對于具有相同值的多個(gè)元素疗疟，其間的先后順序保持不變该默。對于基本數(shù)據(jù)類型而言，一個(gè)排序算法是否穩(wěn)定策彤，影響很小栓袖，但是對于結(jié)構(gòu)體數(shù)組，穩(wěn)定排序就十分重要店诗。
下面是三種快排實(shí)現(xiàn)裹刮，其中針對特殊的情況
（1）對已排序的序列進(jìn)行快排
（2）對數(shù)字全部相同的一個(gè)序列進(jìn)行快排
上面兩種情況都會(huì)導(dǎo)致快排的時(shí)間復(fù)雜度達(dá)到O(n^2)，所以有了雙軸快排和隨機(jī)化快排
一庞瘸、經(jīng)典快排
public class QuickSort {
/**
* 快速排序算法
*/
public static void quickSort(int[] list, int left, int right) {
if (left < right) {
// 分割數(shù)組捧弃，找到分割點(diǎn)
int middle = partition(list, left, right);
// 遞歸調(diào)用，對左子數(shù)組進(jìn)行快速排序
quickSort(list, left, middle - 1);
// 遞歸調(diào)用擦囊，對右子數(shù)組進(jìn)行快速排序
quickSort(list, middle + 1, right);
}
}
/**
* 分割數(shù)組违霞，找到分割點(diǎn)
*/
public static int partition(int[] list, int left, int right) {
// 用數(shù)組的最后一個(gè)元素作為基準(zhǔn)數(shù)
int less = -1; // less區(qū)，小于基準(zhǔn)的元素都放在其左邊
while (left < right){
if(list[left] < list[right]){
less++;
swap(list, less, left);
}
left++;
}
swap(list, less+1, right);// 將基準(zhǔn)值放序列中間霜第，完成partition過程
return less+1;
}
/**
* 交換數(shù)組中兩個(gè)位置的元素
*/
public static void swap(int[] list, int left, int right) {
int temp;
if (list != null && list.length > 0) {
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
}
二葛家、雙軸快排
雙軸快排避免了由于待排序列是有序的，而導(dǎo)致時(shí)間復(fù)雜度達(dá)到O(n^2)的情況
public class QuickSort {
/**
* 快速排序算法
*/
public static void quickSort(int[] list, int left, int right) {
if (left < right) {
// 分割數(shù)組泌类，找到分割點(diǎn)
int middle = partition(list, left, right);
// 遞歸調(diào)用癞谒，對左子數(shù)組進(jìn)行快速排序
quickSort(list, left, middle - 1);
// 遞歸調(diào)用，對右子數(shù)組進(jìn)行快速排序
quickSort(list, middle + 1, right);
}
}
/**
* 分割數(shù)組刃榨，找到分割點(diǎn)
*/
public static int partition(int[] list, int left, int right) {
// 選取第一個(gè)元素為基準(zhǔn)
int flag = list[left];
while (left < right) {
while (left < right && list[right] >= flag) {
right--;
}
// 交換
swap(list, left, right);
while (left < right && list[left] <= flag) {
left++;
}
// 交換
swap(list, left, right);
}
// 返回分割點(diǎn)所在的位置
return left;
}
/**
* 交換數(shù)組中兩個(gè)位置的元素
*/
public static void swap(int[] list, int left, int right) {
int temp;
if (list != null && list.length > 0) {
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
}
三弹砚、隨機(jī)化快排
隨機(jī)數(shù)快排避免了由于待排序列是相同的數(shù)，而導(dǎo)致時(shí)間復(fù)雜度達(dá)到O(n^2)的情況
public class QuickSort {
/**
* 快速排序算法
*/
public static void quickSort(int[] list, int left, int right) {
if (left < right) {
// 分割數(shù)組枢希，找到分割點(diǎn)
int middle = partition(list, left, right);
// 遞歸調(diào)用桌吃，對左子數(shù)組進(jìn)行快速排序
quickSort(list, left, middle - 1);
// 遞歸調(diào)用，對右子數(shù)組進(jìn)行快速排序
quickSort(list, middle + 1, right);
}
}
/**
* 分割數(shù)組苞轿，找到分割點(diǎn)
*/
public static int partition(int[] list, int left, int right) {
// 隨機(jī)選取一個(gè)基準(zhǔn)
int length = right-left+1;
int index = new Random(47).nextInt()%(length+left);
// 將隨機(jī)基準(zhǔn)放到序列首部茅诱，之后以首部為基準(zhǔn)進(jìn)行快排
swap(list, left, index);
int flag = list[left];
while (left < right) {
while (left < right && list[right] >= flag) {
right--;
}
// 交換
swap(list, left, right);
while (left < right && list[left] <= flag) {
left++;
}
// 交換
swap(list, left, right);
}
// 返回分割點(diǎn)所在的位置
return left;
}
/**
* 交換數(shù)組中兩個(gè)位置的元素
*/
public static void swap(int[] list, int left, int right) {
int temp;
if (list != null && list.length > 0) {
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
}
以上是我在學(xué)習(xí)過程中對于快排的總結(jié)逗物，若有不足之處，歡迎評論瑟俭。
