前段時間為準備百度面試惡補的東西，雖然最后還是被刷了，還是把那幾天的“戰利品”放點上來，算法一直是自己比較薄弱的地方，以后還要更加努力啊。
下面用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]
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
