欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

常见的排序算法和查找算法——python实现

程序员文章站 2024-03-20 18:19:58
...

文章目录

时间复杂度

  • O© 常量时间复杂度 - 布隆过滤器 / 哈希存储
  • O(log2n) 对数时间复杂度 - 折半查找（二分查找）
  • O(n) 线性时间复杂度 - 顺序查找 / 计数排序
  • O(n*log2n) 对数线性时间复杂度 - 高级排序算法（归并排序、快速排序）
  • O(n2) 平方时间复杂度 - 简单排序算法（选择排序、插入排序、冒泡排序）
  • O(n3) 立方时间复杂度 - Floyd算法 / 矩阵乘法运算
  • O(2n) 几何级数时间复杂度 - 汉诺塔
  • O(n!) 阶乘时间复杂度 - 旅行经销商问题 - NPC

排序算法

交换排序

冒泡排序

时间复杂度 O(n2)，空间复杂度 O
(1)，稳定排序算法。

def bubble_sort(alist):
    '''冒泡排序'''
    n = len(alist)
    for i in range(n-1):
        for j in range(n-i-1):
            if alist[j] > alist[j+1]:
                alist[j], alist[j+1] = alist[j+1], alist[j]
    return alist

快速排序（使用了分治策略和递归）

时间复杂度 O(n*log2n)， 空间复杂度 O(log2n)，非稳定排序算法。

原理：从序列中找出一个基准元素（pivot），然后大于该元素的放到一边，小于该元素的放到另一边形成分区；然后在分别冲大小分区中再找基准再分别分出相对大小分区，这样递归的完成快速排序。

def quick_sort(alist):
    '''快速排序'''
    if len(alist) <= 1:
        return alist
    else:
        # 设置基准元素为alist的第一个元素，也可以是其它
        pivot = alist[0]
        # 移除alist中的基准元素
        alist.remove(pivot)
        left_part, right_part = [], []
        for num in alist:
            if num <= pivot:
                left_part.append(num)
            else:
                right_part.append(num)
        return quick_sort(left_part) + [pivot] + quick_sort(right_part)

上面算法实现的快排在遍历数组时需要额外的空间，下面这种优化算法实现了原地排序。

def quick_sort_optimized(alist, start, end): # 注意不要让end溢出（end=len(alist)-1）
    '''快速排序优化'''
    if start >= end:
        return
    else:
        # 选取基准元素pivot
        pivot = alist[start]
        # 定义两个指（low、high）针从列表两端读取数据
        low = start
        high = end
        while low < high:
            # 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
            while low < high and pivot <= alist[high]:
                high -= 1
            # 当high指向的元素小于pivot时，将其放到low的位置上
            alist[low] = alist[high]
            # 如果low与high未重合，low指向的元素比基准元素大，则low向右移动
            while low < high and pivot > alist[low]:
                low += 1
            # 当low指向的元素大于pivot时，将其放到high的位置上
            alist[high] = alist[low]

        # 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
        # 将基准元素放到该位置
        alist[low] = pivot

        quick_sort_optimized(alist, start, low-1)
        quick_sort_optimized(alist, low+1, end)
        return alist

if __name__ == '__main__':
    import random
    l = list(range(20))
    random.shuffle(l)
    print(l)
    print(quick_sort_optimized(l,0,len(l)-1))

插入排序

直接插入排序

时间复杂度 O(n2)，空间复杂度 O(1)，稳定排序算法。

原理：通过构建一个初始的有序序列，然后从无序序列中抽取元素，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

def insert_sort(alist):
    '''插入排序'''
    n = len(alist)
    for i in range(1,n):
        j = i
        temp = alist[i]     # 每次循环待插入的数
        while j > 0 and temp < alist[j-1]:  # 从后往前做比较
            alist[j] = alist[j-1]   # 往后移动，给temp腾出位置
            j -= 1
        alist[j] = temp     # 将待插入的数填补进该空位
    return alist
    

# 将上面代码中的 while 循环用另一种方式实现
def insert_sort(items):
    for i in range(1, len(items)):
        # 从第i个元素开始向前比较，如果小于前一个元素，交换位置
        for j in range(i, 0, -1):
            if items[j] < items[j-1]:
                items[j], items[j-1] = items[j-1], items[j]
             else:
             # 终止内层循环
                break
    return items

希尔排序

时间复杂度 O(n*log2n)，空间复杂度 O(1)，非稳定排序算法。

希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。

希尔排序的原理是把序列按一定步长分组，对每组使用直接插入排序算法排序；当步长减至1时，整个序列被分成一组，完成最后一次比较，排序完成。

希尔排序图解

def shell_sort(alist):
    '''希尔排序'''
    n = len(alist)
    # 设置步长step，将alist分割成若干个子序列
    step = n // 2
    while step > 0:
        for i in range(step, n):
            # 设置指针j，并将待插入数据的位置赋予j
            j = i
            # 通过while循环，将待插入数据与以step为步长的子序列向前作比较
            # 当alist[j] >= alist[j-1]时，终止继续向前作比较
            while j >= step and alist[j] < alist[j-1]:
                alist[j], alist[j-step] = alist[j-step], alist[j]
                j -= step
        # 缩小步长step，直至step=1时，
        step = step // 2
    return alist

选择排序

简单选择排序

时间复杂度O(n2)，空间复杂度O(1)，非稳定排序算法。

选择排序原理：把序列中的最小值（或者最大值）找出来与第一个元素作比较，若该最小值小于第一个元素，则将其放到序列中的第一个位置，然后再从剩下的序列中找出极值放到第二个位置，以此类推。

def select_sort(alist):
    '''简单选择排序'''
    n = len(alist)
    for i in range(n-1):
        min_index = i
        for j in range(i+1,n):
            if alist[j] < alist[min_index]:
                min_index = j
        if min_index != i:
            alist[i], alist[min_index] = alist[min_index], alist[i]
    return alist

堆排序（未实现）

。。。

归并排序

时间复杂度 O(nlog₂n)，空间复杂度，O(1)，稳定排序算法。

归并排序是采用分治法的一个非常典型的应用，另一个可以采用分治法的是快速排序，归并算法比快速排序速度稍低。归并排序的思想就是先递归分解数组，再合并数组。

将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

def merge_sort(alist):
    '''归并排序'''

    def merge(left, right):
        '''合并函数'''
        l, r = 0, 0
        merge_list = []
        while l < len(left) and r < len(right):
            if left[l] <= right[r]:
                merge_list.append(left[l])
                l += 1
            else:
                merge_list.append(right[r])
                r += 1
        merge_list += left[l:]
        merge_list += right[r:]
        return merge_list

    def recursive(alist):
        '''递归函数'''
        if len(alist) <= 1:
            return alist
        mid = len(alist) // 2
        left = recursive(alist[:mid])
        right = recursive(alist[mid:])
        return merge(left,right)

    return recursive(alist)

非比较类排序

计数排序（counting sort）
桶排序（bucket sort）
基数排序（radix sort）

查找算法

平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

顺序查找

顺序查找又称为线性查找，适用于线性表的顺序存储结构和链式存储结构。该算法属于无序查找算法，时间复杂度为O(n)。

思路：从第一个元素到最后一个元素依次与待查值相比较，若值相同则返回改元素下标，若到最后也没找到则返回 -1 。

def seq_serch(items, key):
    '''顺序查找'''
    for index, item in enumerate(items):
        if item == key:
            return index
    return -1

二分查找

二分查找也称为折半查找，是一种在有序序列中查找某一特定元素的查找算法。该算法属于有序序查找算法，时间复杂度为O(logn)。

思路：选择序列（是一个有序的序列）中间的元素mid_value与待查值key作比较，若相同则返回下标结束查找，若不相同就选取一半可能包含key的区间继续查找，直到结束。

Tips：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》

def binary_search(items, key):
    '''二分查找'''
    start, end = 0, len(items)-1
    while start <= end:
        mid = (start+end) // 2
        if key < items[mid]:
            end = mid - 1
        elif key > items[mid]:
            start = mid + 1
        else:
            return mid
    return -1


def binary_search(items, key, start, end):
    '''二分查找，递归实现'''
    mid = (start + end) // 2
    while start <= end:
        if key < items[mid]:
            return binary_search(items,key,start,mid-1)
        elif key > items[mid]:
            return binary_search(items,key,mid+1,end)
        else:
            return mid
    return -1

插值查找

插值查找是基于二分查找，将查找点的选择改进为自适应选择，以提高查找效率。例如在 list(rang(100)) 中查找 key=10 ，二分查找选择的查找点是（50，25，12），我们可以同过算法使选择的查找值向key靠近。利用下述公式计算第一轮查找点 mid=10=key，直接结束查找。

插值查找核心算法公式：

mid = low+int((high-low)/(list[high]-list[low])*(key-list[low]))

时间复杂度(受元素分布的影响)：如果元素均匀分布，则 O(log log n)，如果分布非常不均匀可能需要 O(n)。当然插值查找也属于有序查找。

def insertion_search(items, key):
    '''插值排序'''
    if len(items) < 2:
        return
    low, high = 0, len(items) - 1
    while low < high:
        mid = low+int((high-low)/(items[high]-items[low])*(key-items[low]))
        if key < items[mid]:
            high = mid - 1
        elif key > items[mid]:
            low = mid + 1
        else:
            return mid
    return -1

未实现的查找算法

斐波那契查找、哈希查找、B树查找、二叉树查找 …

相关标签： 数据结构与算法 排序算法 快速排序 算法

上一篇： finally简单总结

下一篇： 【C】折半查找法

推荐阅读