数据结构与算法帮你记之——归并排序和快速排序
程序员文章站
2022-03-19 22:15:22
归并排序和快速排序是面试常考的两大排序,两者平均时间复杂度均可以达到O(nlogn)。接下来将记录一下这两种排序的动图原理显示以及代码的记忆方式。 归并排序 一、动图展示 动图原文链接:https://blog.csdn.net/qq_36442947/article/details/8161287 ......
归并排序和快速排序是面试常考的两大排序,两者平均时间复杂度均可以达到o(nlogn)。接下来将记录一下这两种排序的动图原理显示以及代码的记忆方式。
归并排序
一、动图展示
动图原文链接:https://blog.csdn.net/qq_36442947/article/details/81612870
二、做法及思路
在java中,万物皆对象。因此我们可以尝试以面向对象的思想来进行编写。
- 定义一个类mergesort,并为其添加私有成员变量arr数组和数组长度arraylength,当然,也需要添加必要的getset方法;
- 定义public的mergesort方法作为向外提供的排序接口,这个方法主要实现:判断数组是否为空,以及msort函数的调用;
- 定义一个private的msort方法作为正式开始,这个方法主要实现:将数组不断拆分到不可拆为止,最后再将拆完的单个元素数组合并为两个元素、四个元素等等。。。从动图可以看到这个过程是循环往复的,因此可以考虑采用递归来实现,边界条件就是开始角标小于结束角标;
- 定义一个merge方法专门用来将两个小单元进行合并,合并的思路就像上面图片那样,这里我们需要新建一个中间数组用来存放合并后的结果:
- 一前一后有两个指针,分别指向待合并两部分的开头;
- 当前一个指向的元素更小时,令前一个元素赋值给中间数组tmp,前一个的指针向后移动;
- 同样的,当后一个指向的元素更小时,令后一个元素赋值给tmp,后一个指针也++;
- 我们知道,这样做并不能保证两个数组同时完成自己的任务,因此最终一定会剩下左右其中一个数组还没有全部放入tmp,这个时候就对没有操作完的数组的剩余部分全部放到tmp中;
- 最后,我们并不想直接返回这个中间数组,因此需要将中间数组赋值给我们类中的arr数组。
过程还是较多的,但其中很大部分都是很容易想到的。上面说的难免有遗漏,可以看注释:
1 public class mergesort { 2 private int[] arr; 3 4 private int arraylength; 5 6 public mergesort(int arr[]){ 7 this.arr = arr; 8 setarraylength(); 9 } 10 public void setarr(int[] arr) { 11 this.arr = arr; 12 setarraylength(); 13 } 14 15 public int[] getarr() { 16 return arr; 17 } 18 19 public void setarraylength() { 20 if(arr!=null) 21 this.arraylength = arr.length; 22 } 23 24 public void mergesort(){ 25 if(arr!=null){ 26 int[] temp = new int[arraylength]; 27 msort(0, arr.length-1, temp); 28 } 29 else{ 30 // throw new runtimeexception(); 31 system.out.println("待排序数组为空"); 32 } 33 } 34 /*保证共用一个temp,节省内存*/ 35 private void msort(int start, int end, int[] temp){ 36 int center; 37 if(start<end){ 38 center = (start+end)/2; 39 msort(start, center, temp); 40 msort(center+1, end, temp); 41 merge(start, center, end, temp); 42 } 43 } 44 /*left: the begin of left 45 * right: the end of right 46 * center: the end of left*/ 47 private void merge(int leftst, int center, int right, int[] temp){ 48 int tmppos = leftst; 49 int rightst = center+1; 50 while(leftst<=center && rightst<=right){ 51 if(arr[leftst]<arr[rightst]){ 52 temp[tmppos++]=arr[leftst++]; 53 } 54 else{ 55 temp[tmppos++]=arr[rightst++]; 56 } 57 } 58 while(leftst<=center){ 59 temp[tmppos++]=arr[leftst++]; 60 } 61 while(rightst<=right){ 62 temp[tmppos++]=arr[rightst++]; 63 } 64 //向arr转移tmp存储的数组,这里要注意:上面的操作已经打乱了left的位置,所以只能使用未被打乱的right角标,然后倒着赋值 65 for(int i=0; i<right-leftst+1; i++, right--){ 66 arr[right] = temp[right]; 67 } 68 } 69 70 public void printarr(){ 71 for(int i=0; i<arraylength; i++){ 72 system.out.print(arr[i]+" "); 73 } 74 } 75 }
可以看到除了我们自己添加的一些非重要代码,正式的归并排序代码仅有三十行左右。
上一篇: 委托入门案例