由于链表(LinkedList)不支持随机访问(Random Access),只允许顺序访问,因此对于链表的O(logn)时间复杂度的排序算法不可以采用诸如快速排序等基于随机访问的排序算法,而归并排序可以满足这一需求。
归并排序是分治法(Divide and Conquer)的典型应用,其伪代码如下:
merge_sort(list) {
split list into two halfs, say first and second ;
merge_sort(firstHalf);
merge_sort(secondHalf);
merge(firstHalf,secondHalf);
}
下面的Java代码实现了对单链表(singly linked list)的归并排序,代码实现优美 ...