左右指针法容易出现问题的地方是一趟快速排序相遇时的处理方式
如果参考在末尾,要先从左走
如果参考在数组头部,要先从右走
参考在数组头部,要先从右走
private static int partition(int[] array, int left, int right) {
int key = array[left];
int index = left;
while (left < right) {
while (left < right && array[right] <= key) {
--right;
}
while (left < right && array[left] >= key) {
++left;
}
swap(array, left, right);
}
swap(array, right, index);
return right;
}
private static void swap(int[] cost, int i, int j) {
int temp = cost[i];
cost[i] = cost[j];
cost[j] = temp;
}
参考在末尾,要先从左走
private static int partition2(int[] array, int left, int right) {
int key = array[right];
int index = right;
while (left < right) {
while (left < right && array[left] <= key) {
++left;
}
while (left < right && array[right] >= key) {
--right;
}
swap(array, left, right);
}
swap(array, left, index);
return left;
}
网友评论