iOS算法篇(一)快速排序算法

快速排序是當(dāng)遇到較大數(shù)據(jù)時,排序快,高效的方法(公司面試時,基本上會被問到...)該方法的基本思想是:

1.先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)音婶。

2.分區(qū)過程货抄,將比這個數(shù)大的數(shù)全放到它的右邊,小于或等于它的數(shù)全放到它的左邊。3.再對左右區(qū)間重復(fù)第二步塌计,直到各區(qū)間只有一個數(shù)栗恩。

? ? ? 簡單地理解就是,找一個基準(zhǔn)數(shù)(待排序的任意數(shù),一般都是選定首元素),把比小于等于基準(zhǔn)數(shù)的元素放到基準(zhǔn)數(shù)的左邊,把大于基準(zhǔn)數(shù)的元素放在基準(zhǔn)數(shù)的右邊.排完之后,在把基準(zhǔn)數(shù)的左邊和右邊各看成一個整體,? 左邊:繼續(xù)選擇基準(zhǔn)數(shù)把小于等于基準(zhǔn)數(shù)的元素放到基準(zhǔn)數(shù)的左邊,把大于基準(zhǔn)數(shù)的元素放在基準(zhǔn)數(shù)的右邊,右邊也是一樣..直到各區(qū)間只有一個數(shù)位置.

? ? ? ?快速排序之所比較快男窟,因為相比冒泡排序势决,每次交換是跳躍式的步淹。每次排序的時候設(shè)置一個基準(zhǔn)點(diǎn)从隆,將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊,將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的右邊缭裆。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換键闺,交換的距離就大的多了。因此總的比較和交換次數(shù)就少了澈驼,速度自然就提高了辛燥。當(dāng)然在最壞的情況下,仍可能是相鄰的兩個數(shù)進(jìn)行了交換。因此快速排序的最差時間復(fù)雜度和冒泡排序是一樣的都是O(N2)挎塌,它的平均時間復(fù)雜度為O(NlogN)畅铭。

圖片詮釋上面的思想技術(shù)分享 <書面語解釋>

1、算法思想? ??

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

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

(2)快速排序的基本思想? ?  設(shè)當(dāng)前待排序的無序區(qū)為R[low..high]阳惹,利用分治法可將快速排序的基本思想描述為:①分解:? ?  在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止潮。

②求解:通過遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序钞楼。

③組合:因為當(dāng)"求解"步驟中的兩個遞歸調(diào)用結(jié)束時喇闸,其左、右兩個子區(qū)間已有序询件。對快速排序而言燃乍,"組合"步驟無須做什么,可看作是空操作宛琅。代碼實現(xiàn): #import#define COUNT 100? ? ? //定義數(shù)組元素的個數(shù)

int a[COUNT], n; //定義全局變量刻蟹,這兩個變量需要在子函數(shù)中使用

//給快速排序方法連個參數(shù),開始位置(左),和結(jié)束位置(右)

void quicksort(int left, int right){

int i, j, t, temp;

if(left > right)? //開始位置坐標(biāo)大于結(jié)束位置坐標(biāo)時,直接return,結(jié)束下面的操作

return;

temp = a[left];? //temp中存的就是基準(zhǔn)數(shù)(基準(zhǔn)數(shù)是隨機(jī)的,但一般都是第一個元素)

i = left;

j = right;

while(i != j)

{

//順序很重要,要先從右邊開始找

while(a[j] >= temp && i

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末夯秃,一起剝皮案震驚了整個濱河市座咆,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌仓洼,老刑警劉巖介陶,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異色建,居然都是意外死亡哺呜,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進(jìn)店門箕戳,熙熙樓的掌柜王于貴愁眉苦臉地迎上來某残,“玉大人国撵,你說我怎么就攤上這事〔J” “怎么了介牙?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長澳厢。 經(jīng)常有香客問我环础,道長,這世上最難降的妖魔是什么剩拢? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任线得,我火速辦了婚禮,結(jié)果婚禮上徐伐,老公的妹妹穿的比我還像新娘贯钩。我一直安慰自己,他們只是感情好办素,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布角雷。 她就那樣靜靜地躺著,像睡著了一般性穿。 火紅的嫁衣襯著肌膚如雪谓罗。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天季二,我揣著相機(jī)與錄音檩咱,去河邊找鬼。 笑死胯舷,一個胖子當(dāng)著我的面吹牛刻蚯,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播桑嘶,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼炊汹,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了逃顶?” 一聲冷哼從身側(cè)響起讨便,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎以政,沒想到半個月后霸褒,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡盈蛮,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年废菱,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡殊轴,死狀恐怖衰倦,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情旁理,我是刑警寧澤樊零,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站孽文,受9級特大地震影響淹接,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜叛溢,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望劲适。 院中可真熱鬧楷掉,春花似錦、人聲如沸霞势。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽愕贡。三九已至草雕,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間固以,已是汗流浹背墩虹。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留憨琳,地道東北人诫钓。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像篙螟,于是被迫代替她去往敵國和親菌湃。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 一遍略、直接插入排序 直接插入排序(Insertion Sort)的基本思想是:每次將一個待排序的元素記錄惧所,按其關(guān)鍵字...
    kevin16929閱讀 562評論 0 0
  • quicksort可以說是應(yīng)用最廣泛的排序算法之一,它的基本思想是分治法绪杏,選擇一個pivot(中軸點(diǎn))下愈,將小于pi...
    黎景陽閱讀 449評論 0 1
  • 概述 排序有內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序蕾久,而外部排序是因排序的數(shù)據(jù)很大驰唬,一次不能容納全部...
    蟻前閱讀 5,191評論 0 52
  • 概述:排序有內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序,而外部排序是因排序的數(shù)據(jù)很大叫编,一次不能容納全部...
    每天刷兩次牙閱讀 3,733評論 0 15
  • 時間:2017年9月27日 地點(diǎn):豆丁公寓 作者:阮博杰 發(fā)現(xiàn):擁有孩子般的干凈 糾結(jié):但是我得做大男人哪 幸運(yùn):...
    阮博杰閱讀 154評論 0 1