最近在學(xué)習(xí)算法，對此也做一個總結(jié)：
排序?qū)τ谌魏我粋€程序員來說，可能都不會陌生。你學(xué)的第一個算法，可能就是排序。大部分編程語言中，也都提供了排序函數(shù)。在平常的項目中，我們也經(jīng)常會用到排序。排序算法太多了，有很多可能你連名字都沒聽說過，比如猴子排序、睡眠排序、面條排序等。我只講眾多排序算法中的一小撮，也是最經(jīng)典的、最常用的：冒泡排序、插入排序、選擇排序、歸并排序、快速排序、計數(shù)排序、基數(shù)排序、桶排序。
按照時間復(fù)雜度把它們分成了三類：
算法之間性能也有差異，從哪些方面分析呢？可以從以下三個方面分析比較
排序算法的執(zhí)行效率
對于排序算法執(zhí)行效率的分析，我們一般會從這幾個方面來衡量：
1.最好情況、最壞情況、平均情況時間復(fù)雜度
我們在分析排序算法的時間復(fù)雜度時，要分別給出最好情況、最壞情況、平均情況下的時間復(fù)雜度。除此之外，你還要說出最好、最壞時間復(fù)雜度對應(yīng)的要排序的原始數(shù)據(jù)是什么樣的。
為什么要區(qū)分這三種時間復(fù)雜度呢？第一，有些排序算法會區(qū)分，為了好對比，所以我們最好都做一下區(qū)分。第二，對于要排序的數(shù)據(jù)，有的接近有序，有的完全無序。有序度不同的數(shù)據(jù)，對于排序的執(zhí)行時間肯定是有影響的，我們要知道排序算法在不同數(shù)據(jù)下的性能表現(xiàn)。
2. 時間復(fù)雜度的系數(shù)、常數(shù) 、低階
我們知道，時間復(fù)雜度反應(yīng)的是數(shù)據(jù)規(guī)模n很大的時候的一個增長趨勢，所以它表示的時候會忽略系數(shù)、常數(shù)、低階。但是實際的軟件開發(fā)中，我們排序的可能是10 個、100 個、1000 個這樣規(guī)模很小的數(shù)據(jù)，所以，在對同一階時間復(fù)雜度的排序算法性能對比的時候，我們就要把系數(shù)、常數(shù)、低階也考慮進來。
3. 比較次數(shù)和交換（或移動）次數(shù)
基于比較的排序算法的執(zhí)行過程，會涉及兩種操作，一種是元素比較大小，另一種是元素交換或移動。所以，如果我們在分析排序算法的執(zhí)行效率的時候，應(yīng)該把比較次數(shù)和交換（或移動）次數(shù)也考慮進去。
排序算法的內(nèi)存消耗
我們前面講過，算法的內(nèi)存消耗可以通過空間復(fù)雜度來衡量，排序算法也不例外。不過，針對排序算法的空間復(fù)雜度，我們還引入了一個新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空間復(fù)雜度是 O(1) 的排序算法。冒泡排序、插入排序、選擇排序，都是原地排序算法。
排序算法的穩(wěn)定性
僅僅用執(zhí)行效率和內(nèi)存消耗來衡量排序算法的好壞是不夠的。針對排序算法,我們還有一個重要的度量指標(biāo)，穩(wěn)定性。這個概念是說，如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變。
我通過一個例子來解釋一下。比如我們有一-組數(shù)據(jù)2, 9, 3, 4, 8, 3,按照大小排序之后就是2，3,3,4,8,9。
這組數(shù)據(jù)里有兩個3。經(jīng)過某種排序算法排序之后，如果兩個3的前后順序沒有改變,那我們就把這種排序算法叫作穩(wěn)定的排序算法;如果前后順序發(fā)生變化,那對應(yīng)的排序算法就叫作不穩(wěn)定的排序算法。
你可能要問了，兩個3哪個在前，哪個在后有什么關(guān)系啊，穩(wěn)不穩(wěn)定又有什么關(guān)系呢?為什么要考察排序算法的穩(wěn)定性呢?
很多數(shù)據(jù)結(jié)構(gòu)和算法課程，在講排序的時候，都是用整數(shù)來舉例，但在真正軟件開發(fā)中，我們要排序的往往不是單純的整數(shù)，而是一-組對象， 我們需要按照對象的某個key來排序。
比如說，我們現(xiàn)在要給電商交易系統(tǒng)中的“訂單”排序。訂單有兩個屬性, -個是下單時間，另一個是訂單金額。如果我們現(xiàn)在有10萬條訂單數(shù)據(jù),我們希望按照金額從小到大對訂單數(shù)據(jù)排序。對于金額相同的訂單，我們希望按照下單時間從早到晚有序。對于這樣一個排序需求，我們怎么來做呢?
最先想到的方法是:我們先按照金額對訂單數(shù)據(jù)進行排序，然后，再遍歷排序之后的訂單數(shù)據(jù)，對于每個金額相同的小區(qū)間再按照下單時間排序。這種排序思路理解起來不難,但是實現(xiàn)起來會很復(fù)雜。
借助穩(wěn)定排序算法，這個問題可以非常簡潔地解決。解決思路是這樣的:我們先按照下單時間給訂單排序，注意是按照下單時間，不是金額。排序完成之后，我們用穩(wěn)定排序算法，按照訂單金額重新排序。兩遍排序之后，我們得到的訂單數(shù)據(jù)就是按照金額從小到大排序，金額相同的訂單按照下單時間從早到晚排序的。為什么呢?
穩(wěn)定排序算法可以保持金額相同的兩個對象,在排序之后的前后順序不變。第一次排序之后， 所有的訂單按照下單時間從早到晚有序了。在第二次排序中，我們用的是穩(wěn)定的排序算法，所以經(jīng)過第二次排序之后，相同金額的訂單仍然保持下單時間從早到晚有序。
接下來我將一一講解各種經(jīng)典算法的核心思想
冒泡排序
冒泡排序只會操作相鄰的兩個數(shù)據(jù)。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關(guān)系要求。如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應(yīng)該在的位置，重復(fù) n 次，就完成了 n 個數(shù)據(jù)的排序工作。
可以看出，經(jīng)過一次冒泡操作之后，6 這個元素已經(jīng)存儲在正確的位置上。要想完成所有數(shù)據(jù)的排序，我們只要進行 6 次這樣的冒泡操作就行了。
實際上，剛講的冒泡過程還可以優(yōu)化。當(dāng)某次冒泡操作已經(jīng)沒有數(shù)據(jù)交換時，說明已經(jīng)達(dá)到完全有序，不用再繼續(xù)執(zhí)行后續(xù)的冒泡操作。我這里還有另外一個例子，這里面給 6 個元素排序，只需要 4次冒泡操作就可以了。
冒泡排序算法的原理比較容易理解，具體的代碼我貼到下面，你可以結(jié)合著代碼來看我前面講的原理。
#pragma mark -
#pragma mark 冒泡排序
- (void)gly_bubbleSort:(NSString *)propertyName result:(NSComparisonResult)result
{
if (self.count <= 1)
{
return;
}
for (NSInteger i = 0; i < self.count; i++)
{
//提前退出冒泡循環(huán)的標(biāo)志位
BOOL flag = NO;
for (NSInteger j = 0; j < self.count - i - 1; j++)
{
NSNumber *numberOne = [self[j] valueForKey:propertyName];
NSNumber *numberTwo = [self[j + 1] valueForKey:propertyName];
if ([numberOne compare:numberTwo] == result)
{
flag = YES;
[self exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
}
}
if (!flag)
{
break;
}
}
}
現(xiàn)在，結(jié)合剛才我分析排序算法的三個方面，我有三個問題要問你。
第一，冒泡排序是原地排序算法嗎?
冒泡的過程只涉及相鄰數(shù)據(jù)的交換操作，只需要常量級的臨時空間，所以它的空間復(fù)雜度為0(1), 是一個原地排序算法。
第二，冒泡排序是穩(wěn)定的排序算法嗎?
在冒泡排序中，只有交換才可以改變兩個元素的前后順序。為了保證冒泡排序算法的穩(wěn)定性，當(dāng)有相鄰的兩個元素大小相等的時候，我們不做交換，相同大小的數(shù)據(jù)在排序前后不會改變順序，所以冒泡排序是穩(wěn)定的排序算法。
第三，冒泡排序的時間復(fù)雜度是多少?
最好情況下，要排序的數(shù)據(jù)已經(jīng)是有序的了，我們只需要進行一次冒泡操作，就可以結(jié)束了，所以最好情況時間復(fù)雜度是0(n)。而最壞的情況是，要排序的數(shù)據(jù)剛好是倒序排列的，我們需要進行n次冒泡操作，所以最壞情況時間復(fù)雜度為O(n2)。
最好、最壞情況下的時間復(fù)雜度很容易分析，那平均情況下的時間復(fù)雜是多少呢?我們前面講過, 平均時間復(fù)雜度就是加權(quán)平均期望時間復(fù)雜度，分析的時候要結(jié)合概率論的知識。
對于包含n個數(shù)據(jù)的數(shù)組，這n個數(shù)據(jù)就有n!種排列方式。不同的排列方式，冒泡排序執(zhí)行的時間肯定是不同的。比如我們前面舉的那兩個例子，其中一一個要進行6次冒泡，而另一個只需要4次。如果用概率論方法定量分析平均時間復(fù)雜度，涉及的數(shù)學(xué)推理和計算就會很復(fù)雜。我這里還有一種思路,通過“有序度”和“逆序度”這兩個概念來進行分析。
有序度是數(shù)組中具有有序關(guān)系的元素對的個數(shù)。有序元素對用數(shù)學(xué)表達(dá)式表示就是這樣:
1有序元素對: a[i] <= a[j],如果i < j。
同理，對于一個倒序排列的數(shù)組，比如6, 5, 4, 3, 2, 1,有序度是0;對于一一個完全有序的數(shù)組，比如1, 2, 3, 4, 5, 6,有序度就是n*(n- -1)/2,也就是15。我們把這種完全有序的數(shù)組的有序度叫作滿有序度。
逆序度的定義正好跟有序度相反(默認(rèn)從小到大為有序)，我想你應(yīng)該已經(jīng)想到了。關(guān)于逆序度，我就不舉例子講了。你可以對照我講的有序度的例子自己看下。
逆序元素對：a[i] > a[j], 如果 i < j。
關(guān)于這三個概念，我們還可以得到一個公式:逆序度=滿有序度-有序度。我們排序的過程就是一種增加有序度，減少逆序度的過程，最后達(dá)到滿有序度，就說明排序完成了。
我還是拿前面舉的那個冒泡排序的例子來說明。要排序的數(shù)組的初始狀態(tài)是4, 5, 6, 3, 2, 1，其中，有序元素對有(4, 5)(4, 6)(5, 6), 所以有序度是3。n=6,所以排序完成之后終態(tài)的滿有序度為n*(n-1)/2=15。
冒泡排序包含兩個操作原子，比較和交換。每交換一次，有序度就加1。不管算法怎么改進，交換次數(shù)總是確定的，即為逆序度，也就是n*(n- -1)/2-初始有序度。此例中就是15- -3=12，要進行12次交換操作。
對于包含n個數(shù)據(jù)的數(shù)組進行冒泡排序，平均交換次數(shù)是多少呢?最壞情況下，初始狀態(tài)的有序度是0，所以要進行n(n-1)/2次交換。最好情況下，初始狀態(tài)的有序度是n(n-1)/2，就不需要進行交換。我們可以取個中間值n*(n-1)/4,來表示初始有序度既不是很高也不是很低的平均情況。
換句話說，平均情況下，需要n*(n-1)/4次交換操作，比較操作肯定要比交換操作多，而復(fù)雜度的上限是O(n2)，所以平均情況下的時間復(fù)雜度就是O(n2)。
這個平均時間復(fù)雜度推導(dǎo)過程其實并不嚴(yán)格，但是很多時候很實用，畢竟概率論的定量分析太復(fù)雜，不太好用。等我們講到快排的時候，我還會再次用這種“不嚴(yán)格”的方法來分析平均時間復(fù)雜度。
插入排序(Insertion Sort)
我們先來看一個問題。一個有序的數(shù)組，我們往里面添加一個新的數(shù)據(jù)后，如何繼續(xù)保持?jǐn)?shù)據(jù)有序呢?很簡單，我們只要遍歷數(shù)組，找到數(shù)據(jù)應(yīng)該插入的位置將其插入即可。
這是一個動態(tài)排序的過程，即動態(tài)地往有序集合中添加數(shù)據(jù)，我們可以通過這種方法保持集合中的數(shù)據(jù)一-直有序。而對于一組靜態(tài)數(shù)據(jù)，我們也可以借鑒上面講的插入方法，來進行排序，于是就有了插入排序算法。
那插入排序具體是如何借助.上面的思想來實現(xiàn)排序的呢?
首先，我們將數(shù)組中的數(shù)據(jù)分為兩個區(qū)間，已排序區(qū)間和未排序區(qū)間。初始已排序區(qū)間只有一個元素，就是數(shù)組的第一個元素。插入算法的核心思想是取未排序區(qū)間中的元素，在已排序區(qū)間中找到合適的插入位置將其插入，并保證已排序區(qū)間數(shù)據(jù)一-直有序。重復(fù)這個過程，直到未排序區(qū)間中元
素為空，算法結(jié)束。
如圖所示，要排序的數(shù)據(jù)是4, 5, 6, 1, 3, 2,其中左側(cè)為已排序區(qū)間，右側(cè)是未排序區(qū)間。
插入排序也包含兩種操作，一種是元素的比較，一種是元素的移動。當(dāng)我們需要將一個數(shù)據(jù)a插入到已排序區(qū)間時，需要拿a與已排序區(qū)間的元素依次比較大小，找到合適的插入位置。找到插入點之后，我們還需要將插入點之后的元素順序往后移動一-位，這樣才能騰出位置給元素a插入。
對于不同的查找插入點方法(從頭到尾、從尾到頭)，元素的比較次數(shù)是有區(qū)別的。但對于一個給定的初始序列，移動操作的次數(shù)總是固定的，就等于逆序度。
為什么說移動次數(shù)就等于逆序度呢?我拿剛才的例子畫了一個圖表，你一看就明白了。滿有序度是n*(n-1)/2=15，初始序列的有序度是5,所以逆序度是10。插入排序中，數(shù)據(jù)移動的個數(shù)總和也等于10=3+3+4。
插入排序的原理也很簡單吧？我也將代碼實現(xiàn)貼在這里，你可以結(jié)合著代碼再看下
#pragma mark -
#pragma mark 插入排序
- (void)gly_insertionSort:(NSString *)propertyName result:(NSComparisonResult)result
{
for (NSInteger i = 1; i < self.count; i++)
{
id aimObj = self[i];
NSNumber *aimNumber = [aimObj valueForKey:propertyName];
NSInteger j = i - 1;
for (; j >= 0; j--)
{
id obj = self[j];
NSNumber *number = [obj valueForKey:propertyName];;
if ([number compare:aimNumber] == result)
{
[self replaceObjectAtIndex:j + 1 withObject:self[j]];
}
else
{
break;
}
}
self[j + 1] = aimObj;
}
}
現(xiàn)在，我們來看點稍微復(fù)雜的東西。我這里還是有三個問題要問你。
第一，插入排序是原地排序算法嗎?
從實現(xiàn)過程可以很明顯地看出，插入排序算法的運行并不需要額外的存儲空間，所以空間復(fù)雜度是0(1)，也就是說，這是一個原地排序算法。
第二，插入排序是穩(wěn)定的排序算法嗎?
在插入排序中，對于值相同的元素，我們可以選擇將后面出現(xiàn)的元素，插入到前面出現(xiàn)元素的后面，這樣就可以保持原有的前后順序不變，所以插入排序是穩(wěn)定的排序算法。
第三，插入排序的時間復(fù)雜度是多少?
如果要排序的數(shù)據(jù)已經(jīng)是有序的，我們并不需要搬移任何數(shù)據(jù)。如果我們從尾到頭在有序數(shù)據(jù)組里面查找插入位置，每次只需要比較一個數(shù)據(jù)就能確定插入的位置。所以這種情況下，最好是時間復(fù)雜度為O(n)。 注意，這里是從尾到頭遍歷已經(jīng)有序的數(shù)據(jù)。
如果數(shù)組是倒序的，每次插入都相當(dāng)于在數(shù)組的第一個位置插入新的數(shù)據(jù)，所以需要移動大量的數(shù)據(jù)，所以最壞情況時間復(fù)雜度為O(n2)。
在數(shù)組中插入一個數(shù)據(jù)的平均時間復(fù)雜度是O(n)。所以，對于插入排序來說，每次插入操作都相當(dāng)于在數(shù)組中插入一個數(shù)據(jù)，循環(huán)執(zhí)行n次插入操作，所以平均時間復(fù)雜度為O(n2)。
選擇排序算法的實現(xiàn)思路有點類似插入排序，也分已排序區(qū)間和未排序區(qū)間。但是選擇排序每次會從未排序區(qū)間中找到最小的元素，將其放到已排序區(qū)間的末尾。
照例，也有三個問題需要你思考，不過前面兩種排序算法我已經(jīng)分析得很詳細(xì)了，這里就直接公布答案了。
首先，選擇排序空間復(fù)雜度為0(1)，是一種原地排序算法。選擇排序的最好情況時間復(fù)雜度、最壞情況和平均情況時間復(fù)雜度都為0(n2)。 你可以自己來分析看看。
那選擇排序是穩(wěn)定的排序算法嗎?這個問題我著重來說一下。
答案是否定的，選擇排序是一種不穩(wěn)定的排序算法。從我前面畫的那張圖中，你可以看出來，選擇排序每次都要找剩余未排序元素中的最小值，并和前面的元素交換位置，這樣破壞了穩(wěn)定性。
比如5, 8, 5, 2, 9這樣一-組數(shù)據(jù)，使用選擇排序算法來排序的話，第一次找到最小元素 2，與第一個5交換位置，那第一個5和中間的5順序就變了，所以就不穩(wěn)定了。正是因此，相對于冒泡排序和插入排序，選擇排序就稍微遜色了。
希爾排序
希爾排序**(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是插入排序算法的一種更高效的改進版本。對于中等規(guī)模的數(shù)據(jù)效果顯著，希爾排序是非穩(wěn)定排序算法。
希爾排序核心思想：設(shè)待排序元素序列有n個元素，首先取一個整數(shù)increment（小于n）作為間隔將全部元素分為increment個子序列，所有距離為increment的元素放在同一個子序列中，在每一個子序列中分別實行直接插入排序。然后縮小間隔increment，重復(fù)上述子序列劃分和排序工作。直到最后取increment=1，將所有元素放在同一個子序列中排序為止。 由于開始時，increment的取值較大，每個子序列中的元素較少，排序速度較快，到排序后期increment取值逐漸變小，子序列中元素個數(shù)逐漸增多，但由于前面工作的基礎(chǔ)，大多數(shù)元素已經(jīng)基本有序，所以排序速度仍然很快。
首先它把較大的數(shù)據(jù)集合分割成若干個小組（邏輯上分組），然后對每一個小組分別進行插入排序，此時，插入排序所作用的數(shù)據(jù)量比較?。恳粋€小組），插入的效率比較高
1>下面給出一個數(shù)據(jù)列：
2>第一趟取increment的方法是：n/3向下取整=3（關(guān)于increment的取法之后會有介紹）。將整個數(shù)據(jù)列劃分為間隔為3的3個子序列，然后對每一個子序列執(zhí)行直接插入排序，相當(dāng)于對整個序列執(zhí)行了部分排序調(diào)整。圖解如下：
3>第二趟將間隔increment= increment/3向下取整+1=2，將整個元素序列劃分為2個間隔為2的子序列，分別進行排序。圖解如下：
4>第3趟把間隔縮小為increment= increment/3向下取整+1=1，當(dāng)增量為1的時候，實際上就是把整個數(shù)列作為一個子序列進行插入排序，圖解如下：
5>直到increment=1時，就是對整個數(shù)列做最后一次調(diào)整，因為前面的序列調(diào)整已經(jīng)使得整個序列部分有序，所以最后一次調(diào)整也變得十分輕松，這也是希爾排序性能優(yōu)越的體現(xiàn)。
直接上代碼:
- (void)gly_shellSort:(NSString *)propertyName result:(NSComparisonResult)result
{
NSInteger gap = (NSInteger)self.count / 2;
while (gap >= 1)
{
for (NSInteger i = gap ; i < self.count; i++)
{
id tempObj = self[i];
NSNumber *tempNumber = [tempObj valueForKey:propertyName];
NSInteger j = i;
while (j >= gap && [[self[j - gap] valueForKey:propertyName] compare:tempNumber] == result)
{
[self replaceObjectAtIndex:j withObject:[self objectAtIndex:j - gap]];
j -= gap;
}
[self replaceObjectAtIndex:j withObject:tempObj];
}
gap = gap / 2;
}
}
最后總結(jié):
- 冒泡、插入和選擇排序的時間復(fù)雜度都是 O(n2)，比較高，適合小規(guī)模數(shù)據(jù)的排序
- 希爾排序的時間復(fù)雜度為O(n(1.3—2))，因此中等大小規(guī)模表現(xiàn)良好
- 接下來講到的快速排序和歸并排序的時間復(fù)雜度均為O(nlogn)，適合大規(guī)模數(shù)據(jù)的排序。
最后的最后：
自己寫了一個NSMutableArray+GLYSort算法分類，只需1行代碼，即可完成復(fù)雜排序操作。
