欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間:2016年07月02日 10:29:41   作者:cangmean  
快速排序算法來源于分治法的思想策略,這里我們將來為大家簡(jiǎn)單解析一下快速排序的算法思想及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()

相關(guān)文章

  • 基于python3的socket聊天編程

    基于python3的socket聊天編程

    這篇文章主要為大家詳細(xì)介紹了基于python3的socket聊天編程,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-02-02
  • python語言中有算法嗎

    python語言中有算法嗎

    在本篇文章里小編給大家整理的是一篇關(guān)于python里算法的相關(guān)知識(shí)點(diǎn)內(nèi)容,有興趣的朋友們可以學(xué)習(xí)下。
    2020-06-06
  • Python通過OpenPyXL處理Excel的完整教程

    Python通過OpenPyXL處理Excel的完整教程

    OpenPyXL是一個(gè)強(qiáng)大的Python庫,用于處理Excel文件,允許讀取、編輯和創(chuàng)建Excel工作簿和工作表,本文將詳細(xì)介紹OpenPyXL的各種功能,希望對(duì)大家有所幫助
    2023-11-11
  • Python隨機(jī)值生成的常用方法總結(jié)

    Python隨機(jī)值生成的常用方法總結(jié)

    這篇文章主要為大家詳細(xì)介紹了Python中隨機(jī)值生成的一些常用方法,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)Python有一定幫助,需要的可以了解一下
    2022-10-10
  • Python實(shí)現(xiàn)在Excel文件中寫入圖表

    Python實(shí)現(xiàn)在Excel文件中寫入圖表

    這篇文章主要為大家介紹了如何利用Python語言實(shí)現(xiàn)在Excel文件中寫入一個(gè)比較簡(jiǎn)單的圖表,文中的實(shí)現(xiàn)方法講解詳細(xì),快動(dòng)手嘗試一下吧
    2022-05-05
  • python之yield表達(dá)式學(xué)習(xí)

    python之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圖形界面

    這篇文章主要介紹了教你用一行Python代碼實(shí)現(xiàn)GUI圖形界面,通過使用PySimpleGUI的popup_get_folder()方法,一行代碼就能實(shí)現(xiàn)選擇文件夾的操作,本文結(jié)合示例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下
    2023-01-01
  • python實(shí)現(xiàn)圖片中文字分割效果

    python實(shí)現(xiàn)圖片中文字分割效果

    這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)圖片中文字分割效果,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-07-07
  • pandas中pd.groupby()的用法詳解

    pandas中pd.groupby()的用法詳解

    本文主要介紹了pandas中pd.groupby()的用法詳解,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧<BR>
    2022-06-06
  • Softmax函數(shù)原理及Python實(shí)現(xiàn)過程解析

    Softmax函數(shù)原理及Python實(shí)現(xiàn)過程解析

    這篇文章主要介紹了Softmax函數(shù)原理及Python實(shí)現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-05-05

最新評(píng)論