返回
最新动态
一文读懂Python版的十大经典排序算法（附动图演示）
2025-01-03 06:17

来源：大数据DT


  • 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

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

    • 名词解释：


    • n：数据规模。

    • k：“桶”的个数。

    • In-place：占用常数内存，不占用额外内存。

    • Out-place：占用额外内存。

    01 冒泡排序

    冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

    1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
    2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
    3. 重复第二步，直到所有元素均排序完毕。
    1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
    2. 按增量序列个数 k，对序列进行 k 趟排序；
    3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。


    2. Python 代码

    def shellSort(arr):    import math    gap=1    while(gap < len(arr)/3):        gap = gap*3+1    while gap > 0:        for i in range(gap,len(arr)):            temp = arr[i]            j = i-gap            while j >=0 and arr[j] > temp:                arr[j+gap]=arr[j]                j-=gap            arr[j+gap] = temp        gap = math.floor(gap/3)    return arr}

    05 归并排序

    归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

    作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

    • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
    • 自下而上的迭代。

    和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

    1. 在额外空间充足的情况下，尽量增大桶的数量。
    2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。


    同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

    • 什么时候最快
    当输入的数据可以均匀的分配到每一个桶中。

    • 什么时候最慢

    当输入的数据被分配到了同一个桶中。

    • Python 代码

    def bucket_sort(s):    """桶排序"""    min_num = min(s)    max_num = max(s)    # 桶的大小    bucket_range = (max_num-min_num) / len(s)    # 桶数组    count_list = [ [] for i in range(len(s) + 1)]    # 向桶数组填数    for i in s:        count_list[int((i-min_num)//bucket_range)].append(i)    s.clear()    # 回填，这里桶内部排序直接调用了sorted    for i in count_list:        for j in sorted(i):            s.append(j)
    if __name__ == __main__ :    a = [3.2,6,8,4,2,6,7,3]bucket_sort(a)print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]

    10 基数排序

    基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。


    基数排序有两种方法：

    这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

    • 基数排序：根据键值的每位数字来分配桶；
    • 计数排序：每个桶只存储单一键值；
    • 桶排序：每个桶存储一定范围的数值。

    2. 动图演示


    3. Python 代码

    def RadixSort(list):    i = 0                                    #初始为个位排序    n = 1                                     #最小的位数置为1（包含0）    max_num = max(list) #得到带排序数组中最大数    while max_num > 10**n: #得到最大数是几位数        n += 1    while i < n:        bucket = {} #用字典构建桶        for x in range(10):            bucket.setdefault(x, []) #将每个桶置空        for x in list: #对每一位进行排序            radix =int((x / (10**i)) % 10) #得到每位的基数            bucket[radix].append(x) #将对应的数            组元素加入到相 #应位基数的桶中        j = 0        for k in range(10):            if len(bucket[k]) != 0: #若桶不为空                for y in bucket[k]: #将该桶中每个元素                    list[j] = y #放回到数组中                    j += 1        i += 1return  list
    

    
    
            
    以上就是本篇文章【一文读懂Python版的十大经典排序算法（附动图演示）】的全部内容了，欢迎阅览 ！ 文章地址：https://sicmodule.kub2b.com/quote/18390.html 
         

栏目首页     
相关文章     
动态     
同类文章     
热门文章     
网站地图     
返回首页 企库往资讯移动站https://sicmodule.kub2b.com/mobile/,查看更多   
    发表评论
    0评