算法

排序算法

 

快排

递归

算法思想

在待排序数组中找到一个元素作为标准元素t，在数组中将所有小于t的元素放在t左侧，所有大于t的元素放在t的右侧（从小到大排序，否则反过来）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def qs(l,r,nums):
    if l<r:
        i = l
        j = r
        key = nums[l]
        while i<j:
            while i<j and nums[j]>=key:
                j-=1
            nums[i]=nums[j]
            while i<j and nums[i]<=key:
                i+=1
            nums[j]= nums[i]
        nums[i] = key
        qs(l,i-1,nums)
        qs(i+1,r,nums)

归并排序

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(arr):
    """
    归并排序
    原理：
    1. 将数组分为两部分，分别对两部分进行排序
    2. 将两个有序数组合并
    3. 递归
    时间复杂度：O(nlogn)
    """
    if len(arr)<=1:
        return arr
    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left,right)

def merge(left,right):
    # 合并两个有序数组
    res = []
    i = 0
    j = 0
    while i<len(left) and j<len(right):
        if left[i]<right[j]:
            res.append(left[i])
            i+=1
        else:
            res.append(right[j])
            j+=1
    res+=left[i:]
    res+=right[j:]
    return res

arr=[3,5,6,7,1,4,2]
print(merge_sort(arr))