Java教程

算法导论第八章——线性时间排序

本文主要是介绍算法导论第八章——线性时间排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 8.1排序算法的下界
  • 8.2 计数排序
  • 8.3 基数排序
  • 8.4 桶排序

8.1排序算法的下界

算法最好情况最糟情况平均情况是否原址
插入排序 Θ ( n ) \Theta(n) Θ(n) Θ ( n 2 ) \Theta(n^2) Θ(n2) Θ ( n 2 ) \Theta(n^2) Θ(n2)原址
冒泡排序 Θ ( n ) \Theta(n) Θ(n) Θ ( n 2 ) \Theta(n^2) Θ(n2) Θ ( n 2 ) \Theta(n^2) Θ(n2)原址
选择排序 Θ ( n 2 ) \Theta(n^2) Θ(n2) Θ ( n 2 ) \Theta(n^2) Θ(n2) Θ ( n 2 ) \Theta(n^2) Θ(n2)原址
归并排序 Θ ( n l g n ) \Theta(nlgn) Θ(nlgn) Θ ( n l g n ) \Theta(nlgn) Θ(nlgn) Θ ( n l g n ) \Theta(nlgn) Θ(nlgn)非原址
堆排序 O ( n l g n ) ) O(nlgn)) O(nlgn)) O ( n l g n ) ) O(nlgn)) O(nlgn)) − − − − ---- −−−−原址
快速排序 Θ ( n l g n ) \Theta(nlgn) Θ(nlgn) Θ ( n 2 ) \Theta(n^2) Θ(n2) O ( n l g n ) O(nlgn) O(nlgn)原址

1、在最坏情况下,任何比较排序算法都需要 Ω ( n l g n ) \Omega(nlgn) Ω(nlgn)次比较
2、堆排和归并排序是渐进最优的比较排序算法
决策树模型: 比较排序可以被抽象为一颗决策树。决策树是一棵完全二叉树,它可以表示在给定输入规模情况下,某一特定排序算法对所有元素的比较操作。

8.2 计数排序

1、时间复杂度: Θ ( n + k ) \Theta(n+k) Θ(n+k)
2、计数排序具有稳定性:具有相同值的元素在输出数组中的相对次序与他们在输入数据中的相对次序相同。
3、非原址排序

"""计数排序"""
import numpy as np


def Counting_sort(A):
    if len(A) < 2:
        return A
    MAX = max(A)
    MIN = min(A)
    C = [0] * (MAX - MIN + 1)
    B=[0]*(len(A))
    for i in range(0, len(A)):
        C[A[i]] = C[A[i]] + 1
    C = np.cumsum(C)
    for i in range((len(A)-1),-1,-1):
        """此处不可以改为有 0->len(A)-1  因为C是一个累加的值,
        即在往B中安放出现了3次的元素的A[i],假设A[i]排列后分别位于索引(2,3,4)位置,
        是先将A[i]放在第4的位置的,然后第3,第2的"""
        B[C[A[i]]-1]=A[i]
        C[A[i]]=C[A[i]]-1
    return B


A = [2, 5, 3, 0, 2, 3, 0, 3]
print(Counting_sort(A))

8.3 基数排序

1、时间复杂度: Θ ( d ( n + k ) ) \Theta(d(n+k)) Θ(d(n+k)) n个k进制的d位数
2、具有稳定性但不是原址排序
在这里插入图片描述

"""基数排序"""

def Radix_SORT(A):
    n = len(str(max(A)))
    for k in range(n):#从低位到高位轮排序
        bucket_list = [[] for i in range(10)]
        for i in A:
            bucket_list[i // (10 ** k) % 10].append(i)#基于计数排序
        #A = [j for i in bucket_list for j in i]
        A=[]
        for i in bucket_list:
            for j in i:
                A.append(j)
    return A


A = [329,457,657,839,436,720,355]
print(Radix_SORT(A))
#输出[329, 355, 436, 457, 657, 720, 839]

8.4 桶排序

1、时间复杂度: T ( n ) = Θ ( n ) + ∑ i = 0 b u c k e t − 1 ( n i 2 ) T(n)=\Theta(n)+\sum_{i=0}^{bucket-1}(n_i^2) T(n)=Θ(n)+∑i=0bucket−1​(ni2​)( n i n_i ni​表示桶B[i]中的元素个数,求和符号中的 ( b u c k e t − 1 ) (bucket-1) (bucket−1)表示桶的个数)
当达到极限情况即每个桶只有一个数据时,桶排序的最好效率能够达到 O ( n ) O(n) O(n)
2、具有稳定性
在这里插入图片描述

"""桶排序"""


# 插入排序
def INSERTION_SORT(A):
    if len(A) < 2:
        return A
    for i in range(1, len(A)):
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = key
    return A


def BUCKET_SORT(A):
    n = len(A)
    BUCKET = [[] for i in range(n)]
    for i in range(n):
        BUCKET[int(n * A[i])].append(A[i])
    RES = []
    for j in BUCKET:
        if j:
            j = INSERTION_SORT(j)
            for num in range(len(j)):
                RES.append(j[num])
    return RES


A = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
print(BUCKET_SORT(A))
这篇关于算法导论第八章——线性时间排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!