快速排序的思路整理

快速排序的实现

package algorithm; import java.util.Arrays; public class QuicklySort { public static void main(String[] args) { int[] arr1 = { 45, 28, 80, 90, 50, 16, 100, 10 }; // 快速排序详解 quicklySort(arr1, 0, arr1.length - 1); echoArr(arr1); int[] arr2 = { 45, 28, 80, 90, 50, 16, 100, 10 }; // 快速排序纯代码 codeSort(arr2, 0, arr2.length - 1); echoArr(arr2); } // 快速排序 public static void quicklySort(int[] arr, int left, int right) { // 基准数 默认取第一个数 可优化 int base = arr[left]; // 左侧指针 // 最外层递归初始值为 0,子递归为对应计算下标值 int pointLeft = left; // 右侧指针 // 最外层递归初始值为 arr.length - 1,子递归为对应计算下标值 int pointRight = right; // 左指针小于右指针 while (pointLeft < pointRight) { /* * L pointLeft * R pointRight * B base * * L/B R * 0 1 2 * 执行循环,指针将会右移动 */ while (pointLeft < pointRight && arr[pointRight] >= base) { pointRight --; } /* * * L/B/R * 0 1 2 * 循环结束，若： * L == R 说明右侧值全部比当前基准数大 * * * * L/B R * 5 6 2 7 * * L/B R * 5 6 2 7 * * 上述情况会 break; * * 循环结束，若： * L < R 说明右侧有值比基准数小 */ if(pointLeft < pointRight) { // 在以上循环中，右侧找到了比基准数大的数 /* * L/B R * 5 6 2 7 * * 执行变量更替 * B = 5 * * L R * 2 6 5 7 */ int temp = arr[pointRight]; arr[pointRight] = arr[pointLeft]; arr[pointLeft] = temp; /* * L R * 2 6 5 7 * * 左侧指针挪动 * * L R * 2 6 5 7 */ pointLeft ++; } /* * 上述情况如下 不会进入循环 * L R * 2 6 5 7 * * * * 此种情况 会进入循环 * L R * 2 3 9 8 5 7 * */ while (pointLeft < pointRight && arr[pointLeft] <= base) { /* * L R * 2 3 9 8 5 7 * * 执行指针的移动 * * * L R * 2 3 9 8 5 7 * 循环 break * * 可能有数据在此步骤会导致 L == R 本次循环推出 * * 或 L < R 执行下方 if 处理逻辑 */ pointLeft ++; } /* * L R * 2 6 5 7 * * 或者 * L R * 2 3 9 8 5 7 * * 都可进入 if */ if(pointLeft < pointRight) { /* * * 先执行数据交换 * * =======第一种======== * * L R * 2 6 5 7 * * L R * 2 5 6 7 * * =======第二种======== * * L R * 2 3 9 8 5 7 * * L R * 2 3 5 8 9 7 */ int temp = arr[pointRight]; arr[pointRight] = arr[pointLeft]; arr[pointLeft] = temp; /* * * 执行指针移动 * * =======第一种======== * * L R * 2 5 6 7 * * L/R * 2 5 6 7 * * 本情况下次递归传参 参数会导致递归出口 * * =======第二种======== * * L R * 2 3 9 8 5 7 * * L R * 2 3 5 8 9 7 */ pointRight --; } /* * 循环结束 若 L < R 其中可能包含更多未排序数据 如 * * L R * 2 3 5 8 3 8 9 7 * * 再次执行 while 体,直至 L == R 分段完成; * * L R * - - 5 8 3 8 - - */ } // 至此 本次递归基准数分段完成 // 开始递归调用 /* * left == L === R == right * x * 此时不能进行递归调用 否则死递归 * 添加判断条件 */ if(left < pointLeft) { quicklySort(arr, left, pointLeft - 1); } if(pointLeft < right) { quicklySort(arr, pointLeft + 1, right); } } // 快速排序 纯代码 public static void codeSort(int[] arr, int left, int right) { int base = arr[left]; int pointLeft = left; int pointRight = right; while (pointLeft < pointRight) { while (pointLeft < pointRight && arr[pointRight] >= base) { pointRight --; } if(pointLeft < pointRight) { int temp = arr[pointRight]; arr[pointRight] = arr[pointLeft]; arr[pointLeft] = temp; pointLeft ++; } while (pointLeft < pointRight && arr[pointLeft] <= base) { pointLeft ++; } if(pointLeft < pointRight) { int temp = arr[pointRight]; arr[pointRight] = arr[pointLeft]; arr[pointLeft] = temp; pointRight --; } } if(left < pointLeft) { codeSort(arr, left, pointLeft - 1); } if(pointLeft < right) { codeSort(arr, pointLeft + 1, right); } } // 输出数组内容的方法 public static void echoArr(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+ " "); } System.out.println(); } }

附本机执行结果如下：

10 16 28 45 50 80 90 100 10 16 28 45 50 80 90 100