排序算法 | 2hip3ng

速记

名称	时间复杂度	稳定性
冒泡排序	$O(n^2)$	稳定
插入排序	$O(n^2)$	稳定
选择排序	$O(n^2)$	不稳定
归并排序	$O(nlogn)$	稳定
快速排序	$O(nlogn)$	不稳定
希尔排序	$O(nlogn)$	不稳定
堆排序	$O(nlogn)$	不稳定
基数排序		稳定
桶排序		稳定
计数排序		稳定

稳定性记忆方法：高复杂度（ $O(n^2)$ ）选择排序是例外，低复杂度（ $O(nlogn)$ ）归并排序是例外。

选择排序不稳定举例：(7) 2 5 9 3 4 [7] 1…当我们利用直接选择排序算法进行排序时候,(7)和1调换,(7)就跑到了[7]的后面了,原来的次序改变了,这样就不稳定了.

快速排序

def quick_sort(array, start, end):
    """快速排序"""
    if start >= end:  
        return
    mid = array[start]  
    low = start  
    high = end 
    while low < high:
        while low < high and array[high] >= mid:
            high -= 1
        array[low] = array[high]
        
        while low < high and array[low] < mid:
            low += 1
        array[high] = array[low]

    array[low] = mid  

    quick_sort(alist, start, low - 1)  
    quick_sort(alist, low + 1, end)  

# Test
array = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(array, 0, len(array) - 1)          # 闭区间 [0, len(array) -1]
print(array)

归并排序

def merge_sort(array):
    if len(array) == 1:
        return array
    mid = len(array) // 2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])
    
    return merge(left_array, right_array)
    

def merge(left_array, right_array):
    array = []
    i = 0
    j = 0
    while i < len(left_array) and j < len(right_array):
        if left_array[i] <= right_array[j]:
            array.append(left_array[i])
            i += 1
        else:
            array.append(right_array[j])
            j += 1
    while i < len(left_array):
        array.append(left_array[i])
        i += 1
    while j < len(right_array):
        array.append(right_array[j])
        j += 1
    
    return array


# Test
array = [54, 26, 93, 17, 77, 31, 44, 55, 20]
array = merge_sort(array)          
print(array)

topK问题

暴力解法

最基本的思路，将N个数进行完全排序，从中选出排在前K的元素即为所求。有了这个思路，我们可以选择相应的排序算法进行处理，目前来看快速排序，堆排序和归并排序都能达到$O(NlogN)$的时间复杂度。

优先队列

可以采用数据池的思想，选择其中前K个数作为数据池，后面的N-K个数与这K个数进行比较，若小于其中的任何一个数，则进行替换。这种思路的算法复杂度是$O(N*K)$

大根堆

大根堆维护一个大小为K的数组，目前该大根堆中的元素是排名前K的数，其中根是最大的数。此后，每次从原数组中取一个元素与根进行比较，如小于根的元素，则将根元素替换并进行堆调整（下沉），即保证大根堆中的元素仍然是排名前K的数，且根元素仍然最大；否则不予处理，取下一个数组元素继续该过程。该算法的时间复杂度是O(N*logK)，一般来说企业中都采用该策略处理topK问题，因为该算法不需要一次将原数组中的内容全部加载到内存中，而这正是海量数据处理必然会面临的一个关卡。

快速排序

利用快速排序的分划函数找到分划位置K，则其前面的内容即为所求。该算法是一种非常有效的处理方式，时间复杂度是O(N)（证明可以参考算法导论书籍）。对于能一次加载到内存中的数组，该策略非常优秀。

def topK(array, K):
    left = 0
    right = len(array) - 1
    index = quick_sort(array, left, right)
    while index+1 != K:
        if index+1 < K:
            index = quick_sort(array, index+1, right)
        elif index+1 > K:
            index = quick_sort(array, left, index-1)
    return array[:K]

def quick_sort(array, left, right):
    # print(left, right)
    mid = array[left]
    while left < right:
        while left < right and array[right] < mid:
            right -= 1
        array[left] = array[right]
        while left < right and array[left] >= mid:
            left += 1
        array[right] = array[left]
    array[left] = mid
    return left


# Test
array = [54, 26, 93, 17, 77, 31, 44, 55, 20]
array = topK(array, K=8)          
print(array)