不想當(dāng)將軍的士兵，不是好士兵。不了解算法的程序員也不是好的程序員豪直。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? by? ?尼古拉斯---彥祖
首先給上一張金蜀，實(shí)驗(yàn)環(huán)境下，各個(gè)排序算法的時(shí)間效率對(duì)比吃靠。
一? 簡(jiǎn)單概念
????算法頻率度即一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度硫眨。記為T(n)。
????時(shí)間復(fù)雜度以大O表示法 常見的有四種：
????O(1)巢块、O(n)礁阁、O(logn)巧号、O(n2)分別可以稱為常數(shù)階、線性階姥闭、對(duì)數(shù)階和平方階
二? 快速排序
? ? 取某一位（一般是首位）作為flag. 分治法排序丹鸿。
? ? 每一趟的下標(biāo)都是前后同時(shí)進(jìn)行，比f(wàn)lag小的放到左邊棚品，比f(wàn)lag大的放到右邊卜高。結(jié)束條件為前后下標(biāo)重合。
? ? 一趟排序可以得到以flag為界限的 兩個(gè)集合南片。依次遞歸掺涛，結(jié)束條件為不可再分。
? ? 換句話說：? 現(xiàn)在要給一萬(wàn)個(gè)排成一列的士兵 按照大小個(gè)排隊(duì)疼进。??
? ??首先取第一個(gè)士兵的高度為標(biāo)準(zhǔn)薪缆，稱其為flag，一趟算法的期望運(yùn)行結(jié)果伞广，就是所有比這個(gè)士兵低的人在這個(gè)士兵前面拣帽，所有比這個(gè)士兵高的人都在他后面。
? ??那么嚼锄，怎么實(shí)現(xiàn)這個(gè)效果呢减拭？？?
? ??找兩個(gè)將軍來区丑，一個(gè)站在列首拧粪，一個(gè)站在列尾。
? ??列尾的將軍沧侥，站在第10000個(gè)士兵這個(gè)位置可霎，看看他比f(wàn)lag高，還是低宴杀，如果高那么不管癣朗，列尾的將軍向前走一步。 走到第9999個(gè)士兵處旺罢，繼續(xù)比較旷余，直到走到一個(gè)比f(wàn)lag低的士兵位置。比如第9996個(gè)士兵比第一個(gè)士兵低扁达，那么讓 9996和 1 互換位置正卧。? ? ?此時(shí)的flag的位置變成了9996
? ??現(xiàn)在列尾的將軍先休息，讓列首的將軍從2這個(gè)位置向前走罩驻，走到第一個(gè)比f(wàn)lag高的位置穗酥，比如是第15個(gè)。 那就讓15 和9996換位置惠遏，并且更新flag為15砾跃。此時(shí)列首將軍休息，列尾的將軍繼續(xù)节吮。? 以此類推抽高。
直到列首和列尾的將軍碰了面，那么本趟快排結(jié)束透绩。?
比如此時(shí)的位置是6666個(gè)士兵處翘骂。根據(jù)上面的過程推論，此時(shí)flag也一定在6666處帚豪。兩個(gè)將軍不碰面也正是快速排序的特點(diǎn)
那么本趟排序完成碳竟。 整個(gè)隊(duì)列被6666分成了兩個(gè)A B隊(duì)列，前面的一定比士兵flag矮小狸臣，后面的一定比f(wàn)lag高大莹桅。
然后再請(qǐng)四位將軍過來對(duì)，這AB兩個(gè)隊(duì)列進(jìn)行上述操作烛亦。直到隊(duì)列變成2個(gè)人（不可再分割）诈泼。以此類推
三? ?選擇排序
? ? 與冒泡排序類似，但是區(qū)別在于煤禽，新建局部變量?jī)?chǔ)存本趟的目標(biāo)值铐达。
????每次只比較而不交換，直到一趟排序結(jié)束之后檬果。才進(jìn)行轉(zhuǎn)換瓮孙，提升了部分效率
? ? 還是那一列一萬(wàn)個(gè)士兵的隊(duì)伍。?
? ??一個(gè)將軍拿著一個(gè)筆記本选脊，
????從第一個(gè)開始問衷畦，你身高多少？ “1.60”? ?看來你是最低的知牌，于是他將第一個(gè)士兵的名字寫到了筆記本上祈争。
? ? 第二個(gè) “你身高多高”? ? “185”? ? ?不管，下一個(gè)
? ? 第三個(gè)問“你身高多少”“158”? ? ? ? 將軍角寸，劃掉了上一個(gè)名字菩混，記上了最新的這個(gè)人的名字。
? ? 直到問完整個(gè)隊(duì)伍扁藕。? 將軍看到筆記本上寫著? 最低的那個(gè)人的名字???“提利昂-蘭尼斯特”? 你站到第一個(gè)位置沮峡。
? ? 這是一趟排序結(jié)束。
? ?? 接下來亿柑，將軍從第二個(gè)位置開始問邢疙。（第一個(gè)已經(jīng)確定了）以此類推，直到最后一個(gè)。
? ??
四? 插入排序
? ? 4.1 簡(jiǎn)單插入排序
? ? ? ? 簡(jiǎn)單插入排序的核心思想是認(rèn)為疟游，所有的事情都是基于一個(gè)已有序的序列進(jìn)行的呼畸。
? ? ? ? 比如下標(biāo)從第一個(gè)元素開始，認(rèn)為? 第一個(gè)元素本身是一個(gè)有序序列（這是對(duì)的颁虐，因?yàn)橹挥幸粋€(gè)元素蛮原。）
? ? ? ? 那么下標(biāo)轉(zhuǎn)移到第二個(gè)元素，將第二個(gè)元素 去與左邊的有序序列（第一個(gè)元素）比較另绩，插入到合適的位置儒陨。
? ? ? ? 下標(biāo)繼續(xù)，邏輯依然如此笋籽，直到下標(biāo)行走到最后的位置蹦漠。整個(gè)序列都有序了。
? ? ? ? 他的算法邏輯是這樣的车海， 請(qǐng)來兩位將軍A,B笛园，?
? ??????首先是告訴A將軍，你首先管理的是無(wú)序的9999個(gè)士兵隊(duì)列容劳。你只管把他們一個(gè)個(gè)都推出去給B將軍就行了喘沿。 你可以認(rèn)為B將軍那里的永遠(yuǎn)是一個(gè)有序隊(duì)列。
? ? ? ? 然后告訴B將軍竭贩，你手下永遠(yuǎn)是有序的隊(duì)列⊙劣。現(xiàn)在你手下有一個(gè)人，當(dāng)然是有序的留量，接下來再來新人窄赋，都讓他們和之前的有序隊(duì)列比較，找到他們合適的位置。??
? ??????第二個(gè)人來的時(shí)候，和原先的第一個(gè)人比較恰力，如果比之前的人高，那么站在他后面错敢，如果比他矮站在他前面?
? ? ? ? 第三個(gè)人來的時(shí)候，從第一個(gè)位置開始找缕粹，找到第一個(gè)比他高的人稚茅，插入進(jìn)隊(duì)列。后面的士兵平斩，都后退一步亚享。
? ? ? ? 以此類推，直到B將軍手下 所有的士兵都到了A將軍手下為止绘面。
? ? ? ? 所以欺税，你可以簡(jiǎn)單的理解它為插隊(duì)排序
? ? 4.2? 希爾排序
????????希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
? ? ? ? ? ? 1? ? ?插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)侈沪，效率高，即可以達(dá)到線性排序的效率晚凿。
? ? ? ? ? ? 2? ? ?但插入排序一般來說是低效的亭罪，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。
? ? ? ? 希爾排序的意思是現(xiàn)將正序列變成一個(gè)基本有序的序列晃虫，然后再進(jìn)行簡(jiǎn)單插入排序皆撩。
? ? ? ? 那么如何將一個(gè)序列變成基本有序的序列呢扣墩。 現(xiàn)在有一個(gè)100元素的序列
? ? ? ? 第一趟將其拆成50個(gè)有序序列哲银。? 對(duì)這50個(gè)有序序列進(jìn)行簡(jiǎn)單插入排序
? ? ? ? 第二趟將其拆分為25個(gè)，每個(gè)4元素的序列呻惕，對(duì)這25個(gè)有序序列進(jìn)行簡(jiǎn)單插入排序荆责。
? ? ? ? 知道最后將其拆分為一個(gè) 100元素序列為止。
? ? ? ? 希爾排序是在簡(jiǎn)單插入排序的基礎(chǔ)上演進(jìn)來的亚脆，理論的東西做院，不多贅述”舫郑可以這樣理解键耕。
? ? ? ? 希爾排序的基本思想還是 A ,B兩個(gè)將軍 分別管理一個(gè)有序隊(duì)列和一個(gè)無(wú)序隊(duì)列。
? ??????但是差別在于柑营，如果整個(gè)隊(duì)列是接近完全無(wú)序的情況下屈雄，每次新兵進(jìn)去 B將軍的有序隊(duì)列，都要進(jìn)行一次整體的位移官套。也就是比較的次數(shù)為L(zhǎng)OG（n2）酒奶，而且在排序后期，這里的N基本都無(wú)限接近一萬(wàn)奶赔，這是一個(gè)很大的性能消耗惋嚎。
? ??????而希爾排序，則是先取增量為10站刑，所有的下標(biāo)向10取余
? ??????先讓尾號(hào)為0的士兵向前一步另伍， 這樣就出現(xiàn)了1000名，位置尾號(hào)為0的士兵绞旅。 先對(duì)這1000名士兵進(jìn)行插入排序摆尝，即便出現(xiàn)插入操作而導(dǎo)致的整體位移，移動(dòng)成本也比一萬(wàn)名士兵移動(dòng)好多了玻靡。? 這樣已經(jīng)有十分之一的士兵有序了
? ??????然后再讓尾號(hào)為1的士兵向前一步...结榄，尾號(hào)為2的士兵向前一步。? 以此類推囤捻。整體一萬(wàn)個(gè)士兵也就基本有序了臼朗。
這樣我們一趟排序完成，此時(shí)我們的增量為10. 接下來我們降低增量為5，
所有士兵的下標(biāo)向5取余视哑。? 我們還是按照剛才的辦法绣否，每次對(duì)五分之一的士兵，進(jìn)行插入排序挡毅。
雖然兩千名士兵整體位移的成本依然很高蒜撮，但是畢竟比一萬(wàn)小了很多，況且之前已經(jīng)有過一次十分之一規(guī)模的插入排序了跪呈。所以發(fā)生插入操作的概率不大段磨。
第二趟排序結(jié)束。? 繼續(xù)縮小增量耗绿。直到為0.苹支。。误阻。债蜜。。? ?
over (真特么的麻煩究反。寻定。。)
五? 冒泡排序
? ? 相對(duì)原始的方法精耐，對(duì)比每一個(gè)元素狼速，每趟選出一個(gè)最大值出來。時(shí)間復(fù)雜度為O（n2）
這個(gè)算法最簡(jiǎn)單黍氮，也最好理解唐含，和選擇排序極為類似。只不過區(qū)別不是將軍帶著筆記本去挨個(gè)統(tǒng)計(jì)個(gè)頭了沫浆。
而是將軍領(lǐng)著當(dāng)前等待排序的士兵本人捷枯，與下一個(gè)士兵比個(gè)頭。? 最后跟著將軍走到隊(duì)列尾部的专执，一定是個(gè)頭最大的淮捆。
? ? 算法實(shí)現(xiàn)：
附上：源碼下載地址：
http://note.youdao.com/noteshare?id=2afb3adfc83d0684ff79deb931c079bb&sub=97381DA724BC4B3DA8EE2D5175176593
