Berkeley CS 61B Homework8

shendezhuti 发表于 2019-5-23 19:36
本次作业整体还是比较简单的，（不过我还是参考了一下别人的clean code）大概是因为这个quicksort不是老师 ...

merge sort is not stable，因为q1 q2的顺序会影响相同key的顺序
而quick sort is stable，因为这是一种类似自顶向下的排序，有一个equal的queue在！

1. 开始在makeQueueOfQueues()我用了递归的做法，结果就是到10000个的时候就溢出了，不知道是自己的算法的问题还是这就是递归本身会存在的问题（这种会递归很多次的就是该避免用递归的方法？
2. 就在quicksort中，我开始分case的时候用的是if和else if结果在这里找了好久的bug。。。
3.另外我我觉得我写的的mergesort还是stable。。。然后自己按照看到的同学的思路写了一个testcase感觉还是stable（当然很可能是一个testcase不够），总之不太理解那个造成stable的原因，好想知道大家不stable的实现和我是哪里不同。。。贴一下我写的：

1. public static LinkedQueue mergeSortedQueues(LinkedQueue q1, LinkedQueue q2) {
   
2.     // Replace the following line with your solution.
   
3.     LinkedQueue newQueue = new LinkedQueue();
   
4.     Comparable front1, front2;
   
5.     while(q1.size()!=0||q2.size()!=0){
   
6.       try{
   
7.         front1 = (Comparable)q1.front();
   
8.       }catch (QueueEmptyException e) {
   
9.         System.out.println("EMPTY QUEUE!");
   
10.         front1 = null;
    
11.       }
    
12. 
    
13.       try{
    
14.         front2 = (Comparable)q2.front();
    
15.       }catch (QueueEmptyException e) {
    
16.         System.out.println("EMPTY QUEUE!");
    
17.         front2 = null;
    
18.       }
    
19. 
    
20.       if (front2==null) {
    
21.         newQueue.enqueue(front1);
    
22.         try{
    
23.           q1.dequeue();
    
24.         }catch (QueueEmptyException e) {
    
25.           System.out.println("EMPTY QUEUE!");
    
26.         }
    
27.       }else if(front1==null){
    
28.         newQueue.enqueue(front2);
    
29.         try{
    
30.           q2.dequeue();
    
31.         }catch (QueueEmptyException e) {
    
32.           System.out.println("EMPTY QUEUE!");
    
33.         }
    
34.       }else if (front1.compareTo(front2)<=0) {
    
35.         newQueue.enqueue(front1);
    
36.         try{
    
37.           q1.dequeue();
    
38.         }catch (QueueEmptyException e) {
    
39.           System.out.println("EMPTY QUEUE!");
    
40.         }
    
41.       }else{
    
42.         newQueue.enqueue(front2);
    
43.         try{
    
44.           q2.dequeue();
    
45.         }catch (QueueEmptyException e) {
    
46.           System.out.println("EMPTY QUEUE!");
    
47.         }
    
48.       }
    
49.     }
    
50.    
    
51.     return newQueue;
    
52.   }

复制代码

附上截图：

跟着readme做就可以了，明白每个method是什么才行。没什么新的知识点。
主要是while和if判断那里有问题，debug了很久，时间花费性价比很低，标明了学习一下。
学习到了以后输出有误，但是没有报错，不如重写if，while，for等语句，重新规划逻辑，使其更精简一些。