Python实现的几个常用排序算法实例
本文导语: 前段时间为准备百度面试恶补的东西,虽然最后还是被刷了,还是把那几天的“战利品”放点上来,算法一直是自己比较薄弱的地方,以后还要更加努力啊。 下面用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] = 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