排列顺序方法 常见的六种排序方法汇总

冒泡排序

冒泡排序(英语:Bubble Sort)是⼀种简单的排序算法。它重复地遍历要排序的数列,⼀次⽐较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的⼯作是重复地进⾏直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下:

  1. ⽐较相邻的元素。如果第⼀个⽐第⼆个⼤(升序),就交换他们两个。
  2. 对每⼀对相邻元素作同样的⼯作,从开始第⼀对到结尾的最后⼀对。步做完后,最后的元素会是最⼤的数。
  3. 针对所有的元素重复以上的步骤,除了最后⼀个。
  4. 持续每次对越来越少的元素重复上⾯的步骤,直到没有任何⼀对数字需要⽐较。
排列顺序方法 常见的六种排序方法汇总-熊猫号
import random


def get_rand_list(num):
    # 获取随机列表数据
    data = [random.randint(0, num * 2) for _ in range(num)]
    print('get_rand_li:', data)
    return data


def bubble_sort(data):
    """ 冒泡排序
    最优: O(N),对已经有序数据排序,只用遍历一遍
    最坏: O(N^2)
    稳定性: 稳定(如果比较为'>='则不稳定)
    """
    n = len(data)
    for i in range(n - 1):
        flag = True  # 表示没有交换
        # 一次遍历,最大放最后,下一次不用比较最大值
        for j in range(n - 1 - i):
            if data[j] > data[j + 1]:  # 将大元素后移
                data[j], data[j + 1] = data[j + 1], data[j]
                flag = False  # 存在交换
        if flag:  # 如果没有交换则已经排序好
            break
    return data

if __name__ == '__main__':
    list_num = 10
    print('bubble_sort:', bubble_sort(get_rand_list(list_num)), 'n')

选择排序

选择排序(Selection sort)是⼀种简单直观的排序算法。它的⼯作原理如下。⾸先在未排序序列中找到最⼩(⼤)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最⼩(⼤)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换⼀对元素,它们当中⾄少有⼀个将被移到其最终位置上,因此对n个元素的表进⾏排序总共进⾏⾄多n-1次交换。在所有的完全依靠交换去移动元素的排序⽅法中,选择排序属于⾮常好的⼀种。

排列顺序方法 常见的六种排序方法汇总-熊猫号
import random

def get_rand_list(num):
    # 获取随机列表数据
    data = [random.randint(0, num * 2) for _ in range(num)]
    print('get_rand_li:', data)
    return data

def select_sort(data):
    """ 选择排序
    最优,最坏: O(N^2)
    稳定性: 不稳定(相同元素,后面元素会先移到前面元素之前)
    """
    n = len(data)
    for i in range(n - 1):
        min_index = i  # 赋值最小值下标
        for j in range(i + 1, n):
            if data[j] < data[min_index]:
                min_index = j  # 找到更小的值则记录下标
        if i != min_index:
            data[i], data[min_index] = data[min_index], data[i]
    return data

if __name__ == '__main__':
    list_num = 10
    print('select_sort:', select_sort(get_rand_list(list_num)), 'n')

插入排序

插⼊排序(英语:Insertion Sort)是⼀种简单直观的排序算法。它的⼯作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插⼊。插⼊排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插⼊空间。

排列顺序方法 常见的六种排序方法汇总-熊猫号
import random

def get_rand_list(num):
    # 获取随机列表数据
    data = [random.randint(0, num * 2) for _ in range(num)]
    print('get_rand_li:', data)
    return data

def insert_sort(data):
    """ 插入排序
    最优: O(N),对已经有序数据排序,只用遍历一遍
    最坏: O(N^2)
    稳定性: 稳定
    """
    for i in range(1, len(data)):  # 从第二个元素开始
        for j in range(i, 0, -1):
            # j遍历的范围:[i,i-1,i-2,...,1]
            if data[j] < data[j - 1]:
                data[j], data[j - 1] = data[j - 1], data[j]
            else:  # 当前元素和前面数组组成有序,不需要再循环
                break
    return data

if __name__ == '__main__':
    list_num = 10
    print('insert_sort:', insert_sort(get_rand_list(list_num)), 'n')

希尔排序

希尔排序(Shell Sort)是插⼊排序的⼀种。也称缩⼩增量排序,是直接插⼊排序算法的⼀种更⾼效的改进版本。希尔排序是⾮稳定排序算法。该⽅法因DL.Shell于1959年提出⽽得名。 希尔排序是把记录按下标的⼀定增量分组,对每组使⽤直接插⼊排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减⾄1时,整个⽂件恰被分成⼀组,算法便终⽌。

希尔排序过程:希尔排序的基本思想是:将数组列在⼀个表中并对列分别进⾏插⼊排序,重复这过程,不过每次⽤更⻓的列(步⻓更⻓了,列数更少了)来进⾏。最后整个表就只有⼀列了。将数组转换⾄表是为了更好地理解这算法,算法本身还是使⽤数组进⾏排序。

例如,假设有这样⼀组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10],如果我们以步⻓为5开始进⾏排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样(竖着的元素是步⻓组成):

13 14 94 33 82

25 59 94 65 23

45 27 73 25 39

10

然后我们对每列进⾏排序:

10 14 73 25 23

13 27 94 33 39

25 59 94 65 82

45

将上述四⾏数字,依序接在⼀起时我们得到:[ 10 14 73 25 23 13 27 94 3339 25 59 94 65 82 45 ]。这时10已经移⾄正确位置了,然后再以3为步⻓进⾏排序:

10 14 73

25 23 13

27 94 33

39 25 59

94 65 82

45

排序之后变为:

10 14 13

25 23 33

27 25 59

39 65 73

45 94 82

94

最后以1步⻓进⾏排序(此时就是简单的插⼊排序了)

排列顺序方法 常见的六种排序方法汇总-熊猫号
import random

def get_rand_list(num):
    # 获取随机列表数据
    data = [random.randint(0, num * 2) for _ in range(num)]
    print('get_rand_li:', data)
    return data

def shell_sort(data):
    """ 希尔排序
    最优: 根据步⻓序列的不同⽽不同,去掉那个break就是O(N)
    最坏: O(N^2)
    稳定性: 不稳定(因为相同元素可能存在不同步长中,排序后相对位置会变)
    """
    n = len(data)
    gap = n // 2  # 初始步长为长度的一半
    while gap >= 1:  # 步长为1的时候完成排序
        for j in range(gap, n):  # 按步长进行插入排序
            while (j - gap) >= 0:
                if data[j] < data[j - gap]:
                    data[j], data[j - gap] = data[j - gap], data[j]
                    j -= gap
                else:  # 当前已经有序
                    break
        gap //= 2  # 更新间隔
    return data

if __name__ == '__main__':
    list_num = 10
    print('shell_sort :', shell_sort(get_rand_list(list_num)), 'n')

快速排序

快速排序(英语:Quicksort),⼜称划分交换排序(partition-exchangesort),通过⼀趟排序将要排序的数据分割成独⽴的两部分,其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩,然后再按此⽅法对这两部分数据分别进⾏快速排序,整个排序过程可以递归进⾏,以此达到整个数据变成有序序列。

步骤为:

  1. 从数列中挑出⼀个元素,称为”基准”(pivot)
  2. 重新排序数列,所有元素⽐基准值⼩的摆放在基准前⾯,所有元素⽐基准值⼤的摆在基准的后⾯(相同的数可以到任⼀边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursive)把⼩于基准值元素的⼦数列和⼤于基准值元素的⼦数列排序。

递归的最底部情形,是数列的⼤⼩是零或⼀,也就是永远都已经被排序好了。虽然⼀直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它⾄少会把⼀个元素摆到它最后的位置去。

排列顺序方法 常见的六种排序方法汇总-熊猫号
import random

def get_rand_list(num):
    # 获取随机列表数据
    data = [random.randint(0, num * 2) for _ in range(num)]
    print('get_rand_li:', data)
    return data

def quick_sort(data):
    """ 快速排序
    最优: O(nlogn)
    最坏: O(N^2)
    稳定性: 不稳定
    """

    def quick_sort_base(base_data, start, end):
        # 定义快速排序递归实现
        if start >= end:
            return  # 递归结束条件
        # 设定起始元素基准元素
        mid = base_data[start]
        # left为序列左边的由左向右移动的游标
        left = start
        # right为序列右边的由右向左移动的游标
        right = end
        # left与right未重合,就向中间移动
        while left < right:
            # 如果left与right未重合,right指向的元素不⽐基准元素⼩,则right向左移动
            while left < right and base_data[right] >= mid:
                right -= 1
            # 将right指向的元素放到left的位置上
            base_data[left] = base_data[right]
            # 如果left与right未重合,left指向的元素⽐基准元素⼩,则left向右移动
            while left < right and base_data[left] < mid:
                left += 1
            # 将left指向的元素放到right的位置上
            base_data[right] = base_data[left]
        # 从循环退出后,left与right相遇,即left==right
        base_data[left] = mid
        # 对左边部分执行快速排序
        quick_sort_base(base_data, start, left - 1)
        # 对右边部分执行快速排序
        quick_sort_base(base_data, left + 1, end)

    quick_sort_base(data, 0, len(data) - 1)
    return data

if __name__ == '__main__':
    list_num = 10
    print('quick_sort :', quick_sort(get_rand_list(list_num)), 'n')

归并排序

归并排序是采⽤分治法的⼀个⾮常典型的应⽤。归并排序的思想就是先递归分解数组,再合并数组。将数组分解最⼩之后,然后合并两个有序数组,基本思路是⽐较两个数组的最前⾯的数,谁⼩就先取谁,取了后相应的指针就往后移⼀位。然后再⽐较,直⾄⼀个数组为空,最后把另⼀个数组的剩余部分复制过来即可。

排列顺序方法 常见的六种排序方法汇总-熊猫号
import random

def get_rand_list(num):
    # 获取随机列表数据
    data = [random.randint(0, num * 2) for _ in range(num)]
    print('get_rand_li:', data)
    return data

def merge_sort(data):
    """ 归并排序
    最优: O(nlogn)
    最坏: O(nlogn)
    稳定性: 稳定
    """
    # 当只剩余一个元素,则返回这个列表
    if (n := len(data)) <= 1:
        return data
    # 从中间二分数据
    mid = n // 2
    # 对左半部分进行归并排序
    left_sorted_list = merge_sort(data[:mid])
    # 对右半部分进行归并排序
    right_sorted_list = merge_sort(data[mid:])
    # 合并两个有序集合
    left, right = 0, 0
    # 存放最终结果
    merge_sorted_list = []
    # 得到左右列表长度
    left_n, right_n = len(left_sorted_list), len(right_sorted_list)
    # 当左右游标都在范围内则进行排序
    while left < left_n and right < right_n:
        if left_sorted_list[left] <= right_sorted_list[right]:
            # 左边小则添加左边元素
            merge_sorted_list.append(left_sorted_list[left])
            left += 1
        else:
            # 右边小则添加左边元素
            merge_sorted_list.append(right_sorted_list[right])
            right += 1

    # 将左边列表剩余元素追加
    merge_sorted_list += left_sorted_list[left:]
    # 将右边列表剩余元素追加
    merge_sorted_list += right_sorted_list[right:]
    return merge_sorted_list

if __name__ == '__main__':
    list_num = 10
    print('merge_sort :', merge_sort(get_rand_list(list_num)), 'n')

常⻅排序算法效率⽐较

关于排序算法稳定性的定义:待排序元素中两个相同元素A和B,A在B前面,当经过排序后B移动到了A前面则说明该排序算法不稳定,如果A还是在B前面则说明该排序算法稳定。

排列顺序方法 常见的六种排序方法汇总-熊猫号

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 2476560997@qq.com 举报,一经查实,本站将立刻删除。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 2022年3月12日 7:20 上午
下一篇 2022年3月13日 6:47 上午

相关推荐

  • bitlocker强制破解 三种思路巧妙破解Bitlocker加密

    课前提要 BitLocker加密是Windows的一种数据保护功能,主要用于解决由于计算机设备的物理丢失导致的数据失窃或恶意泄漏,能够同时支持FAT和NTFS两种格式,可以加密电脑的整个系统分区,也可以加密可移动的便携存储设备,如U盘和移动硬盘等。 BitLocker使用AES(高级加密标准/Advanced Encryption Standard)128位…

    2022年3月12日
    653
  • d盘删除了c盘扩展卷仍为灰色 教你解决扩展卷选项变成灰色问题

    在Windows 10、8或7中,您是否尝试扩展磁盘分区?磁盘管理中的扩展卷选项变成灰色,无法增加磁盘分区大小?放轻松!本文提供了有效方法可以帮助您解决这个问题并轻松扩展磁盘分区。 本文内容: 1. 为何扩展卷选项变成灰色2. 如何运用未分配空间扩展分区 问:无法将分割区扩展到未分配空间,该怎么解决? 「你好,你知道如何解决磁盘管理中的扩展卷选项变成灰色的问…

    2022年3月12日
    1.7K
  • 服务器cdn防御 什么是CDN劫持如何进行防御

    CDN能加速大家都知道,但其中原理不少人都不清楚。其实,CDN本身就是一种DNS劫持,只不过是良性的。 不同于黑客强制DNS把域名解析到自己的钓鱼IP上,CDN则是让DNS主动配合,把域名解析到临近的服务器上。 这台服务器同样也开启了HTTP代理,让用户感觉不到CDN的存在。 不过CDN劫持不像黑客那样贪心,劫持用户所有流量,它只『劫持』用户的静态资源访问,…

    2022年2月28日
    45
  • 大屏数据可视化前端 从0-1制作数据可视化大屏

    都说「数不如图」,在数据报告中,就常常借助图形化的手段将数据清晰表达出来,可以更简单有效地传达和沟通。 这两年,数据可视化大屏在数据报告中的占比越来越大,企业和政府会更倾向于选择炫酷大屏进行数据分析展示。炫酷大屏不仅能实时监控重点数据,提高决策效率,放在公司会议室,展台等地方,还能提升公司形象。 作为一个从事可视化大屏项目3年多的秃头技术,做过大大小小几十个…

    2022年3月12日
    389
  • 相似图片识图 百度识图查找图源及相似图

    搜索引擎是大家日常生活经常使用的工具,遇到不了解的事就搜一下,很方便。但有时候,如果根本不知道要搜索的东西是什么,就很难去搜索。对此,我们可以以图搜图,用图片去搜索,解决上述难题。 地址:参见文末图 在“百度识图”可以直接上传图片,即可开始搜索。官方给出的应用范围包括商品、素材、植物、人物、风景等。 ONETer用Windows11的默认桌面作为搜索图,搜索…

    2022年3月12日
    147
  • 怎么破解私人充值网站 小伙利用Python爆破某会员网站

    寒假在家上网,qq群里一位好友给我说他想要某个网站的会员,ps(是个小网站),本着助人为乐的精神我去踩了点。。。 是吗 然后就有了思路(骚操作) 这是小编准备的python学习资料,为了你们更好的学习python,关注,转发,私信小编“01”即可免费领取! 先讲一下思路 1 .先注册用户登录 2.flidder抓包 3.python 模拟登录 4.在评论区抓…

    2022年3月12日
    1.1K
  • address解决方法 程序运行Address的解决方法

    ★问题描述★: 我们打开某个程序(.EXE后缀的可执行文件)时提示:Access ViolatiOn At Address xxxxxxxxx,每个程序出现的代码也不一致。 今天在架设**世界的服务器端时,提示要运行EasyWeb程序,但双击运行该程序时提示:Access violation at address 004C0B3D,随即我们通过一系列操作让E…

    2022年3月12日
    63

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部