快速排序的算法思想及Python版快速排序的實(shí)現(xiàn)示例
快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略,通常稱其為分治法(Divide-and-ConquerMethod)。
1.分治法的基本思想
分治法的基本思想是:將原問題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題,然后將這些子問題的解組合為原問題的解。
2.快速排序的基本思想
設(shè)當(dāng)前待排序的無序區(qū)為R[low..high],利用分治法可將快速排序的基本思想描述為:
(1)分解:
在R[low..high]中任選一個(gè)記錄作為基準(zhǔn)(Pivot),以此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左、右兩個(gè)較小的子區(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é)果可以簡(jiǎn)單地表示為(注意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)組合:
因?yàn)楫?dāng)"求解"步驟中的兩個(gè)遞歸調(diào)用結(jié)束時(shí),其左、右兩個(gè)子區(qū)間已有序。對(duì)快速排序而言,"組合"步驟無須做什么,可看作是空操作。
Python實(shí)現(xiàn)
原理: 先用初始數(shù)據(jù), 然后對(duì)這個(gè)數(shù)據(jù)進(jìn)行排序使左邊的數(shù)據(jù)小于
該數(shù)據(jù),右邊的大于該數(shù)據(jù),然后用遞歸的方法對(duì)兩邊的數(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()
- python快速排序代碼實(shí)例
- Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之快速排序詳解
- Python實(shí)現(xiàn)快速排序算法及去重的快速排序的簡(jiǎn)單示例
- Python實(shí)現(xiàn)快速排序和插入排序算法及自定義排序的示例
- 快速排序的四種python實(shí)現(xiàn)(推薦)
- python實(shí)現(xiàn)快速排序的示例(二分法思想)
- javascript與Python快速排序?qū)嵗龑?duì)比
- python 二分查找和快速排序?qū)嵗斀?/a>
- Python編程二分法實(shí)現(xiàn)冒泡算法+快速排序代碼示例
- Python實(shí)現(xiàn)的插入排序,冒泡排序,快速排序,選擇排序算法示例
- Python一行代碼實(shí)現(xiàn)快速排序的方法
- Python實(shí)現(xiàn)快速排序的方法詳解
相關(guān)文章
Python實(shí)現(xiàn)在Excel文件中寫入圖表
這篇文章主要為大家介紹了如何利用Python語言實(shí)現(xiàn)在Excel文件中寫入一個(gè)比較簡(jiǎn)單的圖表,文中的實(shí)現(xiàn)方法講解詳細(xì),快動(dòng)手嘗試一下吧2022-05-05python之yield表達(dá)式學(xué)習(xí)
這篇文章主要介紹了python之yield表達(dá)式學(xué)習(xí),python中有一個(gè)略微奇怪的表達(dá)式叫yield expression,本文就來探究一下這是個(gè)什么東西,需要的朋友可以參考下2014-09-09教你用一行Python代碼實(shí)現(xiàn)GUI圖形界面
這篇文章主要介紹了教你用一行Python代碼實(shí)現(xiàn)GUI圖形界面,通過使用PySimpleGUI的popup_get_folder()方法,一行代碼就能實(shí)現(xiàn)選擇文件夾的操作,本文結(jié)合示例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下2023-01-01Softmax函數(shù)原理及Python實(shí)現(xiàn)過程解析
這篇文章主要介紹了Softmax函數(shù)原理及Python實(shí)現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-05-05