1.選擇排序：不穩(wěn)定屏镊，時(shí)間復(fù)雜度 O(n^2)
選擇排序的基本思想是對(duì)待排序的記錄序列進(jìn)行n-1遍的處理而芥，第i遍處理是將L[i..n]中最小者與L[i]交換位置膀值。這樣，經(jīng)過i遍處理之后歌逢，前i個(gè)記錄的位置已經(jīng)是正確的了秘案。
2.插入排序：穩(wěn)定潦匈，時(shí)間復(fù)雜度 O(n^2)
插入排序的基本思想是，經(jīng)過i-1遍處理后,L[1..i-1]己排好序赤惊。第i遍處理僅將L[i]插入L[1..i-1]的適當(dāng)位置凰锡，使得L[1..i] 又是排好序的序列。要達(dá)到這個(gè)目的裕膀，我們可以用順序比較的方法魂角。首先比較L[i]和L[i-1]智绸，如果L[i-1]≤ L[i]瞧栗，則L[1..i]已排好序海铆，第i遍處理就結(jié)束了；否則交換L[i]與L[i-1]的位置殴边，繼續(xù)比較L[i-1]和L[i-2]，直到找到某一個(gè)位置j(1≤j≤i-1)锤岸，使得L[j] ≤L[j+1]時(shí)為止是偷。圖1演示了對(duì)4個(gè)元素進(jìn)行插入排序的過程，共需要(a),(b),(c)三次插入馋评。
3.冒泡排序：穩(wěn)定玛瘸，時(shí)間復(fù)雜度 O(n^2)
冒泡排序方法是最簡單的排序方法捧韵。這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”再来，較小的元素比較輕，從而要往上浮搜变。在冒泡排序算法中我們要對(duì)這個(gè)“氣泡”序列處理若干遍挠他。所謂一遍處理篡帕，就是自底向上檢查一遍這個(gè)序列，并時(shí)刻注意兩個(gè)相鄰的元素的順序是否正確镰烧。如果發(fā)現(xiàn)兩個(gè)相鄰元素的順序不對(duì)，即“輕”的元素在下面茉唉，就交換它們的位置。顯然艾凯，處理一遍之后懂傀，“最輕”的元素就浮到了最高位置；處理二遍之后沧竟，“次輕”的元素就浮到了次高位置悟泵。在作第二遍處理時(shí)，由于最高位置上的元素已是“最輕”元素糕非，所以不必檢查球榆。一般地，第i遍處理時(shí)衡招，不必檢查第i高位置以上的元素每强，因?yàn)榻?jīng)過前面i-1遍的處理，它們已正確地排好序浪箭。
4.堆排序：不穩(wěn)定奶栖，時(shí)間復(fù)雜度 O(nlog n)
堆排序是一種樹形選擇排序门坷，在排序過程中，將A[n]看成是完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)默蚌，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來選擇最小的元素敏簿。
5.歸并排序：穩(wěn)定惯裕，時(shí)間復(fù)雜度 O(nlog n)
設(shè)有兩個(gè)有序（升序）序列存儲(chǔ)在同一數(shù)組中相鄰的位置上，不妨設(shè)為A[l..m]蜻势，A[m+1..h]握玛，將它們歸并為一個(gè)有序數(shù)列，并存儲(chǔ)在A[l..h]冕屯。
6.快速排序：不穩(wěn)定安聘，時(shí)間復(fù)雜度 最理想 O(nlogn) 最差時(shí)間O(n^2)
快速排序是對(duì)冒泡排序的一種本質(zhì)改進(jìn)瓢棒。它的基本思想是通過一趟掃描后，使得排序序列的長度能大幅度地減少脯宿。在冒泡排序中连霉，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長度可能只減少1窘面〔票撸快速排序通過一趟掃描，就能確保某個(gè)數(shù)（以它為基準(zhǔn)點(diǎn)吧）的左邊各數(shù)都比它小谍夭，右邊各數(shù)都比它大憨募。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止菜谣。
7.希爾排序：不穩(wěn)定，時(shí)間復(fù)雜度 平均時(shí)間 O(nlogn) 最差時(shí)間O(n^s) 1<s<2
在直接插入排序算法中媳危，每次插入一個(gè)數(shù)，使有序序列只增加1個(gè)節(jié)點(diǎn)鸣皂，并且對(duì)插入下一個(gè)數(shù)沒有提供任何幫助暮蹂。如果比較相隔較遠(yuǎn)距離（稱為 增量）的數(shù)仰泻，使得數(shù)移動(dòng)時(shí)能跨過多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換慎宾。D.L.shell于1959年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想浅悉。算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組术健，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行荞估，在每組中再進(jìn)行排序勘伺。當(dāng)增量減到1時(shí)飞醉，整個(gè)要排序的數(shù)被分成一組，排序完成轴术。
算法及其時(shí)間復(fù)雜度
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門秉宿，熙熙樓的掌柜王于貴愁眉苦臉地迎上來描睦，“玉大人导而，你說我怎么就攤上這事今艺。” “怎么了撵彻？”我有些...
- 文/不壞的土叔 我叫張陵遥巴，是天一觀的道長铲掐。 經(jīng)常有香客問我，道長摆霉，這世上最難降的妖魔是什么奔坟？ 我笑而不...
- 正文 為了忘掉前任，我火速辦了婚禮搭盾，結(jié)果婚禮上咳秉，老公的妹妹穿的比我還像新娘。我一直安慰自己鸯隅，他們只是感情好澜建，可當(dāng)我...
- 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著蝌以，像睡著了一般炕舵。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上跟畅，一...
- 文/蒼蘭香墨 我猛地睜開眼彰导，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了掏父？” 一聲冷哼從身側(cè)響起爵政，我...
- 序言：老撾萬榮一對(duì)情侶失蹤掺出，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年闸拿，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片苛骨。...
- 正文 年R本政府宣布挨约，位于F島的核電站翁锡，受9級(jí)特大地震影響怨绣，放射性物質(zhì)發(fā)生泄漏开镣。R本人自食惡果不足惜质欲，卻給世界環(huán)境...
- 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧皂岔，春花似錦圾笨、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背。 一陣腳步聲響...
- 正文 我出身青樓，卻偏偏與公主長得像涧狮，于是被迫代替她去往敵國和親涉枫。 傳聞我的和親對(duì)象是個(gè)殘疾皇子尼桶，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 呃本缠，本文有點(diǎn)長……還用到一點(diǎn)點(diǎn)概率論知識(shí) 在講隨機(jī)化之前，先說下目前大家所熟識(shí)的快速排序，先上偽代碼： 最壞情況下...
- 排序：將雜亂無章的數(shù)據(jù)租漂，按照一定的方法進(jìn)行排列的過程叫做排序哩治。 排序的分類 排序大的分類可分為內(nèi)排序和外排序业筏，不需...
- 前言 最近打算好好刷刷算法題朽们，然鵝發(fā)現(xiàn)自己對(duì)這個(gè)算法復(fù)雜度的知識(shí)記憶已全部返還給數(shù)據(jù)結(jié)構(gòu)老師了 一拥娄、算法 算法（A...
- [TOC]1播瞳、插入排序1.1直接插入排序（從后向前找到合適位置后插入）1.2 二分法插入排序1.3 希爾排序2、選...
- 堆排序 堆排序時(shí)間復(fù)雜度 堆排序的時(shí)間復(fù)雜度摊沉，主要在初始化堆過程和每次選取最大數(shù)后重新建堆的過程狐史； 初始化建堆過程...
