排序算法

Posted on | In |

归并排序

如下归并排序的代码里，merge函数里采用了一个辅助数组temp，用来存储排序后的数组，然后再拷贝到原数组。由于排序的复杂度是n，拷贝也是n，因此复杂度是2n。

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
def mergesort(nums, l, r):
    if l == r:
        return
    mid = (l + r)>>1
    mergesort(nums, l, mid)
    mergesort(nums, mid+1, r)
    merge(nums, l, r)
    
def merge(nums, l, r):
    mid = (l + r)>>1
    i, j = l, mid + 1
    temp = []
    while i <= mid and j <= r:
        if nums[i] <= nums[j]:
            temp.append(nums[i])
            i += 1
        else:
            temp.append(nums[j])
            j += 1
    while i <= mid:
        temp.append(nums[i])
        i += 1
    while j <= r:
        temp.append(nums[j])
        j += 1
    for i in range(l, r + 1):
        nums[i] = temp[i-l]