排序算法总结

╰半橙微兮° 2021-12-13 14:13 302阅读 0赞

# 常见排序算法评估 #

### 时间复杂度 ###

O(n2)：冒泡排序、选择排序、插入排序

O(nlogn)：归并排序、快速排序、堆排序、希尔排序

O(n)：计数排序、基数排序   不是基于比较的排序算法，思想来于桶排序

### 空间复杂度 ###

O(1)：插入排序、选择排序、冒泡排序、堆排序（用递归实现是O(logn)）、希尔排序

O(logn~n)：快速排序

O(n)：归并排序

O(m)：计数排序，基数排序（m是“桶”的个数）

### 稳定性 ###

概念：假定待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，称这种排序算法是稳定的，否则称为不稳定的。

稳定的排序算法：冒泡排序、插入排序、归并排序、计数排序、基数排序、桶排序

不稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

--------------------

# 常见排序算法及python实现 #

### 快速排序 ###

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快排代码实现需要分割（partition）部分与递归实现部分。

# 快排
    def partition(l, left, right):
        k = left
        val = l[right]
        for i in range(left, right):
            if l[i]<val:
                l[i], l[k] = l[k], l[i]
                k += 1
        l[right], l[k] = l[k], l[right]
        return k
    
    def quicksort(l, left, right):
        if left<right:
            k0 = partition(l, left, right)
            quicksort(l, left, k0-1)
            quicksort(l, k0+1, right)
        return l
    
    L = [4,5,6,0,1,7,2,3]
    print(quicksort(L,0,len(L)-1))

### 归并排序 ###

假设序列共有n个元素，将序列每相邻两个数字进行有序合并（merge)，形成(n//2+n%2)个序列，排序后每个序列包含两个元素将上述序列再次归并，形成(n//4)个序列，每个序列包含四个元素。重复归并操作，直到所有元素排序完毕。

归并排序代码实现需要有序合并（merge）部分与递归实现部分。

# 归并排序
    def merge(a,b):
        c = []
        i = j = 0
        while i<len(a) and j<len(b):
            if a[i]<b[j]:
                c.append(a[i])
                i += 1
            else:
                c.append(b[j])
                j += 1
        if i==len(a):
            for h in b[j:]:
                c.append(h)
        else:
            for h in a[i:]:
                c.append(h)
        return c
    
    def mergesort(l):
        if len(l)<=1:
            return l
        middle = len(l)//2
        left = mergesort(l[:middle])
        right = mergesort(l[middle:])
        return merge(left,right)
    
    L = [4,5,6,0,1,7,3,3]
    print(mergesort(L))

### TopK ###

维护大根堆实现，复杂度O(nlogk)

def topk(k):
        return [x for x in reversed([heapq.heappop(data) for x in range(k)])]
    def push(elem,data,k):
        if len(data) < k:
            heapq.heappush(data, elem)
        else:
            topk_small = data[0]
            if elem > topk_small:
                heapq.heapreplace(data,elem)
            
    k = 7
    data = []
    list_rand = random.sample(range(1000000), 100)
    for i in list_rand:
        push(i,data,k)
    print(topk(k))
    print(sorted(list_rand, reverse=True)[0:k])  #对比