排序算法

V站上一篇题为“谷歌电面，什么是 Merge Sort ?”的文章引起了热议。于是我就复习了一下排序的知识。

5/10/2018 Update：最近V站上又有人吐槽阮老师的quick sort，于是更新了下quick sort的代码。具体见O(n logn)排序部分。

Merge Sort

Merge Sort的基本想法就是，把一个数组从中点分成两半，先把左一半(left)和右一半(right)分别排序好（递归），然后再把它们按顺序合并（Merge）在一起。

这里的关键步骤是Merge，基本想法就是，分别选取left、right里面最小的两个数，比较它们哪个比较小，把比较小的那个数放到结果里。然后从剩下的left、right里面分别选取最小的两个数，重复以上的过程，直到left、right里面所有的数都已经放到结果里了。

假设我们有两个数组left=[1,3,5], right=[2,4,6]。初始化结果=[]。先看，left里1最小，right里2最小，1<2，所以把1放入结果=[1]。然后剩下的left里3最小，right里2最小，3>2，所以把2放入结果=[1,2]。……

下面是Merge Sort的Python代码。

merge_sort的python代码

• 输入a是一个list。
• a长度<=1的时候，我们什么都不用做。
• 把a对半分成left、right两个list，分别把left、right排序好。（递归）
• 最后，把排序好的left、right合并，按顺序放回a里。

merge的python代码

merge函数值得注意的是，最后两个while的代码。如果left、right里有一方的数已经全部放回a，而另一方还剩几个没有放回去，需要最后把剩余的数放回a。

举个极端的例子，left=[1,2,3]，right=[4,5,6]，因为left的数总是小于right的数，最后left里的数全被先放回了a，而right里的数却一个也没有放。

排序算法

下面是面试常见的排序算法，根据average case的时间复杂度罗列一下。

O(n²)的排序

• Bubble Sort: 冒泡，通过相邻两数两两交换，把最大的数放到数列的最后。【best case: 顺序时，O(n)。worst case: 逆序时，O(n²)。】
• Selection Sort：选择，遍历选出最小的数放到数列的开头。和Bubble Sort除了找最大／最小的相反外，Selection Sort不通过两两交换，而是记下最小数，把它前面的数全部向后偏移一个位置之后，把最小的数放回开头。由于两两交换的成本(tmp=a[i]; a[i]=a[i+1]; a[i+1]=tmp)比偏移(a[i+1]=a[i])高，所以一般来说，Selection Sort比Bubble Sort好，尽管Bubble的best case比较快。【best case: O(n²)。worst case: O(n²)。】
• Insertion Sort：插入，选取一个数，保证这个数之前的数组已经排序好，把这个数插入到之前的数组中合适的位置。和Selection Sort相比，都是保证左半边的数组已经排序好，也都要进行数组偏移。不同点有两个：1. Insertion对左半边(sorted)偏移，Selection对右半边(unsorted)偏移。2. Selection必须遍历右半边的所有数才能找到最小，Insertion只要找到左半边里合适的插入位置就能停下来，所以一般来说，Insertion Sort比Selection Sort好。【best case: 顺序时，O(n)。worst case: 逆序时，O(n²)。】
• 总结：Insertion > Selection > Bubble。

O(n logn)的排序

• Merge Sort：如上所述，left, right两个数组占用额外空间。虽然可以通过记录索引的方式优化，但至少还是需要O(2n)的空间。【best case: O(n logn)。worst case: O(n logn)。】
• Quick Sort：快排，代码如下。通过partition操作，找到一个pivot点a[pivot]，把比它小的都移到它左边，大的都移到它右边。也就是说，保证a[start … pivot-1] <= a[pivot] <= a[pivot+1 … end]。然后对左右两边的数组分别递归排序。如果每次partition选择的pivot都是最大或最小点，快排就会沦为O(n²)的worst case（也就是说，partition不能平衡安排左右两边的工作量）。Quick Sort是O(n)的空间复杂度。【best case: O(n logn)。worst case: O(n²)。】

quick sort

• 即使worst case比较慢，Quick Sort大部分时候还是比Merge Sort快。而且Quick Sort比Merge Sort节约空间，所以Quick Sort > Merge Sort。
• 排序的稳定（stable），指的是相同的两个数，排序后的相对位置和原来一样。Merge Sort是稳定的。Quick Sort是不稳定的。

O(n)的排序

• 通过两数字比较的排序最快也需要O(n logn)，O(n)的排序都不通过两数比较来排序。
• Bucket Sort: 放k个bucket，比如1–10的数放第一个bucket, 11–20放第二个，21–30放第三个……。对每个bucket内的数排序后，按顺序取出。
• Counting Sort: Bucket Sort的特殊情况。比如对范围在1到10的数排序，放10个计数器，遍历一遍把每个数的出现次数记录在对应的计数器上。然后把1到10依次放入结果，每次放一个数对应的计数器减1，直到对应的计数器为0，放下一个数。
• Radix Sort：基本想法是，如果比较两个数，比如6731和1212，我们只要比较最高位（千位6>1）就够了。先按个位数排序，然后按十位数排序，然后按百位数排序……。

实际工程中的排序

有个问题，Quick Sort这么快而且节约空间，为什么不统一天下？

什么时候用Insertion Sort？

• 由于O(n logn)的排序需要对数组分成左右两半，无论是partition还是merge操作，对每一次递归都有一定的overhead。
• 对比较小的数组排序，Insertion Sort虽然时间复杂度较高，但每次循环overhead很小。所以往往比O(n logn)的排序快。所以对较小的数组，常使用Insertion Sort，或则，把它当作O(n logn)排序算法的递归的base case。
• 而且Insertion Sort的best case可以达到O(n)，对几乎已经排好序的数组有较好的性能。

什么时候用Merge Sort？

• 当需要稳定的时候。
• 当数组里面存的是指针，而指针指向的对象远比指针本身大的时候。因为对象越大，拷贝指针数组的overhead相对就越小。我们可以用一点点的overhead换取稳定的性质。
• Java基础类型的排序用的是Quick Sort，因为拷贝基础类型的数组是需要copy by value的。但Collections的排序用的是Merge Sort，因为Collections存的是reference。
• Python的自带的排序算法叫做Tim Sort就是一种Insertion Sort和Merge Sort结合的变种。因为Python的list也是存reference的。

一道排序题

Leetcode上有一道对Linked List排序的题。要求O(n logn)的时间复杂度，和O(1)的空间复杂的。因为Linked List只能顺序读写，不能随机读写，所以不能用索引方便地写排序。

总的来说，这题比较有欺骗性，而且边界条件比较复杂，要完全写对比较不容易。

乍一看，根据空间复杂度，初步判断是Quick Sort的变种。但是，如果用Quick Sort写，你会发现有些测试timeout无法通过，因为Quick Sort的worst case是O(n²)，不满足题目的条件。

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        return quick_sort(head, None, None)
        
def quick_sort(head, pre, post):
    if head is not post and head.next is not post:
        pivot, head = partition(head, pre, post)
        head = quick_sort(head, pre, pivot)
        quick_sort(pivot.next, pivot, post)
    return head
    
        
def partition(head, pre, post):
    pivot = head
    # nodes before "done" are already partitioned
    done = head
    cur = head.next
    while cur is not post:
        next = cur.next
        if cur.val < pivot.val:
            # skip cur node
            done.next = cur.next
            # put cur at head
            cur.next = head
            head = cur
        else:
            done = cur
        cur = next
    if pre:
        pre.next = head
    return pivot, head

而如果用Merge Sort，由于Linked List和数组不同，拷贝Linked List只需要记录第一个元素的reference即可，可以大幅降低空间复杂度，所以满足空间复杂度的同时，在worst case下也能满足O(n logn)的时间复杂度。

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        return merge_sort(head)
def merge_sort(head):
    if not head or not head.next:
        return head
    prev, right = middle(head)
    prev.next = None
    left = merge_sort(head)
    right = merge_sort(right)
    return merge(left, right)
        
def merge(left, right):
    dummy_head = ListNode(0)
    cur = dummy_head
    while left and right:
        if left.val < right.val:
            cur.next = left
            left = left.next
        else:
            cur.next = right
            right = right.next
        cur = cur.next
    if left:
        cur.next = left
    if right:
        cur.next = right
    return dummy_head.next
def middle(head):
    slow = head
    fast = head
    prev = None
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
return prev, slow