假設(shè)含有n個(gè)記錄的序列為{r1,r2,......rn}敞葛，其相應(yīng)的關(guān)鍵字分別為{k1,k2,......kn}与涡，需確定1,2......n的一種排列p1,p2......pn驼卖，使其相應(yīng)的關(guān)鍵字滿足kp1<=kp2<=......kpn（非遞減或非遞增）關(guān)系，即使得序列成為一個(gè)按關(guān)鍵字有序的序列{rp1,rp2......rpn}怎囚，這樣的操作就稱為排序恳守。
一井誉、排序的基本概念與分類
排序的依據(jù)是關(guān)鍵字之間的大小關(guān)系整胃，那么，對(duì)同一個(gè)記錄集合奔则，針對(duì)不同的關(guān)鍵字進(jìn)行排序蔽午，可以得到不同序列及老。
1.1排序的穩(wěn)定性
假設(shè)ki=kj（1<=i<=n,1<=j<=n,i不等于j）骄恶，且在排序前的序列中ri領(lǐng)先于rj（即i<j）。如果排序后ri仍領(lǐng)先于rj虐呻，則稱所用的排序方法是穩(wěn)定的寞秃；反之春寿，若可能使得排序后的序列rj領(lǐng)先ri堂淡，則稱所用的排序方法是不穩(wěn)定的。
1.2內(nèi)排序與外排序
內(nèi)排序是在排序整個(gè)過(guò)程中瘾腰，待排序的所有記錄全部被放置在內(nèi)存中。外排序是由于排序的記錄個(gè)數(shù)太多费薄，不能同時(shí)放置在內(nèi)存楞抡，整個(gè)排序過(guò)程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進(jìn)行析藕。這里主要介紹內(nèi)排序。
二先紫、冒泡排序
冒泡排序是一種交換排序筹煮，它的基本思想是：兩兩比較相鄰記錄的關(guān)鍵字败潦，如果反序則交換，直到?jīng)]有反序的記錄為止眼俊。
算法示例：
冒泡算法由雙層循環(huán)實(shí)現(xiàn)疮胖，其中外層循環(huán)用于控制排序輪數(shù)澎灸，一般為要排序的數(shù)組長(zhǎng)度減1次遮晚，因?yàn)樽詈笠淮闻判蛑皇Ｏ乱粋€(gè)數(shù)組元素县遣，不需要對(duì)比萧求，同時(shí)數(shù)組已經(jīng)完成排序了。而內(nèi)層循環(huán)主要用于對(duì)比數(shù)組中每個(gè)臨近元素的大小元旬，以確定是否交換位置匀归，對(duì)比和交換次數(shù)隨排序輪數(shù)減少耗帕。例如仿便，一個(gè)擁有6個(gè)元素的數(shù)組，在排序過(guò)程中每一次循環(huán)的排序過(guò)程和結(jié)果如下圖所示：
三窑业、簡(jiǎn)單選擇排序
簡(jiǎn)單選擇排序法就是通過(guò)n-i次關(guān)鍵字間的比較常柄，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄搀擂，并和第i（1<=i<=n）個(gè)記錄交換之哨颂。
算法示例：
每一趟從待排序的數(shù)據(jù)元素中選出最型铡（或最大）的一個(gè)元素，順序的放在已排好序的數(shù)列的最后腹备，直到全部待排序的數(shù)據(jù)元素排完植酥。排序過(guò)程和結(jié)果如下圖所示：
四友驮、直接插入排序
直接插入排序的基本操作是將一個(gè)記錄插入到已經(jīng)排好序的有序表中卸留，從而得到一個(gè)新的稻据、記錄數(shù)增1的有序表捻悯。
小結(jié)：
直接插入排序的時(shí)間復(fù)雜度和冒泡排序與簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度一樣今缚。同樣的時(shí)間復(fù)雜度姓言，直接插入排序比冒泡和簡(jiǎn)單選擇排序的性能要好一些。
五囱淋、希爾排序（對(duì)直接插入排序的改進(jìn)）
直接插入排序妥衣，它的效率某些時(shí)候是很高的税手，比如需纳，記錄本身就是基本有序的不翩，我們只需要少量的插入操作口蝠，就可以完成整個(gè)記錄集的排序工作，此時(shí)直接插入很高效俱箱。還有就是記錄數(shù)比較少時(shí)狞谱，直接插入的優(yōu)勢(shì)也比較明顯跟衅。但是這兩個(gè)條件本身就過(guò)于苛刻播歼，現(xiàn)實(shí)中記錄少或者基本有序都屬于特殊情況。
所謂的基本有序秘狞，就是小的關(guān)鍵字基本在前面叭莫，大的基本在后面，不大不小的基本在中間烁试，像{2,1,3,6,4,7,5,8,9}這樣可以稱為基本有序了雇初。
跳躍分割策略：將相距某個(gè)“增量”的記錄組成一個(gè)子序列，這樣才能保證在子序列內(nèi)分別進(jìn)行直接插入排序后得到的結(jié)果是基本有序而不是局部有序减响。
六靖诗、堆排序（對(duì)簡(jiǎn)單選擇排序的改進(jìn)）
堆排列就是對(duì)簡(jiǎn)單選擇排序進(jìn)行的一種改進(jìn)郭怪。堆是具有下列性質(zhì)的二叉樹(shù)：每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值刊橘，稱為大頂堆（左圖）鄙才；或者每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值，稱為小頂堆（右圖）促绵。
堆排序就是利用堆進(jìn)行排序的方法攒庵。它的基本思路是，將待排序的的序列構(gòu)造成一個(gè)大頂堆绞愚。此時(shí)叙甸，整個(gè)序列的最大值就是堆頂?shù)母Y(jié)點(diǎn)。將它移走（其實(shí)就是將其與堆數(shù)組的末尾元素交換位衩，此時(shí)末尾元素就是最大值）裆蒸，然后將剩余的n-1個(gè)序列重新構(gòu)造成一個(gè)堆，這樣就會(huì)得到n個(gè)元素中的次大值糖驴。如此反復(fù)執(zhí)行僚祷，就能得到一個(gè)有序序列了。
堆排序小結(jié)：
堆排序的運(yùn)行時(shí)間主要是耗費(fèi)在初始構(gòu)建堆和在重建堆時(shí)的反復(fù)篩選上贮缕。在構(gòu)建堆的過(guò)程中辙谜，因?yàn)槲覀兪峭耆鏄?shù)從最下層最右邊的非終端結(jié)點(diǎn)開(kāi)始構(gòu)建，將它與其孩子進(jìn)行比較和若有必要的交換感昼，對(duì)于每個(gè)非終端結(jié)點(diǎn)來(lái)說(shuō)装哆，其實(shí)最多進(jìn)行兩次比較和互換操作，因此整個(gè)構(gòu)建堆的時(shí)間復(fù)雜度為O（n）定嗓。
由于堆排序?qū)υ加涗浀呐判蛴涗洸⒉幻舾型汕伲虼怂鼰o(wú)論是最好、最壞和平均時(shí)間復(fù)雜度是一樣的宵溅。這在性能上要遠(yuǎn)遠(yuǎn)好于冒泡凌简、簡(jiǎn)單選擇、直接插入的時(shí)間復(fù)雜度恃逻〕В空間復(fù)雜度上，它只有一個(gè)用來(lái)交換的暫存單元寇损，也很不錯(cuò)凸郑。不過(guò)由于記錄的比較與交換是跳躍式進(jìn)行，因此堆排序也是一種不穩(wěn)定的排序方法矛市。由于初始構(gòu)建堆所需的比較次數(shù)較多线椰，因此，它并不適合待排序序列個(gè)數(shù)較少的情況尘盼。
七憨愉、歸并排序
將本是無(wú)序的數(shù)組序列{16,7,13,10,9,15,3,2,5，8,12卿捎，1,11,4,6,14}配紫，通過(guò)兩兩合并排序后再合并，最終獲得一個(gè)有序的數(shù)組午阵。
歸并排序就是利用歸并的思想實(shí)現(xiàn)的排序方法躺孝。它的原理是假設(shè)初始序列含有n個(gè)記錄，則可以看成是n個(gè)有序的子序列底桂，每個(gè)子序列的長(zhǎng)度為1植袍，然后兩兩歸并得到[n/2]個(gè)長(zhǎng)度為2或1的有序子序列；再兩兩歸并籽懦，......于个，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止暮顺，這種排序方法稱為2路歸并排序厅篓。
歸并排序小結(jié)：
歸并排序需要兩兩比較，不存在跳躍捶码，因此歸并排序是一種穩(wěn)定的排序算法羽氮。歸并排序是一種比較占用內(nèi)存，但卻效率高且穩(wěn)定的算法惫恼。
八档押、快速排序（對(duì)冒泡排序的改進(jìn)）
快速排序其實(shí)就是前面認(rèn)為最慢的冒泡排序的升級(jí)，它們都屬于交換排序類祈纯。即它也是通過(guò)不斷比較和移動(dòng)交換來(lái)實(shí)現(xiàn)排序的令宿，只不過(guò)它的實(shí)現(xiàn)，增大了記錄的比較和移動(dòng)的距離盆繁，將關(guān)鍵字較大的記錄從前面直接移動(dòng)到后面掀淘，關(guān)鍵字較小的記錄從后面直接移動(dòng)到前面，從而減少了總的比較次數(shù)和移動(dòng)交換次數(shù)油昂。
快速排序的基本思想：
通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分革娄，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序冕碟，以達(dá)到整個(gè)序列有序的目的拦惋。
快速排序小結(jié)：
快速排序的時(shí)間性能取決于快速排序遞歸的深度，可以用遞歸樹(shù)來(lái)描述遞歸算法的執(zhí)行情況安寺。在最優(yōu)情況下厕妖，快速排序算法的時(shí)間復(fù)雜度為O(nlogn)。就空間復(fù)雜度來(lái)說(shuō)挑庶，最好情況言秸，遞歸樹(shù)的深度為log2n软能，其空間復(fù)雜度就為O(logn)，最壞情況举畸，需要進(jìn)行n-1遞歸調(diào)用查排，其空間復(fù)雜度為O（n），平均情況抄沮，空間復(fù)雜度也為O(logn)跋核。
由于關(guān)鍵字的比較和交換是跳躍進(jìn)行的，因此叛买，快速排序是一種不穩(wěn)定的排序方法砂代。
九、總結(jié)
根據(jù)排序過(guò)程中借助的主要操作率挣，將內(nèi)排序分為：插入排序刻伊、交換排序、選擇排序和歸并排序四類难礼。
將7種算法的各種指標(biāo)進(jìn)行對(duì)比：
從算法的簡(jiǎn)單性來(lái)看娃圆，將7種算法分為2類：
簡(jiǎn)單算法：冒泡、簡(jiǎn)單選擇蛾茉、直接插入讼呢。
改進(jìn)算法：希爾、堆谦炬、歸并悦屏、快速。
就平均情況來(lái)看键思，顯然最后3種改進(jìn)算法要?jiǎng)龠^(guò)希爾排序础爬，并遠(yuǎn)遠(yuǎn)勝過(guò)前3中簡(jiǎn)單算法。
從最好情況看吼鳞，反而冒泡和直接插入更勝一籌看蚜，也就是說(shuō)，如果待排序序列總是基本有序赔桌，反而不應(yīng)該考慮4種復(fù)雜的改進(jìn)算法供炎。
從最壞情況看，堆排序與歸并排序又強(qiáng)過(guò)快速排序以及其它簡(jiǎn)單排序疾党。
從待排序的記錄個(gè)數(shù)上來(lái)說(shuō)音诫，待排序的個(gè)數(shù)n越小，采用簡(jiǎn)單排序方法越合適雪位。反之竭钝，n越大，采用改進(jìn)排序方法越合適。
