快速排序自己的標準寫法
public static void quickSort(int[] arr, int low, int high) {
// low,high 為每次處理數(shù)組時的首贺氓、尾元素索引
// 當low==high是表示該序列只有一個元素谋币，不必排序了
if (low >= high) {
return;
}
// 選出哨兵元素和基準元素棺克。這里左邊的哨兵元素也是基準元素
int i = low, j = high, base = arr[low];
while (i < j) {
// 右邊哨兵從后向前找
while (arr[j] >= base && i < j) {
j--;
}
// 左邊哨兵從前向后找
while (arr[i] <= base && i < j) {
i++;
}
swap(arr, i, j); // 交換元素
}
swap(arr, low, j); // 基準元素與右哨兵交換
// 遞歸調(diào)用，排序左子集合和右子集合
quickSort(arr, low, j - 1);
quickSort(arr, j + 1, high);
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
獲取基準元素的位置的時候咒吐，先從右哨兵節(jié)點開始野建，再從左哨兵節(jié)點開始，退出循環(huán)后將基準元素和右哨兵節(jié)點交換位置恬叹，此時基準元素就位候生。
