#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]