常见的三种双指针索引while判断
(1) while(left + 1 < right){
// to do
// update
left++;
right--;
}
奇数情况下:left和right指针相遇就退出
偶数情况下:left和right指针相邻就退出
(2) while(left < right){
// to do
// update
left++;
right--;
}
奇数情况下:left和right指针相遇就退出
偶数情况下:left和right 对半遍历
(3) while(left <= right){
// to do
// update
left++;
right--;
}
奇数情况下:left和right指针 对半遍历
偶数情况下:left和right指针 对半遍历
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
int m = Integer.parseInt(sc.nextLine());
int[] nums = new int[m];
String[] strs = sc.nextLine().split(" ");
for(int i = 0; i < m; ++i){
nums[i] = Integer.parseInt(strs[i]);
}
quickSort(nums, 0, m - 1);
for(int num : nums){
System.out.print(num + " ");
}
}
public static void quickSort(int[] nums, int start, int end){
if(start >= end) return;
int left = start;
int right = end;
// 我在这里犯了一个错误, mid = left + (right - left) / 2
// 试图用nums[mid]代替 target
// 因为每次更新 left right 值都会变,那么nums[mid]所指向的值就会不停的变化
int target = nums[start + (end - start) / 2];
// 无论nums.length 为偶数还是奇数, left 和 right 指针都是对半遍历
while(left <= right){
while(nums[left] < target){left++;};
while(nums[right] > target){right--;};
// 因为left right 进行了更新,所以要对left和right进行判断
if(left <= right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
quickSort(nums, start, right);
quickSort(nums, left, end);
}
}