這是我以前寫(xiě)的博客肴焊，我遷移過(guò)來(lái)的燎孟，時(shí)間寫(xiě)的有點(diǎn)久遠(yuǎn)
1.冒泡排序和選擇排序
為什么把冒泡排序和選擇排序放在一塊兒呢臭脓？因?yàn)槲野l(fā)現(xiàn)他們兩個(gè)有點(diǎn)像。
冒泡排序是不停的把最大的元素?fù)Q到數(shù)組的最右端吗浩。
而選擇排序是把最小的元素?fù)Q到最左端建芙。
看到這兒，你是不是覺(jué)得冒泡和選擇好像沒(méi)啥區(qū)別啊懂扼，把最大換成最小就成了一種新的算法禁荸？那我也來(lái)一個(gè)？
其實(shí)阀湿，無(wú)論換最大還是最小屡限，都無(wú)關(guān)緊要，就算冒泡變成換最小的元素?fù)Q到數(shù)組的最左端炕倘，那它也叫冒泡排序的钧大。
冒泡排序的描述：它重復(fù)地走訪(fǎng)過(guò)要排序的數(shù)列，一次比較兩個(gè)元素罩旋，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)啊央。走訪(fǎng)數(shù)列的工作是重復(fù)地進(jìn)行直到不需要交換眶诈，也就是說(shuō)該數(shù)列已經(jīng)排序完成。
選擇排序的描述：每一趟從待排序的數(shù)據(jù)元素中選出最泄霞ⅰ（或最大）的一個(gè)元素逝撬，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完乓土。
為了便于描述二者之間的區(qū)別宪潮，我們把冒泡和排序都換成是把最大元素?fù)Q到最右端。
他們的最大區(qū)別在于
冒泡排序不停比較兩個(gè)相鄰的元素趣苏，并不斷交換較大的元素狡相，直到數(shù)組尾。
選擇排序開(kāi)始只比較不交換食磕，直到數(shù)組尾才進(jìn)行一次交換尽棕。
在這里，你可以認(rèn)為選擇排序是冒泡排序的優(yōu)化彬伦，因?yàn)檫x擇排序多數(shù)時(shí)候減少了交換的次數(shù)滔悉，卻實(shí)現(xiàn)了相同的效果。
難道冒泡排序多做的那些交換就全是無(wú)用功嗎单绑？仔細(xì)想想回官，當(dāng)然不是這樣！
仔細(xì)看看冒泡排序是怎么說(shuō)的搂橙，“走訪(fǎng)數(shù)列的工作是重復(fù)地進(jìn)行直到不需要交換”歉提，這個(gè)很重要，假如我們加入一個(gè)變量份氧，來(lái)記錄交換次數(shù)，當(dāng)某趟遍歷交換次數(shù)為零的時(shí)候弯屈，說(shuō)明數(shù)組已經(jīng)排序好了蜗帜，那就可以結(jié)束排序了！
比如“1,2,3,4,5,6,7,8,9”资厉，對(duì)于這樣一個(gè)數(shù)組厅缺，冒泡排序只需要進(jìn)行一次遍歷就ok了，所以對(duì)于基本有序的數(shù)組宴偿，冒泡可以做到O(n)的復(fù)雜度湘捎。
但是選擇排序做不到這一點(diǎn)，一個(gè)已經(jīng)有序的數(shù)組和隨機(jī)排列的數(shù)組將花差不多的時(shí)間（稍微會(huì)少點(diǎn)窄刘，因?yàn)橛行驍?shù)組不需要交換窥妇，只需要比較）。
在這里娩践，我們發(fā)現(xiàn)活翩，選擇排序并沒(méi)有利用數(shù)組的初始輸入狀態(tài)烹骨，而冒泡排序利用了。這是冒泡的優(yōu)勢(shì)材泄，在這里沮焕，你可能會(huì)想，冒泡是如何利用初始狀態(tài)的呢拉宗？當(dāng)然就是在一次又一次相鄰元素的比較上嘛峦树。
最后，由于選擇排序會(huì)交換不相鄰元素旦事，比如直接把a(bǔ)[0]和a[8]交換位置魁巩，導(dǎo)致了選擇排序的不穩(wěn)定。而冒泡只會(huì)交換相鄰元素族檬，所以冒泡是穩(wěn)定的歪赢，我們當(dāng)然不會(huì)蠢到a[0]=1,a[1]=1的時(shí)候交換他們的位置是吧。
待會(huì)兒我們會(huì)分析插入排序和希爾排序单料，這兩個(gè)排序的穩(wěn)定性的因果分析也和是否交換不相鄰元素有關(guān)埋凯。
先到這兒，明天再寫(xiě)扫尖。白对。
=====================我是分割線(xiàn)8.18===============================
上次說(shuō)好了明天再寫(xiě)，結(jié)果那天晚上就被人分手了换怖，真是悲痛萬(wàn)分甩恼。話(huà)說(shuō)愛(ài)情從未影響過(guò)學(xué)習(xí)，影響學(xué)習(xí)的是暗戀和失戀沉颂，這真是一個(gè)真理啊条摸。
學(xué)習(xí)還是要繼續(xù)，現(xiàn)在開(kāi)始吧铸屉。
=====================我也是分割線(xiàn)=================================
2.插入排序和希爾排序
插入排序：插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中钉蒲，并且要求插入后此數(shù)據(jù)序列仍然有序。
比如序列1235678彻坛，現(xiàn)在又來(lái)了一個(gè)4顷啼，那我們就要把它插到3和5之間。舉個(gè)例子昌屉，你撲克的時(shí)候一般手上的牌都是排好序的钙蒙，你又起了一張牌，肯定會(huì)把它插入到合適的位置（也就是不會(huì)破壞有序的位置）间驮。
不過(guò)這里有點(diǎn)小小的區(qū)別躬厌，人眼可以一瞬間看出牌應(yīng)該插在哪里，但是計(jì)算機(jī)做不到竞帽，計(jì)算機(jī)得一個(gè)個(gè)比較烤咧。我們?nèi)绻氚?插到1235678的序列中偏陪，得按順序和8，7煮嫌，6笛谦，5，3進(jìn)行比較昌阿，然后發(fā)現(xiàn)了3比4小饥脑，所以把4插到3后面。
正因?yàn)檫@樣懦冰，插入排序的時(shí)間復(fù)雜度是O(n^2)灶轰，不過(guò)假如數(shù)組基本有序，你可以發(fā)現(xiàn)刷钢，插入排序的時(shí)間復(fù)雜度將下降很多笋颤。對(duì)于一個(gè)有序數(shù)組，插入排序的時(shí)間復(fù)雜度是O（n）内地。
也正因?yàn)檫@樣伴澄，插入排序?qū)τ谛?shù)組的表現(xiàn)是不錯(cuò)的，因?yàn)樾?shù)組基本有序的可能性是比較大的阱缓，即便是無(wú)序非凌，因?yàn)閿?shù)組小，時(shí)間復(fù)雜度也不會(huì)很大荆针。
實(shí)踐中表明敞嗡，當(dāng)快速排序遞歸到小數(shù)組的時(shí)候（元素?cái)?shù)目15以下），用插入排序航背，可以使效率增高20%到30%喉悴。（來(lái)源：《算法》）
由于插入排序也是通過(guò)一次又一次的比較來(lái)排序的，并且也不會(huì)交換不相鄰的元素玖媚。所以插入排序是穩(wěn)定的箕肃。
希爾排序：希爾排序是插入排序的改良版，是一種分組插入排序最盅。
所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中進(jìn)行插入排序突雪，然后起惕，取第二個(gè)增量d2
那么到底希爾排序改良在哪兒呢涡贱？
作為一個(gè)分組插入排序，它每次會(huì)比較相距dt的元素惹想，如果順序不合问词，就會(huì)交換它。
這有什么好處呢嘀粱？我們知道激挪，插入排序只會(huì)比較和交換相鄰的元素辰狡，這樣會(huì)很浪費(fèi)，假如某元素正確的位置在序列中間垄分，那它就會(huì)比較很多次宛篇。
現(xiàn)在希爾排序排序提供一個(gè)好的方式，就是先以大距離dt分組進(jìn)行排序薄湿，這樣叫倍，然后不斷減小dt,直到dt為1。
這樣的話(huà)豺瘤，元素在分組排序的時(shí)候吆倦，會(huì)交換遠(yuǎn)距離元素，也能離正確的位置更近坐求，但卻只需要少數(shù)幾次交換蚕泽。
這有點(diǎn)不好理解，我們舉個(gè)例子桥嗤，假如有一個(gè)序列须妻，1，6砸逊，8璧南，4，3师逸，9司倚，0，2篓像，5动知，7。先取分組距離為3员辩，那么1盒粮，4堰酿，0抵蚊，7，是一組搪哪，排好序之后變成0宋税，1摊崭，4，7.一共只需要進(jìn)行四次比較杰赛，可如果我們只比較相鄰元素的話(huà)呢簸，那么就遠(yuǎn)遠(yuǎn)不知四次了。
有人可能會(huì)問(wèn)，這樣排序一次之后根时，真的比初始序列更加有序了嗎瘦赫，所獲得的收益劃得來(lái)嗎？
直觀(guān)的想蛤迎，分組之后确虱，我們把小的排在了大的前面，應(yīng)該就是更接近有序了替裆〔跄龋可能會(huì)有部分分組沒(méi)有那么好的效果，但從總體上看扎唾，就會(huì)是更加有序了召川，應(yīng)該有數(shù)學(xué)證明的，我待會(huì)兒找找胸遇。
我有一個(gè)證明的思路荧呐，就是把初始序列中所有元素離正確位置的距離加起來(lái)，再把一次排序后離正確位置的距離加起來(lái)纸镊，相減倍阐，再和比較次數(shù)進(jìn)行比較。
另外逗威，dt的取值也很關(guān)鍵峰搪，這是影響希爾排序的關(guān)鍵因素，不過(guò)我一般取d1=n/3+1;d2=d1/3+1;d3=d2/3+1;..............
看到這兒凯旭，有沒(méi)有似曾相識(shí)概耻？是的，二分法也是這么做的罐呼，不需要一次就找到那個(gè)元素鞠柄，不斷縮小尋找范圍，直到找到那個(gè)元素嫉柴。
希爾排序當(dāng)然是不穩(wěn)定的厌杜，因?yàn)榻粨Q了不相鄰的元素。
今天就到這兒吧计螺，明天再來(lái)夯尽！
