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]