婚纱网站排行,成都软件外包开发,怎么去建设微信网站,泰安千橙网络科技有限公司由于之前做有一题看到题解用了快排提升效率#xff0c;就浅学了一下快速排序#xff0c;还是似懂非懂。 首先快排的核心有两点#xff0c;哨兵划分和递归。 哨兵划分#xff1a;以数组中的某个数#xff08;一般为首位#xff09;为基准数#xff0c;将数组划分为两个部… 由于之前做有一题看到题解用了快排提升效率就浅学了一下快速排序还是似懂非懂。 首先快排的核心有两点哨兵划分和递归。 哨兵划分以数组中的某个数一般为首位为基准数将数组划分为两个部分小于基准数的都在左部分大于基准数的都在右部分。也就是说此时基准数的位置已经正确了递归除了基准数已经处于正确位置其他两部分还需要继续递归执行哨兵划分当划分到子数组长度都为 1 了那就没什么好划分的了说明此时数组已经排序完了。示例代码如下 // 递归部分// lr子数组左右边界public void quickSort(int[] nums, int l, int r){// 说明数组长度被划分到此时为 1 了if(lr)return;// i 为基准数坐标此时 i 左部分都小于 nums[i]右部分大于 nums[i]int ipartition(nums, l, r);// 对左右两部分递归执行哨兵划分quickSort(nums,l,i-1);quickSort(nums,i1,r);}// 哨兵划分int partition(int[] nums, int l, int r) {int il, jr;while(ij){// 先从右边往前找比基准数小的这个 ij 的作用是// 首先不会数组越界其次它保证了不会出现错误的交换// 因为 i 左边的都是划分完的j 右边的也都是划分完的不应该再变动while(i j nums[j] nums[l]) j--;// 再从左边往后找比基准数大的while(i j nums[i] nums[l]) i;// 然后把小的换到左边大的换到右边swap(nums, i, j);}// 因为此时大致为// l i j// 中 小 小 大 大// 所以最后还需要把基准数移到正确的位置swap(nums, i, l);return i;}// 交换 nums[i] 和 nums[j]void swap(int[] nums, int i, int j) {int tmp nums[i];nums[i] nums[j];nums[j] tmp;}时间复杂度的话不难看出哨兵划分操作是 O(N)递归是递归 logN 轮所以时间复杂度 O(logN) ,所以总共是 O(N logN)最差情况下每次哨兵划分都划分出 N-1 长度的数组以及长度 1 的数组那时间复杂度就为 O(N2) 了空间复杂度的话递归深度最好的情况平均情况下都是 logN数组完全倒序让你排成正序那深度就为 N 了
算法优化 快排常见优化手段有「Tail Call」和「随机基准数」两种 Tail Call 上面也说了因为是选取最左边的数为基准数所以如果数组完全倒序那么递归深度就会达到 N也就是说最差空间复杂度为 O(N) 每轮递归时仅对 较短的子数组 执行哨兵划分 partition() 就可将最差的递归深度控制在 O(logN) 每轮递归的子数组长度都 ≤ 当前数组长度 / 2即实现最差空间复杂度 O(logN) 那么只需要修改 quickSort 部分即可 void quickSort(int[] nums, int l, int r) {// 子数组长度为 1 时终止递归while (l r) {// 哨兵划分操作int i partition(nums, l, r);// 仅递归至较短子数组控制递归深度if (i - l r - i) {quickSort(nums, l, i - 1);l i 1;} else {quickSort(nums, i 1, r);r i - 1;}}}随机基准数 由于每次都是取数组首位为基准数所以当数组完全有序或完全倒序时partition() 每次都是只划分了一个元素。也就是说当前情况下选择首位为基准数是最差的选择但是我们仍然每次都坚定选择了最差的选择。 那么使用随机函数 每轮在子数组中随机选择一个元素作为基准数就可以极大概率避免以上劣化情况。 值得注意的是由于仍然可能出现最差情况运气真的差到极点每次都随机到首位跟不随机一样因此快速排序的最差时间复杂度仍为 O(N2) 。 代码仅需修改 partition() 方法其余方法不变在此省略。这个就很好理解了 int partition(int[] nums, int l, int r) {// 在闭区间 [l, r] 随机选取任意索引并与 nums[l] 交换int ra (int)(l Math.random() * (r - l 1));swap(nums, l, ra);// 以 nums[l] 作为基准数int i l, j r;while (i j) {while (i j nums[j] nums[l]) j--;while (i j nums[i] nums[l]) i;swap(nums, i, j);}swap(nums, i, l);return i;}参考原文
