介紹
- 核心是跳位比較和交換
隨機的在數(shù)組中選一個數(shù)诚啃，小于等于它的數(shù)淮摔，統(tǒng)一放在這個數(shù)的左邊，
大于等于它的數(shù)始赎，統(tǒng)一放在這個數(shù)的右邊和橙，接下來對左右兩個部分顾彰，
分別遞歸的調(diào)用快速排序的過程，這樣整個數(shù)組就有序了胃碾。
指標(biāo)
時間復(fù)雜度
空間復(fù)雜度
一. 單軸（普通）快排
partition
遞歸左右部分
代碼
public class QuickSort {//普通快排
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
swap(arr, l + (int) (Math.random() * (r - l + 1)), l);
int pivot = arr[l];
int i = l + 1, j = r;
while (i <= j) {
while (i <= j && arr[i] < pivot) {
i++;
}
while (i <= j && arr[j] >= pivot) {
j--;
}
if (i <= j) {
swap(arr, i, j);
}
}
swap(arr, l, j);// 將pivot交換到中間
quickSort(arr, l, j - 1);// 中心點左半部分 遞歸
quickSort(arr, j + 1, r);// 中心點右半部分 遞歸
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = new int[] { 3, 5, 4, 2, 6, 7, 1, 9, 8 };
quickSort(arr);
printArray(arr);
}
}
輸出
排序后
二. 雙軸快排
代碼
public class QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
// 隨機選擇pivot,并且放在尾部；規(guī)避數(shù)據(jù)狀況
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
// 空間復(fù)雜度O(logn)筋搏，是能二分的次數(shù)仆百，要記錄每次壓棧的位置
int[] p = partition(arr, l, r);
// patition返回值是等于p的區(qū)域的起止下標(biāo)，下面分別對 小于和大于區(qū)域 快排
quickSort(arr, l, p[0] - 1);//---小于區(qū)域
quickSort(arr, p[1] + 1, r);//---大于區(qū)域
}
}
//返回等于區(qū)域的位置
public static int[] partition(int arr[], int left, int right) {
int index = left; // 當(dāng)前位置索引
int less = left - 1; // 小于區(qū)域
int more = right; // 大于區(qū)域
// ---------------往 小于區(qū) 和 大于區(qū) “發(fā)貨 ”--------------
while (index < more) { // 當(dāng)前位置一直向右推移奔脐，一定會遇到大于區(qū)域
if (arr[index] < arr[right]) {// ------ arr[right]就是pivot-----
// 當(dāng)前位置的數(shù)與小于區(qū)域的下一個數(shù)交換俄周，然后當(dāng)前位置下移一位 (擴大小于區(qū)域)
swap(arr, index++, ++less);
} else if (arr[index] > arr[right]) {
// 當(dāng)前位置的數(shù)與大于區(qū)域的前一個數(shù)交換，因為剛交換過來的數(shù)不知道大小髓迎，所以需要繼續(xù)比較
swap(arr, index, --more);
} else {
//中間是等于區(qū)域峦朗， 等于的情況只需要當(dāng)前位置下移一位
index++;
}
}
swap(arr, more, right);
// 返回一個等于區(qū)域的左右邊界
return new int[] { less + 1, more };
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = new int[] { 3, 5, 4, 2, 6, 7, 1, 9, 8 };
quickSort(arr);
printArray(arr);
}
}
右邊在排序完成之前是待定大小
右邊在排序完成之前是待定大小，所以more換過來一個數(shù)排龄，cur要停在原地再判定一次波势。
輸出
排序后
經(jīng)典快排，原始數(shù)據(jù)有序時橄维，復(fù)雜度可能最差O（N2）
參考文章
算法課程
單軸快排（SinglePivotQuickSort）和雙軸快排（DualPivotQuickSort）及其JAVA實現(xiàn)
