快速排序的算法思想及Python版快速排序的實現(xiàn)示例

更新時間：2016年07月02日 10:29:41 作者：cangmean

快速排序算法來源于分治法的思想策略,這里我們將來為大家簡單解析一下快速排序的算法思想及Python版快速排序的實現(xiàn)示例:

快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。

1.分治法的基本思想

分治法的基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。

2.快速排序的基本思想

設(shè)當(dāng)前待排序的無序區(qū)為R[low..high]，利用分治法可將快速排序的基本思想描述為：

（1）分解：

在R[low..high]中任選一個記錄作為基準(zhǔn)(Pivot)，以此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左、右兩個較小的子區(qū)間R[low..pivotpos-1)和R[pivotpos+1..high]，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key，而基準(zhǔn)記錄pivot則位于正確的位置(pivotpos)上，它無須參加后續(xù)的排序。

注意：

劃分的關(guān)鍵是要求出基準(zhǔn)記錄所在的位置pivotpos。劃分的結(jié)果可以簡單地表示為(注意pivot=R[pivotpos])：

R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys

其中l(wèi)ow≤pivotpos≤high。

（2）求解：

通過遞歸調(diào)用快速排序?qū)ψ?、右子區(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

（3）組合：

因為當(dāng)"求解"步驟中的兩個遞歸調(diào)用結(jié)束時，其左、右兩個子區(qū)間已有序。對快速排序而言，"組合"步驟無須做什么，可看作是空操作。

Python實現(xiàn)

原理: 先用初始數(shù)據(jù)，然后對這個數(shù)據(jù)進(jìn)行排序使左邊的數(shù)據(jù)小于
該數(shù)據(jù)，右邊的大于該數(shù)據(jù)，然后用遞歸的方法對兩邊的數(shù)據(jù)進(jìn)行依次排序。

#!/usr/bin/env python
#_*_coding:utf-8_*_ 

def rand(x):
 import random
 if x < 3:
  x = 5
 if x > 1000:
  print "big data"
  return []
 l = range(1, x)
 li = []
 while l:
  r = random.randint(0, len(l)-1)
  li.append(l.pop(r))
 return li

def quicksort(l, low, hight):
 key = l[low]
 while low < hight:
  while key <= l[hight] and low < hight:
   hight -= 1
  l[low], l[hight] = l[hight], l[low]

  while key >= l[low] and low < hight:
   low += 1
  l[low], l[hight] = l[hight], l[low]

 l[hight] = key
 return hight

def m_sort(l, low, hight):
 if low >= hgiht:
  return 

 index = quicksort(l, low, hight)
 m_sort(l, low, index)
 m_sort(l, index+1, hight)

def main():
 l = rand(1500)
 m_sort(l, 0, len(l)-1)
 print l

if __name__ == '__main__':
 main()

您可能感興趣的文章: