雙指針快速排序是一種優化的快速排序實現,通過使用兩個指針從數組的兩端向中間移動,來減少不必要的交換操作,從而提高排序效率。以下是使用雙指針實現快速排序的 Java 代碼示例:
public class QuickSortDoublePointer {
public static void main (String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
public static void quickSort(int[] arr, int low, int high) {
if (low <= high) {
// 找到基準元素的最終位置
int pivotIndex = partition(arr, low, high);
// 遞歸地對基準元素左邊的子數組進行排序
quickSort(arr, low, pivotIndex - 1);
// 遞歸地對基準元素右邊的子數組進行排序
quickSort(arr, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
// 選擇最右邊的元素作為基準
int pivot = arr[high];
// 初始化兩個指針
int left = low;
int right = high - 1;
while (left <= right) {
while (left <= right && arr[left] < pivot) {
left++;
}
while (left <= right && arr[right] >= pivot) {
right--;
}
// 如果左指針小于右指針,交換兩個元素
if (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left ++;
right --;
}
}
// 將基準元素放到正確的位置
int temp = arr[left];
arr[left] = arr[high];
arr[high] = temp;
// 返回基準元素的最終位置
return left;
}
}
浙公網安備 33010602011771號