总结有关python实现八大排序算法（上）

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

#!/usr/bin/env python
#coding:utf-8
'''
file:python-8sort.py
date:9/1/17 9:03 AM
author:lockey
email:lockey@123测试数据
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) 

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) 

# -*- 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)) 

# -*- 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)) 

#!/usr/bin/env python
#coding:utf-8
'''
file:python-8sort.py
date:9/1/17 9:03 AM
author:lockey
email:lockey@123测试数据
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)）,如下图，一列为一组：

然后各组内进行插入排序，经过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实现八大排序算法（上）的详细内容，更多请关注Gxl网其它相关文章！

查看更多关于总结有关python实现八大排序算法（上）的详细内容...