Python实现的几个常用排序算法实例

yipeiwu_com6年前Python基础

前段时间为准备百度面试恶补的东西,虽然最后还是被刷了,还是把那几天的“战利品”放点上来,算法一直是自己比较薄弱的地方,以后还要更加努力啊。

下面用Python实现了几个常用的排序,如快速排序,选择排序,以及二路并归排序等等。

复制代码 代码如下:

#encoding=utf-8
import random
from copy import copy

def directInsertSort(seq):
 """ 直接插入排序 """
 size = len(seq)
 for i in range(1,size):
  tmp, j = seq[i], i
  while j > 0 and tmp < seq[j-1]:
   seq[j], j = seq[j-1], j-1
  seq[j] = tmp
 return seq

def directSelectSort(seq):
 """ 直接选择排序 """
 size = len(seq)
 for i in range(0,size - 1):
  k = i;j = i+1
  while j < size:
   if seq[j] < seq[k]:
    k = j
   j += 1
  seq[i],seq[k] = seq[k],seq[i]
 return seq

def bubbleSort(seq):
 """冒泡排序"""
 size = len(seq)
 for i in range(1,size):
  for j in range(0,size-i):
   if seq[j+1] < seq[j]:
    seq[j+1],seq[j] = seq[j],seq[j+1]
 return seq

def _divide(seq, low, high):
 """快速排序划分函数"""
 tmp = seq[low]
 while low != high:
  while low < high and seq[high] >= tmp: high -= 1
  if low < high:
   seq[low] = seq[high]
   low += 1
  while low < high and seq[low] <= tmp: low += 1
  if low < high:
   seq[high] = seq[low]
   high -= 1
 seq[low] = tmp
 return low

def _quickSort(seq, low, high):
 """快速排序辅助函数"""
 if low >= high: return
 mid = _divide(seq, low, high)
 _quickSort(seq, low, mid - 1)
 _quickSort(seq, mid + 1, high)

def quickSort(seq):
 """快速排序包裹函数"""
 size = len(seq)
 _quickSort(seq, 0, size - 1)
 return seq

def merge(seq, left, mid, right):
 tmp = []
 i, j = left, mid
 while i < mid and j <= right:
  if seq[i] < seq[j]:
   tmp.append(seq[i])
   i += 1
  else:
   tmp.append(seq[j])
   j += 1
 if i < mid: tmp.extend(seq[i:])
 if j <= right: tmp.extend(seq[j:])

 seq[left:right+1] = tmp[0:right-left+1]

def _mergeSort(seq, left, right):
 if left == right:
  return
 else:
  mid = (left + right) / 2
  _mergeSort(seq, left, mid)
  _mergeSort(seq, mid + 1, right)
  merge(seq, left, mid+1, right)

#二路并归排序
def mergeSort(seq):
 size = len(seq)
 _mergeSort(seq, 0, size - 1)
 return seq

if __name__ == '__main__':
 s = [random.randint(0,100) for i in range(0,20)]
 print s
 print "\n"
 print directSelectSort(copy(s))
 print directInsertSort(copy(s))
 print bubbleSort(copy(s))
 print quickSort(copy(s))
 print mergeSort(copy(s))


运行结果如下:
复制代码 代码如下:

E:\python_project\practice>sorting.py
[10, 47, 56, 76, 64, 84, 26, 8, 47, 51, 88, 81, 32, 95, 91, 29, 28, 69, 61, 45]


[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]

相关文章

面向对象学习之pygame坦克大战

经过一天多的奋战,查阅文献,参考别人的代码等等,完成了第一个面向对象的小项目,也深深体会到面向对象编程思想在游戏编程中所扮演的角色。 附上代码,参考了别人的代码,以及对他们代码的完善,又...

使用Python和Scribus创建一个RGB立方体的方法

使用Python和Scribus创建一个RGB立方体的方法

使用 Scribus 的 Python 脚本编写器功能,开发一个显示 RGB 色谱的 3D 立方体。 当我决定这个夏天要玩色彩游戏时,我想到通常色彩都是在色轮上描绘的。这些色彩通常都是使...

django框架模型层功能、组成与用法分析

本文实例讲述了django框架模型层功能、组成与用法。分享给大家供大家参考,具体如下: Django models是Django框架自定义的一套独特的ORM技术。 使用该层开发的首要任务...

python不使用for计算两组、多个矩形两两间的iou方式

python不使用for计算两组、多个矩形两两间的iou方式

解决问题: 不使用for计算两组、多个矩形两两间的iou 使用numpy广播的方法,在python程序中并不建议使用for语句,python中的for语句耗时较多,如果使用numpy广播...

浅谈Python数据类型之间的转换

Python数据类型之间的转换 函数 描述 int(x [,base])...