思路
把一個陣列切分成兩個子陣列的基本思想：
- 找一個基準值，用兩個指標分別指向陣列的頭部和尾部；
- 先從尾部向頭部開始搜索一個比基準值小的元素，搜索到即停止，并記錄指標的位置
- 再從頭部向尾部開始搜索一個比基準值大的元素，搜索到即停止，并記錄指標的位置；
- 交換當前左邊指標位置和右邊指標位置的元素；
- 重復2,3,4步驟，直到左邊指標的值大于右邊指標的值停止，
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int fun = fun(arr, left, right);
quickSort(arr, left, fun - 1);
quickSort(arr, fun + 1, right);
}
/**
* 對陣列，從索引lo到索引hi之間的元素進行分組并回傳分組界限對應的索引
*
* @param arr
* @param left
* @param right
*/
public static int fun(int[] arr, int left, int right) {
int l = left + 1;//左邊索引
int r = right;//右邊索引
int key = arr[left];//取最左邊一個數為基值
while (true) {
while (l < r) {//從左往右遍歷，找到比基值大的數
if (arr[l] > key) break;
l++;
}
while (l <= r) {//從右往左遍歷
if (arr[r] < key) break;
r--;
}
//交換
if (l >= r) break;
else exchage(arr, l, r);
}
//把左邊第一個元素和r索引交換
exchage(arr, left, r);
return r;
}
/**
* 交換元素
*
* @param arr
* @param i
* @param j
*/
public static void exchage(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
速度
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/243887.html
標籤：其他