总结有关python实现八大排序算法(上)

这篇文章主要为大家详细介绍了python实现八大排序算法的第一篇,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

排序

排序是计算机内经常进行的一种操作,其目的是将一组”无序”的记录序列调整为”有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能完全在内存中完成,需要访问外存,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

看图使理解更清晰深刻:

这里写图片描述

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

立即学习“Python免费学习笔记(深入)”;

常见排序算法

快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法

本文将用Python实现冒泡排序、插入排序、希尔排序、快速排序、直接选择排序、堆排序、归并排序、基数排序这八大排序算法。

1. 冒泡排序(Bubble Sort)

算法原理:

已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先比较a[1]与a[2]的值,若a[1]大于a[2]则交换两者的值,否则不变。再比较a[2]与a[3]的值,若a[2]大于a[3]则交换两者的值,否则不变。再比较a[3]与a[4],以此类推,最后比较a[n-1]与a[n]的值。这样处理一轮后,a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮,则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮,以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。降序排列与升序排列相类似,若a[1]小于a[2]则交换两者的值,否则不变,后面以此类推。 总的来讲,每一轮排序后最大(或最小)的数将移动到数据序列的最后,理论上总共要进行n(n-1)/2次交换。

优点:稳定;
缺点:慢,每次只能移动相邻两个数据。

python代码实现:

#!/usr/bin/env python#coding:utf-8'''file:python-8sort.pydate:9/1/17 9:03 AMauthor:lockeyemail:lockey@123.comdesc:python实现八大排序算法'''lst1 = [2,5435,67,445,34,4,34]def bubble_sort_basic(lst1): lstlen = len(lst1);i = 0 while i  lst1[j]:   #对比相邻两个元素的大小,小的元素上浮    lst1[j],lst1[j-1] = lst1[j-1],lst1[j]  i += 1  print 'sorted{}: {}'.format(i, lst1) print '-------------------------------' return lst1bubble_sort_basic(lst1)

登录后复制

冒泡排序算法的改进

对于全员无序或者没有重复元素的序列,上述算法在同一思路上是没有改进余地的,但是如果一个序列中存在重复元素或者部分元素是有序的呢,这种情况下必然会存在不必要的重复排序,那么我们可以在排序过程中加入一标志性变量change,用于标志某一趟排序过程中是否有数据交换,如果进行某一趟排序时并没有进行数据交换,则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程,改进后示例代码如下:

lst2 = [2,5435,67,445,34,4,34]def bubble_sort_improve(lst2): lstlen = len(lst2) i = 1;times = 0 while i > 0:  times += 1  change = 0  for j in range(1,lstlen):   if lst2[j-1] > lst2[j]:   #使用标记记录本轮排序中是否有数据交换    change = j    lst2[j],lst2[j-1] = lst2[j-1],lst2[j]  print 'sorted{}: {}'.format(times,lst2)  #将数据交换标记作为循环条件,决定是否继续进行排序  i = change return lst2bubble_sort_improve(lst2)

登录后复制

两种情况下运行截图如下:

这里写图片描述

由上图可以看出,对于部分元素为有序排列的序列,优化后的算法减少了两轮排序。

2.选择排序(Selection Sort)

算法原理:

每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:

①初始状态:无序区为R[1..n],有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

优点:移动数据的次数已知(n-1次);
缺点:比较次数多,不稳定。

python代码实现:

# -*- coding: UTF-8 -*-'''Created on 2017年8月31日Running environment:win7.x86_64 eclipse python3@author: Lockey'''lst = [65,568,9,23,4,34,65,8,6,9]def selection_sort(lst): lstlen = len(lst) for i in range(0,lstlen):  min = i  for j in range(i+1,lstlen):  #从 i+1开始循环遍历寻找最小的索引   if lst[min] > lst[j]:    min = j  lst[min],lst[i] = lst[i],lst[min]  #一层遍历结束后将最小值赋给外层索引i所指的位置,将i的值赋给最小值索引    print('The {} sorted: {}'.format(i+1,lst)) return lstsorted = selection_sort(lst)print('The sorted result is: {}'.format(sorted))

登录后复制

运行结果截图:

这里写图片描述

3. 插入排序

算法原理:

已知一组升序排列数据a[1]、a[2]、……a[n],一组无序数据b[1]、b[2]、……b[m],需将二者合并成一个升序数列。首先比较b[1]与a[1]的值,若b[1]大于a[1],则跳过,比较b[1]与a[2]的值,若b[1]仍然大于a[2],则继续跳过,直到b[1]小于a数组中某一数据a[x],则将a[x]~a[n]分别向后移动一位,将b[1]插入到原来a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。(若无数组a,可将b[1]当作n=1的数组a)
优点:稳定,快;
缺点:比较次数不一定,比较次数越多,插入点后的数据移动越多,特别是当数据总量庞大的时候,但用链表可以解决这个问题。

算法复杂度

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。

python代码实现:

# -*- coding: UTF-8 -*-'''Created on 2017年8月31日Running environment:win7.x86_64 eclipse python3@author: Lockey'''lst = [65,568,9,23,4,34,65,8,6,9]def insert_sort(lst): count = len(lst) for i in range(1, count):  key = lst[i]  j = i - 1  while j >= 0:   if lst[j] > key:    lst[j + 1] = lst[j]    lst[j] = key   j -= 1  print('The {} sorted: {}'.format(i,lst)) return lstsorted = insert_sort(lst)print('The sorted result is: {}'.format(sorted))

登录后复制

运行结果截图:

这里写图片描述

由排序过程可知,每次往已经排好序的序列中插入一个元素,然后排序,下次再插入一个元素排序。。。直到所有元素都插入,排序结束

4. 希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。

算法原理

算法核心为分组(按步长)、组内插入排序

已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。发现当n不大时,插入排序的效果很好。首先取一增量d(d

python代码实现:

#!/usr/bin/env python#coding:utf-8'''file:python-8sort.pydate:9/1/17 9:03 AMauthor:lockeyemail:lockey@123.comdesc:python实现八大排序算法'''lst = [65,568,9,23,4,34,65,8,6,9]def shell_sort(lists): print 'orginal list is {}'.format(lst) count = len(lists) step = 2 times = 0 group = int(count/step) while group > 0:  for i in range(0, group):   times += 1   j = i + group   while j = 0:     if lists[k] > key:      lists[k + group] = lists[k]      lists[k] = key     k -= group    j += group    print 'The {} sorted: {}'.format(times,lists)  group = int(group/step) print 'The final result is: {}'.format(lists) return listsshell_sort(lst)

登录后复制

运行测试结果截图:
这里写图片描述

过程分析:

第一步:

1-5:将序列分成了5组(group = int(count/step)),如下图,一列为一组:

这里写图片描述

然后各组内进行插入排序,经过5(5组*1次)次组内插入排序得到了序列:

The 1-5 sorted:[34, 65, 8, 6, 4, 65, 568, 9, 23, 9]

这里写图片描述

第二步:

6666-7777:将序列分成了2组(group = int(group/step)),如下图,一列为一组:

这里写图片描述 

然后各组内进行插入排序,经过8(2组*4次)次组内插入排序得到了序列:

The 6-7 sorted: [4, 6, 8, 9, 23, 9, 34, 65, 568, 65]

这里写图片描述

第三步:

888888888:对上一个排序结果得到的完整序列进行插入排序:

[4, 6, 8, 9, 23, 9, 34, 65, 568, 65]

经过9(1组*10 -1)次插入排序后:

The final result is: [4, 6, 8, 9, 9, 23, 34, 65, 65, 568]

希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:增量因子中除1 外没有公因子,且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法

以上就是总结有关python实现八大排序算法(上)的详细内容,更多请关注【创想鸟】其它相关文章!

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

发布者:PHP中文网,转转请注明出处:https://www.chuangxiangniao.com/p/2266352.html

(0)
上一篇 2025年2月27日 09:17:34
下一篇 2025年2月18日 12:59:14

AD推荐 黄金广告位招租... 更多推荐

相关推荐

  • Python实现输出程序执行进度百分比

    这篇文章主要介绍了python实现输出程序执行进度百分比的方法,涉及python数值运算与系统输出相关操作技巧,需要的朋友可以参考下 本文实例讲述了Python实现输出程序执行进度百分比的方法。分享给大家供大家参考,具体如下: 对于一些大型…

    2025年2月27日
    200
  • Python实现求笛卡尔乘积方法详解

    这篇文章主要介绍了python实现求笛卡尔乘积的方法,结合实例形式分析了python计算笛卡尔乘积的原理与实现技巧,需要的朋友可以参考下 本文实例讲述了Python实现求笛卡尔乘积的方法。分享给大家供大家参考,具体如下: 在数学中,两个集合…

    2025年2月27日
    200
  • python中Socket之客户端与服务端握手的实例

    这篇文章主要为大家详细介绍了python socket之客户端和服务端握手,具有一定的参考价值,感兴趣的小伙伴们可以参考一下 简单的学习下利用socket来建立客户端和服务端之间的连接并且发送数据 1. 客户端socketClient.py…

    2025年2月27日
    200
  • Python中time模块求程序运行时间的方法实例分享

    这篇文章主要介绍了python基于time模块求程序运行时间的方法,涉及python time模块的使用及数值运算相关操作技巧,需要的朋友可以参考下 本文实例讲述了Python基于time模块求程序运行时间的方法。分享给大家供大家参考,具体…

    2025年2月27日
    200
  • 使用Python变量易错点介绍

    python编程中经常遇到一些莫名其妙的错误, 其实这不是语言本身的问题, 而是我们忽略了语言本身的一些特性导致的,今天就来看下使用python变量时导致的3个不可思议的错误, 以后在编程中要多多注意。 1、 可变数据类型作为函数定义中的默…

    编程技术 2025年2月27日
    200
  • 详解Python中的魔术方法

    介绍   在python中,所有以“__”双下划线包起来的方法,都统称为“magic method”,中文称『魔术方法』,例如类的初始化方法 __init__ ,python中所有的魔术方法均在官方文档中有相应描述,但是对于官方的描述比较混…

    编程技术 2025年2月27日
    100
  • 比较Python序列化模块pickle和json不同

    这是用于序列化的两个模块: • json: 用于字符串和python数据类型间进行转换 • pickle: 用于python特有的类型和python的数据类型间进行转换 Json模块提供了四个功能:dumps、dump、loads、load…

    编程技术 2025年2月27日
    200
  • Python字典容器介绍

    字典(dictionary) 我们都曾经使用过语言词典来查找不认识的单词的定义。语言词典针对给定的单词(比如 python)提供一组标准的信息。这种系统将定义和其他信息与实际的单词关联(映射)起来。使用单词作为键定位器来寻找感兴趣的信息。这…

    编程技术 2025年2月27日
    200
  • Python中线程的MQ消息队列实现及优缺点介绍

    消息队列(mq,message queue)在消息数据传输中的保存作用为数据通信提供了保障和实时处理上的便利,这里我们就来看一下python中线程的mq消息队列实现以及消息队列的优点解析 “消息队列”是在消息的传输过程中保存消息的容器。消息…

    编程技术 2025年2月27日
    200
  • 分析Python解析XML的几种方式

    在最初学习python的时候,只知道有dom和sax两种解析方法,但是其效率都不够理想,由于需要处理的文件数量太大,这两种方式耗时太高无法接受。 在网络搜索后发现,目前应用比较广泛,且效率相对较高的ElementTree也是一个比较多人推荐…

    2025年2月27日
    200

发表回复

登录后才能评论