个人中心
gpt4 book ai didi

python实现八大排序算法（1）

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 27 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章python实现八大排序算法（1）由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

排序 。

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

看图使理解更清晰深刻:

python实现八大排序算法（1）

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

常见排序算法 。

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

本文将用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代码实现:

 
?
1
 
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/usr/bin/env python
#coding:utf-8
'''
file:python-8sort.py
date:9/1/17 9:03 AM
author:lockey
email:lockey@123.com
desc:python实现八大排序算法
'''
lst1 = [ 2 , 5435 , 67 , 445 , 34 , 4 , 34 ]
def bubble_sort_basic(lst1):
  lstlen = len (lst1);i = 0
  while i < lstlen:
   for j in range ( 1 ,lstlen):
    if lst1[j - 1 ] > lst1[j]:
    #对比相邻两个元素的大小，小的元素上浮
     lst1[j],lst1[j - 1 ] = lst1[j - 1 ],lst1[j]
   i + = 1
   print 'sorted{}: {}' . format (i, lst1)
  print '-------------------------------'
  return lst1
bubble_sort_basic(lst1)

冒泡排序算法的改进 。

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

 
?
1
 
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 lst2
bubble_sort_improve(lst2)

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

python实现八大排序算法（1）

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

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代码实现:

 
?
1
 
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- 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 lst
sorted = selection_sort(lst)
print ( 'The sorted result is: {}' . format ( sorted ))

运行结果截图:

python实现八大排序算法（1）

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代码实现:

 
?
1
 
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- 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 lst
sorted = insert_sort(lst)
print ( 'The sorted result is: {}' . format ( sorted ))

运行结果截图:

python实现八大排序算法（1）

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

4. 希尔排序 。

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

算法原理 。

算法核心为分组（按步长）、组内插入排序 。

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d<n)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操作，直到d=1.

python代码实现:

 
?
1
 
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#!/usr/bin/env python
#coding:utf-8
'''
file:python-8sort.py
date:9/1/17 9:03 AM
author:lockey
email:lockey@123.com
desc: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 < count:
     k = j - group
     key = lists[j]
     while k > = 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 lists
shell_sort(lst)

运行测试结果截图:

过程分析:

第一步:

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

python实现八大排序算法（1）

然后各组内进行插入排序，经过5（5组*1次）次组内插入排序得到了序列:

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

python实现八大排序算法（1）

第二步:

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

python实现八大排序算法（1）

然后各组内进行插入排序，经过8（2组*4次）次组内插入排序得到了序列:

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

python实现八大排序算法（1）

第三步:

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。希尔排序方法是一个不稳定的排序方法 。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我.

原文链接：http://blog.csdn.net/lockey23/article/details/77760746 。

最后此篇关于python实现八大排序算法（1）的文章就讲到这里了,如果你想了解更多关于python实现八大排序算法（1）的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

27 4 0
文章推荐： Python3.4编程实现简单抓取爬虫功能示例
文章推荐： JavaScript正则表达式迷你书之贪婪模式-学习笔记
文章推荐： javascript正则表达式RegExp入门图文教程
文章推荐： php导入导出excel实例
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com