摘要:理解最关键的是结束后各个指针的状态,以及下一步递归的起止点。上面的模板在结束时是的状态,但是不确定中间还有没有一个数,如下图今天在图书馆写码没有带板子,就先照个图了注意里是里一定要注意这个灵活多变照这个思路的相关题
首先是记录一个quick sort的模板(思想是遇到不符合顺序的就交换,很好理解):
public void quickSort(int[] nums, int start, int end){
if(start < end){ int i = start; int j = end; int pivot = nums[(i + j) / 2]; while(i <= j){ while(i <= j && nums[i] < pivot){ i++; } while(i <= j && nums[j] > pivot){ j--; } if(i <= j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; i++; j--; } } quickSort(nums, start, j); quickSort(nums, i, end); }
}
基于快速排序里这个pivot的思想,有一个衍生quick Select, 用来解决一些类似于求中位数啦,kth数字啦之类(第几个第几个可以联想到pivot)的问题,时间复杂度也比快速排序有所降低。理解quick sort, quick select最关键的是结束partition后各个指针的状态,以及下一步递归的起止点。上面的模板在结束时是i
注意quickSort里是(start < end), quickSelect里一定要注意这个灵活多变
照这个思路的相关题:
[LeetCode 215] Kth Largest Element in an Array
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/70020.html
摘要:对于实在不能理解的同学,听我的吧这是死东西,那你就背下来背下来背下来。就说三遍,背完之后,还不能理解,那我也不能理解了。 sort.js JavaScript to achieve the ten common sorting algorithm library 这个小库是对常见的十大排序算法的一个基本汇总,建议读者直接看源码|看源码|看源码。别怕,我注释十分清晰,你要是还看不懂,给...
Problem Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm. Example Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5]. Note 考察对Heap Sort, Q...
摘要:因为直接插入排序在元素基本有序的情况下接近最好情况,效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。 插入排序 def insert_sort(list): n = len(list) for i in range(1, n): key = list[i] for j in range(i-1, -1, -1): ...
摘要:年马上到尾声了,在这里总结一下基于和这四大框架衍生的,经受过时间检验深受广大开发者欢迎的框架。可以说是年最火的引擎类前端框架,以其美观的设计和高质量的组件很快俘获了一大批的芳心。 前端领域最近几年发展的特别迅速,可以说是百家争鸣。在底层的前端框架领域中,最早是jquery称霸互联网,近两年MVVM类型的框架慢慢成为主流,Vue、React和Angular三大框架并驾齐驱。可以说,目...
阅读 3431·2021-10-13 09:39
阅读 1397·2021-10-08 10:05
阅读 2224·2021-09-26 09:56
阅读 2242·2021-09-03 10:28
阅读 2637·2019-08-29 18:37
阅读 1999·2019-08-29 17:07
阅读 565·2019-08-29 16:23
阅读 2113·2019-08-29 11:24