當(dāng)n較大末盔，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序座慰。

快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法庄岖，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短角骤；

時(shí)間開銷

排序的時(shí)間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來衡量。

算法運(yùn)行時(shí)間代價(jià)的大略估算一般都按平均情況進(jìn)行估算心剥。對(duì)于那些受對(duì)象排序碼序列初始排列及對(duì)象個(gè)數(shù)影響較大的邦尊，需要按最好情況和最壞情況進(jìn)行估算

空間開銷

算法執(zhí)行時(shí)所需的附加存儲(chǔ)。

1.插入排序—直接插入排序(Straight Insertion Sort)

基本思想:將一個(gè)記錄插入到已排序好的有序表中优烧，從而得到一個(gè)新蝉揍，記錄數(shù)增1的有序表。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列畦娄，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入又沾，直至整個(gè)序列有序?yàn)橹埂?/p>

直接插入排序示例：

像撲克摸牌一樣，插入即表示將一個(gè)新的數(shù)據(jù)插入到一個(gè)有序數(shù)組中熙卡，并繼續(xù)保持有序杖刷。例如有一個(gè)長(zhǎng)度為N的無序數(shù)組，進(jìn)行N-1次的插入即能完成排序驳癌；第一次滑燃，數(shù)組第1個(gè)數(shù)認(rèn)為是有序的數(shù)組，將數(shù)組第二個(gè)元素插入僅有1個(gè)有序的數(shù)組中颓鲜；第二次表窘，數(shù)組前兩個(gè)元素組成有序的數(shù)組典予，將數(shù)組第三個(gè)元素插入由兩個(gè)元素構(gòu)成的有序數(shù)組中……第N-1次，數(shù)組前N-1個(gè)元素組成有序的數(shù)組乐严，將數(shù)組的第N個(gè)元素插入由N-1個(gè)元素構(gòu)成的有序數(shù)組中瘤袖，則完成了整個(gè)插入排序。?

以下面5個(gè)無序的數(shù)據(jù)為例：?

65 27 59 64 58 （文中僅細(xì)化了第四次插入過程）?

第1次插入: 27 65 59 64 58?

第2次插入: 27 59 65 64 58?

第3次插入: 27 59 64 65 58?

第4次插入: 27 58 59 64 65

算法的實(shí)現(xiàn)：

2. 插入排序—折半插入排序(二分插入)

算法簡(jiǎn)介

二分（折半）插入（Binary?insert?sort)排序是一種在直接插入排序算法上進(jìn)行小改動(dòng)的排序算法昂验。其與直接排序算法最大的區(qū)別在于查找插入位置時(shí)使用的是二分查找的方式捂敌，在速度上有一定提升。

原理

假設(shè)前面的都是排好序的列凛篙，把你需要插入的值跟前面的數(shù)組二分折半位置比較黍匾，小的話往前繼續(xù)二分插入，大就往后二分插入呛梆。

算法的實(shí)現(xiàn)：

3. 插入排序—希爾排序（Shell`s Sort）

基本思想：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序锐涯，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序填物。

①取定一個(gè)正整數(shù)d1作為間隔值纹腌，把全部記錄從第一個(gè)記錄起進(jìn)行分組，所有距離為d1倍數(shù)的記錄放在一組中滞磺，在各組內(nèi)進(jìn)行直接插入排序升薯。

②取定一個(gè)正整數(shù)d2，重復(fù)上述分組和排序工作击困，直至取di=1為止涎劈，即所有記錄在一個(gè)組中進(jìn)行直接插入排序。

③希爾提出的方法是：d1=n/2阅茶，di+1=d1/2

實(shí)例說明:對(duì)序列{25蛛枚，36，12脸哀，68蹦浦，45，16撞蜂，37盲镶，22 }進(jìn)行希爾排序。

算法的實(shí)現(xiàn)：

4. 選擇排序—簡(jiǎn)單選擇排序（Simple Selection Sort）

基本思想：在要排序的一組數(shù)中蝌诡，選出最懈然摺（或者最大）的一個(gè)數(shù)與第1個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最衅趾怠（或者最大）的與第2個(gè)位置的數(shù)交換顽照，依次類推，直到第n-1個(gè)元素（倒數(shù)第二個(gè)數(shù)）和第n個(gè)元素（最后一個(gè)數(shù)）比較為止。

示例:

算法的實(shí)現(xiàn)：

5. 選擇排序—堆排序（Heap Sort）

基本思想：

（1）把待排序數(shù)組構(gòu)造成一個(gè)最大堆

（2）取出樹的根(最大(小)值, 實(shí)際算法的實(shí)現(xiàn)并不是真正的取出)

（3）將樹中剩下的元素再構(gòu)造成一個(gè)最大堆(這里的構(gòu)造和第1步不一樣代兵，具體看實(shí)現(xiàn)部分)

（4）重復(fù)2,3操作尼酿，直到取完所有的元素

（5）把元素按取出的順序排列，即得到一個(gè)有序數(shù)組(在代碼實(shí)現(xiàn)里是通過交換操作"無形中"完成的)

在開始實(shí)現(xiàn)算法先看幾個(gè)結(jié)論(證明略):

（1）完全二叉樹A[0:n-1]中的任意節(jié)點(diǎn)植影，其下標(biāo)為 ii, 那么其子節(jié)點(diǎn)的下標(biāo)分別是為2i+12i+1 和 2(i+1)2(i+1)

（2）大小為n的完全二叉樹A[0:n-1]裳擎，葉子節(jié)點(diǎn)中下標(biāo)最小的是?n2??n2?， 非葉子節(jié)點(diǎn)中下標(biāo)最大的是?n2??1?n2??1

（3）如果數(shù)組是一個(gè)最大堆思币，那么最大元素就是A[0]

（4）最大堆中任意節(jié)點(diǎn)的左右子樹也是最大堆

6. 交換排序—冒泡排序（Bubble Sort）

基本思想：在要排序的一組數(shù)中鹿响，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整谷饿，讓較大的數(shù)往下沉惶我，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)博投，就將它們互換绸贡。

示例：

算法實(shí)現(xiàn)：

7. 交換排序—快速排序（Quick Sort）

基本思想：

1）選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素或者最后一個(gè)元素,

2）通過一趟排序講待排序的記錄分割成獨(dú)立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小毅哗。另一部分記錄的?元素值比基準(zhǔn)值大听怕。

3）此時(shí)基準(zhǔn)元素在其排好序后的正確位置

4）然后分別對(duì)這兩部分記錄用同樣的方法繼續(xù)進(jìn)行排序，直到整個(gè)序列有序虑绵。

示例：

（a）一趟排序的過程：

（b）排序的全過程

算法的實(shí)現(xiàn)：

8. 歸并排序（Merge Sort）

基本思想：歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表尿瞭，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的翅睛。然后再把有序子序列合并為整體有序序列声搁。

示例：

算法實(shí)現(xiàn)：