赞
踩
提示:整个算法界,一共有十大排序算法,每一个算法都要熟悉,才算是算法入门
算法界的十大排序算法分别是:
选择排序、冒泡排序、插入排序、堆排序、希尔排序、归并排序、快速排序、桶排序、计数排序,基数排序。
(1)选择排序:10大排序算法之一:选择排序【不稳定】,一般不用选择排序的
(2)冒泡排序:10大排序算法之二:冒泡排序【稳定的】,但复杂度高,一般不用冒泡排序的
(3)插入排序:10大排序算法之三:插入排序【稳定的】,复杂度高,系统常在数据少时用插入排序。
(4)归并排序:10大排序算法之四:归并排序【稳定的】,复杂度中,系统常用归并排序
(5)快速排序:10大排序算法之五:快速排序【不稳定】,复杂度中,系统常用快速排序
如果你想进互联网大厂,至少这上面的其中最重要的8种,是必须熟练掌握的:
去掉希尔排序,希尔排序是一种改进的插入排序算法——所以只需要掌握插入排序
桶排序中最重要的就是计数排序和基数排序,都是桶的思想
根据算法复杂度低一点的,又稳定的
咱们可以最常用的算法实际上就四种:
插入排序(o(n^2))【当数据量小时,这个方法简单】【稳定】、
堆排序o(nlog(n))【不稳定】、
归并排序o(nlog(n))【稳定】,
快速排序o(nlog(n))(虽然快排不稳定,但是很多不需要稳定情况下,快排非常快)
因此,o(n)的桶排序很少用,除非面试官特别申明,否则都用比较排序。
归并排序是最常用的,复杂度低,而且稳定,达到了一个非常好的折中。
请你用堆排序算法,将arr排序为升序
示例:arr = 5 3 1 8 6 2 4
让其最终变为:arr= 1 2 3 4 5 6 8
上一篇文章,我花了重功夫,讲了系统的堆结构,如何手动改写堆结构?
我把大根堆和小根堆的实现与代码都写好了:
咱们今天要说的堆排序,重要的根基知识就是堆结构,这个堆结构
重要的事情,说三遍:
堆结构远比堆排序重要!
堆结构远比堆排序重要!
堆结构远比堆排序重要!
有了咱们实现的堆结构,那排序一事就很简单了
咱这样做:
最开始,我们认为arr就是小根堆中的缓存,只不过heapSize=0,实际容量还没有呢
(1)索引arr的i=0–N-1每一个位置,利用heapInsert(int[] arr, int i)函数,不断地纳入i位置,将其加入小根堆arr;
(2)然后你会发现,小根堆已经成型了!!!arr自然已经有序了
复杂度每次i加入都会以log(n)复杂度调整,上浮的动作
需要调整N次
所以复杂度为 o(n*log(n))
这与归并排序,快速排序的复杂度一样的
但是,因为堆来回调整,整个顺序乱了,同样的数字相对位置已经无法保证,所以堆排序它不稳定,咱们也不常用的。
利用小根堆做堆排序:手撕代码,很简单了:
//利用小根堆:做堆排序 public static void heapSortUsingSmallHeap(int[] arr){ if (arr == null || arr.length < 2) return; int N = arr.length; SmallHeap heap = new SmallHeap(N);// for (int i = 0; i < N; i++) { heap.add(arr[i]); } //arr已经有序了 for (int i = 0; i < N; i++) { arr[i] = heap.poll(); } } //测试堆排序: public static void test5(){ int[] arr = {5, 3, 1, 8, 6, 2, 4}; heapSortUsingSmallHeap(arr); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] +" "); } } public static void main(String[] args) { // checker(); // test(); // test2(); // test3(); // test4(); test5(); }
复杂度也挺高的,何必呢?所以也不常用
但是堆排序的思想可以理解
重要的是堆结构
提示:重要经验:
堆结构远比堆排序重要!
堆结构远比堆排序重要!
堆结构远比堆排序重要!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。