Go Snail

排序算法

Posted on | In

Merge Sort

Merge sort是典型的分治算法, 直接将原问题分为前一半和后一半。要使用分治算法，原问题必须能够分解为规模相当，且能够独立求解的两个子问题。Merge sort的算法框架可以套用在其它的分治算法上，只要把merge函数重写即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def merge_sort(nums):
    return merge_sort_helper(nums, 0, len(nums)-1)


def merge_sort_helper(nums, start, end):
    if start == end:
        return [nums[start]]
        
    mid = start + (end-start)/2
    res1 = merge_sort_helper(nums, start, mid)
    res2 = merge_sort_helper(nums, mid+1, end)
    
    return merge(res1, res2)
        

def merge(nums1, nums2):
    i = 0
    j = 0
    res = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            res.append(nums1[i])
            i += 1
        else:
            res.append(nums2[j])
            j += 1
    while i < len(nums1):
        res.append(nums1[i])
        i += 1

    while j < len(nums2):
        res.append(nums2[j])
        j += 1

    return res

Merge sort中的merge的办法可以应用到很多问题中。如

也是就是说，合并两个有序的线性结构，可以使用该merge算法。那如果是两个有序的二叉树呢(如 二分查找树)？可以这么来做。先通过该merge算法得到一个排好序的数组(时间复杂度为O(m+n))，然后再由该有序数组生成二分查找树(时间复杂度为O(m+n))。其中，m和n分别为两棵树的节点数。当然了，如果该二分查找树的表示方式为数组的话，那直接merge就完成了。

Quick Sort

Quick Sort也是分治算法。只是它分割子问题的方式相对巧妙一些。相比于merge sort,它不是直接将原数组分为前一半和后一半，而是随机选取一个元素，将原数组分为比这个元素大的一半和不比这个元素大的一半。它的好处是，把两个子问题的结果直接合并就是原问题的解。

我们还可以换一个角度来看这个排序的过程。当你把原数组分割好的时候，其实你也找到了那个分割元素在数组中的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def quick_sort(nums):
    quick_sort_helper(nums, 0, len(nums)-1)

def quick_sort_helper(nums, start, end):
    if start < end:
        r = partition(nums, start, end)
        quick_sort_helper(nums, start, r-1)
        quick_sort_helper(nums, r+1, end)


def partition(nums, start, end):
    pivot = nums[end]
    i = start
    j = end
    while i < j:
        while  i<j and nums[i] <= pivot:
            i += 1
        while i<j and nums[j] >= pivot:
            j -= 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    tmp = nums[i]
    nums[i] = nums[end]
    nums[end] = tmp

    return i