- pivot 选择数组第一个元素
/**
* 以第一个元素作为基准
* 不稳定
* @param arr
* @param startIndex
* @param endIndex
*/
public static void quickSort(int[] arr, int startIndex, int endIndex) {
if (startIndex < endIndex) {
int pivotPos = partition(arr, startIndex, endIndex);
quickSort(arr, startIndex, pivotPos - 1);
quickSort(arr, pivotPos + 1, endIndex);
}
}
public static int partition(int[] arr, int startIndex, int endIndex) {
int pivot = arr[startIndex];
int i = startIndex, j = endIndex;
// 如果 i = startIndex+1 有个坑, 当startIndex+1 = endIndex时，此时 i=j，跳过 while
// 直接交换 startIndex j=endIndex，导致结果错误，解决设置 i=startIndex
while (i < j) {
while (i < endIndex && arr[i] <= pivot) i++;
while (j > startIndex && arr[j] >= pivot) j--;
// arr[i]<=pivot 一定要加 = ，防止 a[i] =pivot a[j] = pivot,i<j 陷入死循环
// 三种情况
// arr[i] > pivot arr[j] < pivot
// i = endIndex ,j = endIndex pivot 最大
// i= startIndex+1 , j = startIndex pivot 最小
if (i < j) {
swap(arr, i, j);
}
}
// 交换 a[startIndex] a[j]
swap(arr, startIndex, j);
// j 为 pivot 所在位置
return j;
}
- pivot 选择数组最后一个元素
/**
* 以最右元素作为基准
* @param a
* @param startIndex
* @param endIndex
* @return
*/
public static int partition2(int[] a, int startIndex, int endIndex) {
int pivot = a[endIndex];
int i = startIndex, j = endIndex;
while (i < j) {
while (i < endIndex && a[i] <= pivot) i++;
while (j > startIndex && a[j] >= pivot) j--;
if (i < j) {
swap(a, i, j);
}
}
// pivot 位置应在索引 i 处，交换 a[endIndex] 、a[i]
swap(a, endIndex, i);
return i;
}
/**
* @param a
* @param startIndex
* @param endIndex
*/
public static void quickSort2(int[] a, int startIndex, int endIndex) {
if (startIndex < endIndex) {
int pivot = partition2(a, startIndex, endIndex);
quickSort2(a, startIndex, pivot - 1);
quickSort2(a, pivot + 1, endIndex);
}
}
