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

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

下面用Python实现了几个常用的排序如快速排序选择排序以及二路并归排序等等。
代码如下:
#encoding=utf-8
import random
from copy import copy

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 _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\practicesorting.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]