未加星标

python实现八大排序算法(1)

字体大小 | |
[开发(python) 所属分类 开发(python) | 发布者 店小二05 | 时间 | 作者 红领巾 ] 0人收藏点击收藏

排序

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

看图使理解更清晰深刻:

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

#!/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,用于标志某一趟排序过程中是否有数据交换,如果进行某一趟排序时并没有进行数据交换,则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程,改进后示例代码如下:

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

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

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

#!/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)
运行测试结果截图:
python实现八大排序算法(1)

过程分析:

第一步:

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

本文开发(python)相关术语:python基础教程 python多线程 web开发工程师 软件开发工程师 软件开发流程

分页:12
转载请注明
本文标题:python实现八大排序算法(1)
本站链接:http://www.codesec.net/view/565134.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 开发(python) | 评论(0) | 阅读(15)