Sort List， 链表排序，一看到O(nlogn)就想到使用merge sort。 对于merge sort，还要研究一下bottom-up和top-down的区别，优劣点，如何继续优化等等，比如n较小时使用insertion sort， 了解Python的Tim-sort之类。也要研究一下链表的Quicksort，以及3-way Quicksort。 当时电面Amazon的时候写排序作死选择Quicksort，还尝试写了一个3-way Quicksort，由于理解不深同时当天也头昏脑胀没解释清楚，被面试官白大姐秒拒，如此浪费一年机会，甚是可惜。对于各种排序的stalability也要好好复习。熟能生巧，多练吧。另外，external sorting，B tree，A* tree，indexing，paging之类的也要复习。聊远了...
这题使用Merge Sort的话，还是按照Divide-and-Conquer分治。 两个辅助方法是findMid找中点，以及merge合并。 merge的话完全可以使用"Merge Sorted List"的代码，找中点我们也使用过，所以可以直接写。
Read full article from 148. Sort List - YRB - 博客园
No comments:
Post a Comment