快捷導(dǎo)航

Python實(shí)現(xiàn)的幾個(gè)常用排序算法實(shí)例

更新時(shí)間：2014年06月16日 11:09:04 投稿：junjie

這篇文章主要介紹了Python實(shí)現(xiàn)的幾個(gè)常用排序算法實(shí)例例如直接插入排序、直接選擇排序、冒泡排序、快速排序等,需要的朋友可以參考下

前段時(shí)間為準(zhǔn)備百度面試惡補(bǔ)的東西，雖然最后還是被刷了，還是把那幾天的“戰(zhàn)利品”放點(diǎn)上來(lái)，算法一直是自己比較薄弱的地方，以后還要更加努力啊。

下面用Python實(shí)現(xiàn)了幾個(gè)常用的排序，如快速排序，選擇排序，以及二路并歸排序等等。

#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):
"""快速排序劃分函數(shù)"""
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):
"""快速排序輔助函數(shù)"""
if low >= high: return
mid = _divide(seq, low, high)
_quickSort(seq, low, mid - 1)
_quickSort(seq, mid + 1, high)

def quickSort(seq):
"""快速排序包裹函數(shù)"""
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))

運(yùn)行結(jié)果如下：

復(fù)制代碼代碼如下:

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]

您可能感興趣的文章: