幾種排序算法總結(jié)
排序的定義
對(duì)一序列對(duì)象根據(jù)某個(gè)關(guān)鍵字進(jìn)行排序弹囚。
這里簡(jiǎn)單總結(jié)下各種排序的特點(diǎn)：
畫個(gè)表
穩(wěn)定性：若a=b恭陡，排序后相對(duì)位置不變即穩(wěn)定对雪，否則為不穩(wěn)定
時(shí)間復(fù)雜度：一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間
空間復(fù)雜度：一個(gè)算法執(zhí)行所耗費(fèi)的內(nèi)存
排序方式：內(nèi)排序—在內(nèi)存中完成排序乔夯，外排序—在硬盤中完成排序
| 平均時(shí)間復(fù)雜度 | 最好情況 | 最壞情況 | 空間復(fù)雜度 | 排序方式 | 穩(wěn)定性 | |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | In-place | 穩(wěn)定 |
| 選擇排序 | O(n2) | O(n2) | O(n2) | O(1) | In-place | 不穩(wěn)定 |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) | In-place | 穩(wěn)定 |
| 希爾排序 | O(n log n) | O(n log2n) | O(n log2n) | O(1) | In-place | 不穩(wěn)定 |
| 歸并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | Out-place | 穩(wěn)定 |
| 快速排序 | O(n log n) | O(n log n) | O(n2) | O(log n) | In-place | 不穩(wěn)定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | In-place | 不穩(wěn)定 |
| 計(jì)數(shù)排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | Out-place | 穩(wěn)定 |
| 桶排序 | O(n + k) | O(n + k) | O(n2) | O(n + k) | Out-place | 穩(wěn)定 |
| 基數(shù)排序 | O(n * k) | O(n * k) | O(n * k) | O(n + k) | Out-place | 穩(wěn)定 |
冒泡排序
從最簡(jiǎn)單的冒泡排序開(kāi)始總結(jié)馏鹤，差不多是每個(gè)人接觸的第一個(gè)排序算法征椒。它重復(fù)地在排序的數(shù)列上跑，一次比較兩個(gè)元素湃累，如果順序不對(duì)就把他們兩個(gè)互相交換勃救，每次從頭開(kāi)始，每次完成一個(gè)脱茉。
選擇排序
每次選擇序列中最小的第一個(gè)放到未排序序列的起始位置剪芥，這個(gè)元素就是已排好序列了，然后繼續(xù)在未排序的序列中找最小值琴许，放到已排序序列的末尾税肪，以此類推。
插入排序
插入排序像玩撲克牌一樣排序，對(duì)于一個(gè)未排序的序列益兄，一個(gè)一個(gè)往前掃描锻梳，當(dāng)它大于前面的數(shù)并且小于后面的數(shù)時(shí)，將這個(gè)數(shù)插入到這個(gè)位置净捅，此時(shí)這一段數(shù)列就是排序后的序列了疑枯，再將未排序序列中的元素從后往前和排序完成的序列挨個(gè)比較，以此類推蛔六。
未完待續(xù)
