HelloBear

Less is More

0%

排序算法

Posted on Edited on

本文介绍常见的排序算法以及简单的应用。

冒泡排序

基本思想是，每次比较相邻的元素，将最大的元素放到后面

1
2
3
4
5
6
7
8
9
def bubble_sort(nums):
    for i in range(len(nums)):
        exchange = False
        for j in range(1,len(nums)-i):
            if nums[j] < nums[j-1]:
                nums[j],nums[j-1] = nums[j-1],nums[j]
                exchange = True
        if not exchange:
            return

选择排序

每次选择数组中的最小元素插入到队首

1
2
3
4
5
6
7
def select_sort(nums):
    for i in range(len(nums)):
        min_loc = i
        for j in range(i+1,len(nums)):
            if nums[min_loc] >= nums[j]:
                min_loc = j
        nums[i],nums[min_loc] = nums[min_loc],nums[i]

插入排序

假设前面的数组已经是排序好的，每个选择一个元素插入到这个已经排序的数组中，保持原数组有序

1
2
3
4
5
6
7
8
def insert_sort(nums):
    for i in range(1,len(nums)):
        j = i - 1
        tmp = nums[i]
        while j >= 0 and nums[j] > tmp:
            nums[j+1] = nums[j]
            j -= 1
        nums[j+1] = tmp

快速排序

每次让一个元素到它应该有的位置（即左边一半数字小于该数，右边一半大于该数）,切分数组为两半。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def partition(nums,left,right):
    tmp = nums[left]
    while left < right:
        #1：注意这里比较的对象是tmp，且必须是大于等于，否则会出现循环无法终止
        while left < right and nums[right] >= tmp: 
            right -= 1
        nums[left] = nums[right]
        while left < right and nums[left] <= tmp:
            left += 1
        nums[right] = nums[left]
    nums[left] = tmp     
    return left
def quick_sort(nums,left,right):
    #2： 注意这里是递归调用，if用于判断递归终止
    if left < right: 
        patition = partition(nums,left,right)
        # 3：注意这里的区间必须要排除分割点
        quick_sort(nums,left,patition-1)
        quick_sort(nums,patition+1,right)

堆排序

维护一个大根堆，每次将堆顶不符合要求的元素放在合适的位置即可

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
def sift(nums,low,high):
    tmp = nums[low]
    i = low
    j = 2 * i + 1
    while j <= high:
        #1： 注意这里的边界判断
        if j + 1 <= high and nums[j+1] > nums[j]:
            j += 1
        #2：注意这里判断的依据依旧是tmp而是不是nums[i]
        if nums[j] > tmp:
            nums[i] = nums[j]
            i = j
            j = 2 * i + 1
        else:
            nums[i] = tmp
            #3：注意这里要终止循环
            break
    #4：如果是由于j>high导致退出，这里需要把tmp放回去
    else:
        nums[i] = tmp
def heap_sort(nums):
    n = len(nums)
    #5：注意这里必须是从后向前挑战，而不能挨个将数字加入到数组的开头
    for i in range((n-2)//2,-1,-1):
        sift(nums,i,n-1)
    for j in range(n-1,-1,-1):
        nums[0],nums[j] = nums[j],nums[0]
        sift(nums,0,j-1)

其实在python语言中，提供了小根堆的类，它的用法如下：

1
2
3
4
5
6
7
8
import heapq
prique = []
for i in nums:
    #1：这里会让prique的队首为最小值，注意在上面的代码中，是不能依次加入的，会破坏树的结构，导致错误
    heapq.heappush(prique,i)
heapq.heapppop(prique)
# 除了对单个数排序外，也可以对元组进行排序，其中排序的标准是元组的第一个元素,例如：
heap.heappush(prique,(i,i**2))

如何实际中需要大根堆，那么就需要把原数组取反，用小根堆解决大根堆的问题。

归并排序

将两个有序的列表合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def merge(nums,left,mid,right):
    i,j = left,mid+1
    tmp = []
    while i <= mid and j <= right:
        if nums[i] < nums[j]:
            tmp.append(nums[i])
            i += 1
        else:
            tmp.append(nums[j])
            j += 1
    while i <= mid:
        tmp.append(nums[i])
        i += 1
    while j <= right:
        tmp.append(nums[j])
        j += 1
    nums[left:right+1] = tmp
def merge_sort(nums,left,right):
    if left < right:
        mid = (left+right) // 2
        merge_sort(nums,left,mid)
        merge_sort(nums,mid+1,right)
        merge(nums,left,mid,right)

TopK问题

TopK问题是指，已知一个数组，返回其大（小）的K个数，不要求返回的数组有序。我们这里以最小的K个数为例。

它的解法有多种，最容易想到的是先排序，再返回前k个。但是由于不要求返回的数组有序，我们可以在排序的时候做一些改进。

基于快排

我们知道，快排每趟都可以把一个元素放到它合适的位置上，即左边的数组都小于该值，右边的数组都大于该值。那么为了返回最小的K个元素，我们就可以对快排做剪枝：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def patition(arr,left,right):
    tmp = arr[left]
    while left < right:
        while left < right and arr[right] >= tmp:
            right -= 1
        arr[left] = arr[right]
        while left < right and arr[left] <= tmp:
            left += 1
        arr[right] = arr[left]
    arr[left] = tmp
    return left

def quicksort(arr,left,right,k):
    if left <= right:
        cut = patition(arr,left,right)
        # 唯一不同之处
        if cut > k:
            quicksort(arr,left,cut-1,k)
        elif cut < k:
            quicksort(arr,cut+1,right,k)
        else:
            return
quicksort(arr,0,len(arr)-1,k)
print(arr[:k])

基于堆排序

由于这里是要返回最小的K个数，我们只需要维护一个大小为K的大根堆，就可以了。

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
def sift(arr,low,high):
    tmp = arr[low]
    i = low
    j = 2 * low + 1
    while j <= high:
        if j+1<=high and arr[j+1] > arr[j]:
            j += 1
        if arr[j] > tmp:
            arr[i] = arr[j]
            i = j 
            j = 2 * j + 1
        else:
            arr[i] = tmp
            break
    else:
       arr[i] = tmp

def heap_sort(arr,k):
    if not k:
        return []
    heap = arr[:k]
    for i in range((len(heap)-2)//2,-1,-1):
        sift(heap,i,len(heap)-1)
    for i in range(k,len(arr)): 
        # 注意这里不能先将arr[i]加到头部，再sift，会导致错误
        if arr[i] < heap[0]:
            heap[0] = arr[i]
            sift(heap,0,k-1)
    return heap
return heap_sort(arr,k)

总结

以上就是常见的排序算法，最后对它们的性能做一个总结

常见算法的时间复杂度和空间复杂度对比表