排序算法

Merge Sort

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

排序算法

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)就够了。先按个位数排序,然后按十位数排序,然后按百位数排序……。

实际工程中的排序

  • 由于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),对几乎已经排好序的数组有较好的性能。
  • 当需要稳定的时候。
  • 当数组里面存的是指针,而指针指向的对象远比指针本身大的时候。因为对象越大,拷贝指针数组的overhead相对就越小。我们可以用一点点的overhead换取稳定的性质。
  • Java基础类型的排序用的是Quick Sort,因为拷贝基础类型的数组是需要copy by value的。但Collections的排序用的是Merge Sort,因为Collections存的是reference。
  • Python的自带的排序算法叫做Tim Sort就是一种Insertion Sort和Merge Sort结合的变种。因为Python的list也是存reference的。

一道排序题

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
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

--

--

--

wannabe programmer

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
czheo

czheo

wannabe programmer

More from Medium

GOVERNMENT MUST ACT IMMEDIATELY TO AVOID AN IMPENDING SOCIO-ECONOMIC TURMOIL!

MY Star Poem…

Eldorado

Service to Love Day 1