排序算法总结

排序算法	时间复杂度(最差)	时间复杂度(最好)	时间复杂度(平均)	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(n^2)$	$O(n)$	$O(n^{1.3})$	$O(1)$	不稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(1)$	不稳定
快速排序	$O(n^2)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	不稳定
归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(n)$	稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定
桶排序	$O(n^2)$	$O(n)$	$O(n+k)$	$O(n+k)$	稳定
基数排序	$O(n*k)$	$O(n*k)$	$O(n*k)$	$O(n+k)$	稳定

堆排序算法

堆的上浮操作：当在堆尾添加了新元素后，需要对堆尾元素进行上浮操作来维护堆
堆的下沉操作：当更新堆首元素后，需要对堆首元素进行下沉操作来维护堆

python

class Solution:
    def heap_sort(self, heap):
        if(len(heap) <= 1):
            return heap
        # 建堆：从最后一个非叶子节点依次向前进行下沉操作
        for i in range(len(heap) // 2 - 1, -1, -1):
            self.sift_down(heap, i, len(heap) - 1)
        # 此时，最大(小)值已处于大(小)项堆的堆顶，将其余最后一个元素交换，即完成一次排序
        # 以此类推，不断交换并对堆顶元素进行下沉操作，直到堆排序完成
        for i in range(len(heap) - 1, 0, -1):
            heap[0], heap[i] = heap[i], heap[0]
            self.sift_down(heap, 0, i - 1)
        return heap

    def sift_down(self, heap, start, end): 
        # 堆顶元素下沉操作调整堆：将start到end中从第一个结点开始依次与其子结点进行比较，将符合条件的结点下沉，一直到堆底
        tmp = heap[start]
        i = start # 当前结点索引
        j = 2 * i + 1 # 左子结点索引
        while(j <= end):
            if(j + 1 <= end and heap[j] < heap[j + 1]): # 判断是否取到右子结点，此为大项堆，若为小项堆则 heap[j] > heap[j + 1]
                j += 1
            if(tmp < heap[j]): # 此为大项堆，若为小项堆则 tmp > heap[j]
                heap[i] = heap[j]
            else:
                break
            # 令i = j，继续对结点i递归进行下沉操作
            i = j
            j = 2 * i + 1
        heap[i] = tmp

运行结果

python

solu = Solution()
print(solu.heap_sort([2, 5, 9, 8, 3, 1, 6, 4]))

>>> [1, 2, 3, 4, 5, 6, 8, 9]

注：
① 大项堆对应的是升序排列，小项堆对应的是降序排列，当然，将结果逆序输出就能反过来。
② 新元素只能添加在末尾，若添加在堆首，则会将堆中元素打乱，从而需要重新构建堆。

复杂度分析

建堆：O(n)
调整堆：O(nlogn)

总体时间复杂度：O(nlogn)

注：构造堆有两种方法。
① 对原始list进行操作，如 基础算法 所示
② 新建一个list，依次插入元素并进行上浮操作，如 算法题案例 所示

算法题案例

最小的K个数

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

解题思路

取前K个数，构造一个大小为K的大项堆，用来记录最小的K个数
依次将剩余数与堆顶元素进行比较
- 若小于堆顶元素，则用其替换堆顶元素，并进行上浮操作调整堆
- 若大于等于堆顶元素，则将其抛弃，继续读入下一个数

python

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        if(k == 0 or k > len(tinput) or len(tinput) == 0):
            return []
        heap = []

        # 建堆：构造并维护一个大小为k的大项堆
        for n in tinput:
            # 若堆中还不足k个元素，则插入堆，并上浮
            if(len(heap) < k):
                heap.append(n)
                self.sift_up(heap, 0, len(heap) - 1)
            # 若堆中已有k个元素，则更新堆，即当新元素小于堆顶时，用其替换堆顶元素，并进行下沉操作
            elif(n < heap[0]):
                heap[0] = n
                self.sift_down(heap, 0, len(heap) - 1)
            print(heap, n)
        return sorted(heap)

    def sift_down(self, heap, start, end): 
        # 堆顶元素下沉操作调整堆：将start到end中从第一个结点开始依次与其子结点进行比较，将符合条件的结点下沉，一直到堆底
        tmp = heap[start]
        i = start # 当前结点索引
        j = 2 * i + 1 # 左子结点索引
        while(j <= end):
            if(j + 1 <= end and heap[j] < heap[j + 1]): # 判断是否取到右子结点，此为大项堆，若为小项堆则 heap[j] > heap[j + 1]
                j += 1
            if(tmp < heap[j]): # 此为大项堆，若为小项堆则 tmp > heap[j]
                heap[i] = heap[j]
            else:
                break
            # 令i = j，继续对结点i递归进行下沉操作
            i = j
            j = 2 * i + 1
        heap[i] = tmp

    def sift_up(self, heap, start, end):
        # 堆底元素上浮操作调整堆：将start到end中从最后一个结点开始依次与其父结点进行比较，将符合条件的结点上浮，一直到堆顶
        tmp = heap[end]
        i = end # 当前结点索引
        j = (i - 1) >> 1 # 父结点索引
        while(j >= start):
            if(tmp > heap[j]): # 此为大项堆，若为小项堆则 tmp < heap[j]
                heap[i] = heap[j]
            else:
                break
            # 令i = j，继续对结点i递归进行上浮操作
            i = j
            j = (i - 1) >> 1
        heap[i] = tmp

运行结果

python

solu = Solution()
print(solu.GetLeastNumbers_Solution([4,5,1,6,2,7,3,8], 4))

>>> [1, 2, 3, 4]

复杂度分析

维护一个大小为k的堆：O(logk)
一共有n个数：O(nlogk)

总体时间复杂度：O(nlogk)

数组中的第K个最大元素

题目来源：Leetcode
题目链接：Leetcode-215
题目描述：

在未排序的数组中找到第 K个最大的元素。请注意，你需要找的是数组排序后的第 K 个最大的元素，而不是第 K 个不同的元素。

解题思路

取前K个数，构造一个大小为K的小项堆，用来记录最大的K个数
依次将剩余数与堆顶元素进行比较
- 若大于堆顶元素，则用其替换堆顶元素，并进行上浮操作调整堆
- 若小于等于堆顶元素，则将其抛弃，继续读入下一个数

python

class Solution:
    def findKthLargest(self, tinput, k):
        if(k == 0 or k > len(tinput) or len(tinput) == 0):
            return []
        heap = []

        for n in tinput:
            # 若堆中还不足k个元素，则插入堆，并上浮
            if(len(heap) < k):
                heap.append(n)
                self.sift_up(heap, 0, len(heap) - 1)
            # 若堆中已有k个元素，则更新堆，即当新元素大于堆顶时，用其替换堆顶元素，并进行下沉操作
            elif(n > heap[0]):
                heap[0] = n
                self.sift_down(heap, 0, len(heap) - 1)
        return heap[0]
    
    def sift_down(self, heap, start, end): 
        # 堆顶元素下沉操作调整堆：将start到end中从第一个结点开始依次与其子结点进行比较，将符合条件的结点下沉，一直到堆底
        tmp = heap[start]
        i = start # 当前结点索引
        j = 2 * i + 1 # 左子结点索引
        while(j <= end):
            if(j + 1 <= end and heap[j] > heap[j + 1]): # 判断是否取到右子结点，此为小项堆，若为大项堆则 heap[j] < heap[j + 1]
                j += 1
            if(tmp > heap[j]): # 此为小项堆，若为大项堆则 tmp < heap[j]
                heap[i] = heap[j]
            else:
                break
            # 令i = j，继续对结点i递归进行下沉操作
            i = j
            j = 2 * i + 1
        heap[i] = tmp

    def sift_up(self, heap, start, end):
        # 堆底元素上浮操作调整堆：将start到end中从最后一个结点开始依次与其父结点进行比较，将符合条件的结点上浮，一直到堆顶
        tmp = heap[end]
        i = end # 当前结点索引
        j = (i - 1) >> 1 # 父结点索引
        while(j >= start):
            if(tmp < heap[j]): # 此为小项堆，若为大项堆则 tmp > heap[j]
                heap[i] = heap[j]
            else:
                break
            # 令i = j，继续对结点i递归进行上浮操作
            i = j
            j = (i - 1) >> 1
        heap[i] = tmp

运行结果

python

solu = Solution()
print(solu.findKthLargest([3,2,1,5,6,4], 2))

>>> 5

print(solu.findKthLargest([3,2,3,1,2,4,5,5,6], 4))

>>> 4

复杂度分析

维护一个大小为k的堆：O(logk)
一共有n个数：O(nlogk)

总体时间复杂度：O(nlogk)

数据流中的第K大元素

题目来源：Leetcode
题目链接：Leetcode-703
题目描述：

设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

解题思路

初始化一个大小至多为K的堆(可能小于K)
依次读入数据流的新元素
- 若堆还没到K，则在堆底插入新元素，并进行上浮操作
- 若堆已到达K，且新元素大于堆顶元素，则用其替换堆顶元素，并进行下沉操作调整堆
- 否则将其抛弃，继续读入下一个数

python

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = []
        # 初始化：将原先nums中的元素构造一个最大为k个元素的小项堆
        for n in nums:
            # 若堆中还不足k个元素，则插入堆
            if(len(self.heap) < self.k):
                self.heap_push(self.heap, n)
            # 若堆中已有k个元素，则更新堆
            else:
                self.heap_update(self.heap, n)

    def add(self, val): # 数据流中的新元素
        # 若堆中还不足k个元素，则插入堆
        if(len(self.heap) < self.k):
            self.heap_push(self.heap, val)
        # 若堆中已有k个元素，则更新堆
        else:
            self.heap_update(self.heap, val)
        return self.heap[0]
    
    def sift_down(self, heap, start, end): 
        # 堆顶元素下沉操作调整堆：将start到end中从第一个结点开始依次与其子结点进行比较，将符合条件的结点下沉，一直到堆底
        tmp = heap[start]
        i = start # 当前结点索引
        j = 2 * i + 1 # 左子结点索引
        while(j <= end):
            if(j + 1 <= end and heap[j] > heap[j + 1]): # 判断是否取到右子结点，此为小项堆，若为大项堆则 heap[j] < heap[j + 1]
                j += 1
            if(tmp > heap[j]): # 此为小项堆，若为大项堆则 tmp < heap[j]
                heap[i] = heap[j]
            else:
                break
            # 令i = j，继续对结点i递归进行下沉操作
            i = j
            j = 2 * i + 1
        heap[i] = tmp

    def sift_up(self, heap, start, end):
        # 堆底元素上浮操作调整堆：将start到end中从最后一个结点开始依次与其父结点进行比较，将符合条件的结点上浮，一直到堆顶
        tmp = heap[end]
        i = end # 当前结点索引
        j = (i - 1) >> 1 # 父结点索引
        while(j >= start):
            if(tmp < heap[j]): # 此为小项堆，若为大项堆则 tmp > heap[j]
                heap[i] = heap[j]
            else:
                break
            # 令i = j，继续对结点i递归进行上浮操作
            i = j
            j = (i - 1) >> 1
        heap[i] = tmp

    def heap_push(self, heap, val):
        # 插入堆：在堆的最后插入元素，将其与父结点比较，递归地进行上浮操作
        # 因为只在堆底加了新元素，其他元素相对大小关系未变，只需将当前堆底元素上浮到合适位置即可
        heap.append(val)
        self.sift_up(heap, 0, len(heap) - 1)

    def heap_update(self, heap, val):
        # 更新堆：若堆顶元素小于新元素，则替换，并对其进行下沉操作
        # 因为只替换了堆顶元素，其他元素相对大小关系未变，只需将当前堆顶元素下沉到合适位置即可
        if(val > heap[0]):
            heap[0] = val
            self.sift_down(heap, 0, len(heap) - 1)

运行结果

python

solu = KthLargest(3, [4,5,8,2])
solu.add(3)
solu.add(5)
solu.add(10)
solu.add(9)
solu.add(4)

>>> 4
>>> 5
>>> 5
>>> 8
>>> 8

复杂度分析

维护一个大小为k的堆：O(logk)
一共有n个数：O(nlogk)

总体时间复杂度：O(nlogk)