Berkeley CS 61B Homework8

homework 8 是对一个queue（实质是一个单向链表）完成mergesort和quicksort，然后分别对比 对100、1000、10000、100000、1000000的size的queue进行mergesort和quicksort的时间。
这个作业挺简单的。
刚开始贴不了图+_+ 后来可以了。。。

一开始在mergeSortedQueues()中想到的是用nth()方法通过count i和j来对比q1和q2中值的大小，也能做出来。后面开始计时之后发现这个方法特别慢，因为每调用一次nth(n)方法，他都要进行n次循环，大大增加了计算次数。后来就干脆用front()得到的值进行对比,再用dequeue()和enqueue()方法。Linkedlist有remove first node的操作，但如果是Array的话就要用到count了。

在我的算法中，归并排序的merge函数在q1 q2 元素相等时每次优先将q1的元素放入新队列中，因此顺序可能会改变，所以不是stable；
快速排序中，由于有了qEquals队列的存在，相等的元素顺序并不会改变，因此是stable的。

先贴作业：

MD先把nth()用到partition里面去了。。。。导致q_sort的时间一直不对。。。

关于stable：
merge sort不stable； 因为merge 2 sorted list的时候一边取一个front；这两个sub list有可能先后错位；
quick sort stable； 因为每次相同的key都按顺序放在中间。

还是quicksort稍微好点啊，尤其是size特别大的时候。

哈哈这个作业我也做过。这两个平均复杂度都是O(nlogn)，不过最坏情况Q-sort是O(n^2)， M-sort慢啊。我记得Q-Sort,M-sort, BST, H-sort平均时间复杂度都一样。

好像比楼主慢了不少...

好像比楼主慢了不少...

wtttt0 发表于 2014-11-14 11:35
好像比楼主慢了不少...

i7-4700MQ

HW8比较简单，完成了，求加学分。

交作业，还有2个作业，坚持住

这次作业比较容易，按照提示说明编写分分钟搞定！
加油！！！！

上次没发到，现在重发