app嵌入手机网站,站内推广方案,华为最新版,淘宝网站内站建设现状一、快速排序描述
每一轮排序选择一个基准点#xff08;pivot#xff09;进行分区 1.1. 让小于基准点的元素的进入一个分区#xff0c;大于基准点的元素的进入另一个分区 1.2. 当分区完成时#xff0c;基准点元素的位置就是其最终位置在子分区内重复以上过程#xff0c;直…一、快速排序描述
每一轮排序选择一个基准点pivot进行分区 1.1. 让小于基准点的元素的进入一个分区大于基准点的元素的进入另一个分区 1.2. 当分区完成时基准点元素的位置就是其最终位置在子分区内重复以上过程直至子分区元素个数少于等于 1这体现的是分而治之的思想 divide-and-conquer从以上描述可以看出一个关键在于分区算法常见的有洛穆托分区方案、双边循环分区方案、霍尔分区方案。
二、单边循环快排lomuto 洛穆托分区方案
选择最右元素作为基准点元素j 指针负责找到比基准点小的元素一旦找到则与 i 进行交换i 指针维护小于基准点元素的边界也是每次交换的目标索引最后基准点与 i 交换i 即为分区位置
public static void quick(int[] a, int l, int h) {if (l h) {return;}// p 索引值int p partition(a, l, h); // 左边分区的范围确定quick(a, l, p - 1); // 右边分区的范围确定quick(a, p 1, h);
}private static int partition(int[] a, int l, int h) {// 基准点元素int pv a[h]; int i l;for (int j l; j h; j) {if (a[j] pv) {if (i ! j) {swap(a, i, j);}i;}}if (i ! h) {swap(a, h, i);}System.out.println(Arrays.toString(a) i i);// 返回值代表了基准点元素所在的正确索引用它确定下一轮分区的边界return i;
}三、双边循环快排不完全等价于 hoare 霍尔分区方案
选择最左元素作为基准点元素j 指针负责从右向左找比基准点小的元素i 指针负责从左向右找比基准点大的元素一旦找到二者交换直至 ij 相交最后基准点与 i此时 i 与 j 相等交换i 即为分区位置
要点 1、基准点在左边并且要先 j 后 i 2、while( i j a[j] pv ) j– 3、while ( i j a[i] pv ) i
private static void quick(int[] a, int l, int h) {if (l h) {return;}int p partition(a, l, h);quick(a, l, p - 1);quick(a, p 1, h);
}private static int partition(int[] a, int l, int h) {int pv a[l];int i l;int j h;while (i j) {// j 从右找小的while (i j a[j] pv) {j--;}// i 从左找大的while (i j a[i] pv) {i;}swap(a, i, j);}swap(a, l, j);System.out.println(Arrays.toString(a) j j);return j;
}四、快排特点
平均时间复杂度是 O(nlog2n)O(nlog_2n )O(nlog2n)最坏时间复杂度 O(n2)O(n^2)O(n2)数据量较大时优势非常明显属于不稳定排序
