//聯(lián)系人:石虎?QQ:1224614774?昵稱:嗡嘛呢叭咪哄
?????????? QQ群:807236138 ?群稱:iOS 技術(shù)交流學(xué)習(xí)群
排序圖表:
一词身、插入排序
每次將一個待排序的數(shù)據(jù)练湿，跟前面已經(jīng)有序的序列的數(shù)字一一比較找到自己合適的位置，插入到序列中涌庭，直到全部數(shù)據(jù)插入完成芥被。
二、希爾排序
先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進(jìn)行直接插入排序坐榆，然后依次縮減增量再進(jìn)行排序拴魄，待整個序列中的元素基本有序（增量足夠小）時席镀，再對全體元素進(jìn)行一次直接插入排序匹中。由于希爾排序是對相隔若干距離的數(shù)據(jù)進(jìn)行直接插入排序，因此可以形象的稱希爾排序為“跳著插”
三愉昆、冒泡排序
? 通過交換使相鄰的兩個數(shù)變成小數(shù)在前大數(shù)在后职员，這樣每次遍歷后，最大的數(shù)就“沉”到最后面了跛溉。重復(fù)N次即可以使數(shù)組有序。
冒泡排序改進(jìn)1：在某次遍歷中如果沒有數(shù)據(jù)交換扮授，說明整個數(shù)組已經(jīng)有序芳室。因此通過設(shè)置標(biāo)志位來記錄此次遍歷有無數(shù)據(jù)交換就可以判斷是否要繼續(xù)循環(huán)。
冒泡排序改進(jìn)2：記錄某次遍歷時最后發(fā)生數(shù)據(jù)交換的位置刹勃，這個位置之后的數(shù)據(jù)顯然已經(jīng)有序了堪侯。因此通過記錄最后發(fā)生數(shù)據(jù)交換的位置就可以確定下次循環(huán)的范圍了。
四荔仁、快速排序
? “挖坑填數(shù)+分治法”伍宦，首先令i =L; j = R; 將a[i]挖出形成第一個坑，稱a[i]為基準(zhǔn)數(shù)乏梁。然后j--由后向前找比基準(zhǔn)數(shù)小的數(shù)次洼，找到后挖出此數(shù)填入前一個坑a[i]中，再i++由前向后找比基準(zhǔn)數(shù)大的數(shù)遇骑，找到后也挖出此數(shù)填到前一個坑a[j]中卖毁。
重復(fù)進(jìn)行這種“挖坑填數(shù)”直到i==j。再將基準(zhǔn)數(shù)填入a[i]中落萎，這樣i之前的數(shù)都比基準(zhǔn)數(shù)小亥啦，i之后的數(shù)都比基準(zhǔn)數(shù)大炭剪。因此將數(shù)組分成二部分再分別重復(fù)上述步驟就完成了排序。
五翔脱、選擇排序
?? 數(shù)組分成有序區(qū)和無序區(qū)奴拦，初始時整個數(shù)組都是無序區(qū)，然后每次從無序區(qū)選一個最小的元素直接放到有序區(qū)的最后届吁，直到整個數(shù)組變有序區(qū)眷细。
六、堆排序
? ? ?圖:
?? 堆的插入就是——每次插入都是將新數(shù)據(jù)放在數(shù)組最后抑堡，而從這個新數(shù)據(jù)的父結(jié)點到根結(jié)點必定是一個有序的數(shù)列按摘，因此只要將這個新數(shù)據(jù)插入到這個有序數(shù)列中即可。
?? 堆的刪除就是——堆的刪除就是將最后一個數(shù)據(jù)的值賦給根結(jié)點濒旦，然后再從根結(jié)點開始進(jìn)行一次從上向下的調(diào)整株旷。調(diào)整時先在左右兒子結(jié)點中找最小的，如果父結(jié)點比這個最小的子結(jié)點還小說明不需要調(diào)整了尔邓，反之將父結(jié)點和它交換后再考慮后面的結(jié)點晾剖。相當(dāng)于從根結(jié)點開始將一個數(shù)據(jù)在有序數(shù)列中進(jìn)行“下沉”。
?? 因此梯嗽，堆的插入和刪除非常類似直接插入排序齿尽，只不是在二叉樹上進(jìn)行插入過程。所以可以將堆排序形容為“樹上插”
七灯节、歸并排序
?? 歸并排序主要分為兩步：分?jǐn)?shù)列（divide）循头，每次把數(shù)列一分為二，然后分到只有兩個元素的小數(shù)列炎疆；合數(shù)列（Merge）卡骂，合并兩個已經(jīng)內(nèi)部有序的子序列，直至所有數(shù)字有序形入。用遞歸可以實現(xiàn)全跨。
八、基數(shù)排序（桶排序）
? ? 基數(shù)排序亿遂，第一步根據(jù)數(shù)字的個位分配到每個桶里浓若，在桶內(nèi)部排序，然后將數(shù)字再輸出（串起來）蛇数；然后根據(jù)十位分桶挪钓，繼續(xù)排序，再串起來苞慢。直至所有位被比較完诵原，所有數(shù)字已經(jīng)有序。
