排序算法

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