什么是排序？就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領(lǐng)域得到相當(dāng)?shù)刂匾?，尤其是在大量?shù)據(jù)的處理方面。一個(gè)優(yōu)秀的算法可以節(jié)省大量的資源。在各個(gè)領(lǐng)域中考慮到數(shù)據(jù)的各種限制和規(guī)范，要得到一個(gè)符合實(shí)際的優(yōu)秀算法，得經(jīng)過大量的推理和分析。

一、概念

排序(Sorting) 是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)關(guān)鍵字有序的序列。

排序算法（英語：Sorting algorithm）是一種將一組特定的數(shù)據(jù)按某種順序進(jìn)行排列的算法。排序算法多種多樣，性質(zhì)也大多不同。

二、分類

排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。

排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。

用一張圖概括：

三、評(píng)價(jià)標(biāo)準(zhǔn)

穩(wěn)定性是一個(gè)特別重要的評(píng)估標(biāo)準(zhǔn)。穩(wěn)定的算法在排序的過程中不會(huì)改變?cè)乇舜说奈恢玫南鄬?duì)次序，反之不穩(wěn)定的排序算法經(jīng)常會(huì)改變這個(gè)次序，這是我們不愿意看到的。我們?cè)谑褂门判蛩惴ɑ蛘哌x擇排序算法時(shí)，更希望這個(gè)次序不會(huì)改變，更加穩(wěn)定，所以排序算法的穩(wěn)定性，是一個(gè)特別重要的參數(shù)衡量指標(biāo)依據(jù)。就如同空間復(fù)雜度和時(shí)間復(fù)雜度一樣，有時(shí)候甚至比時(shí)間復(fù)雜度、空間復(fù)雜度更重要一些。所以往往評(píng)價(jià)一個(gè)排序算法的好壞往往可以從下邊幾個(gè)方面入手：

（1）時(shí)間復(fù)雜度：即從序列的初始狀態(tài)到經(jīng)過排序算法的變換移位等操作變到最終排序好的結(jié)果狀態(tài)的過程所花費(fèi)的時(shí)間度量。

（2）空間復(fù)雜度：就是從序列的初始狀態(tài)經(jīng)過排序移位變換的過程一直到最終的狀態(tài)所花費(fèi)的空間開銷。

（3）使用場(chǎng)景：排序算法有很多，不同種類的排序算法適合不同種類的情景，可能有時(shí)候需要節(jié)省空間對(duì)時(shí)間要求沒那么多，反之，有時(shí)候則是希望多考慮一些時(shí)間，對(duì)空間要求沒那么高，總之一般都會(huì)必須從某一方面做出抉擇。

（4）穩(wěn)定性：穩(wěn)定性是不管考慮時(shí)間和空間必須要考慮的問題，往往也是非常重要的影響選擇的因素。