目的

面试需要, 方便自己后续复习, 作此简单记录

资源

在B站找的, 一个老师讲的高频面试题视频, 我觉得是偏难的, 似乎都是大厂的面试题, 小公司我觉得都不咋问(个人认为).

核心思想

选择一个基准点, 形成一个比基准点大的分区和比基准点小的两个分区. 然后递归的去处理. 结束标识: 子分区元素个数小于等于1.

思想: 分而治之(divide-and conquer).

单边循环快排(lomuto洛穆托分区方案)

选择最右元素作为基准点元素j指针负责找到比基准点小的元素, 一旦找到则与i进行交换i指针维护小于基准点元素的边界, 也是每次交换的目标索引最后基准点与i交换, i即为分区位置

代码实现

public static void main(String[] args) {int[] arr = {5, 3, 7, 2, 9, 8, 1, 4};quick(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}private static void quick(int[] arr, int low, int high) {if (low >= high) {return;}int p = partition(arr, low, high);quick(arr, low, p - 1);quick(arr, p + 1, high);}/*** 分区* <p>* 左边元素都比基准点小, 右边都比基准点元素大** @param arr 待排序数组* @param low 分区的下边界* @param high 分区的上边界* @return 基准点元素最后的索引*/private static int partition(int[] arr, int low, int high) {// 选择上边界作为基准点元素int pv = arr[high];int i = low;for (int j = low; j < high; j++) {if (arr[j] < pv) {swap(arr, i, j);i++;}}swap(arr, high, i);return i;}// 交换private static void swap(int[] arr, int j, int i) {int temp = arr[j];arr[j] = arr[i];arr[i] = temp;}

如果觉得《面试题学习: 单边快速排序》对你有帮助，请点赞、收藏，并留下你的观点哦！