排序算法

czheo
czheo
Nov 20, 2016 · 10 min read

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
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade