圖片源于網(wǎng)絡(luò)
歸并排序：
歸并排序(Merge Sort)是建立在歸并操作上的一種有效的排序算法，算法主要采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。歸并排序比較占用內(nèi)存，但卻是一種效率高且穩(wěn)定的算法。
算法思想
把序列分成元素盡可能相等的兩半。
把兩半元素分別進(jìn)行排序。
把兩個(gè)有序表合并成一個(gè)。
綜上可知，歸并排序其實(shí)要做兩件事：
（1）“分解”——將序列每次折半劃分。
（2）“合并”——將劃分后的序列段兩兩合并后排序。合并相鄰有序子序列
圖-歸并排序示例圖
合并相鄰有序子序列過(guò)程：
合并相鄰有序子序列1
合并相鄰有序子序列2
范例代碼
/**
歸并排序
@param array 需要排序的Array
*/
+ (void)megerSort:(NSMutableArray *)array
{
/**
歸并排序其實(shí)要做兩件事：
（1）“分解”——將序列每次折半劃分。
（2）“合并”——將劃分后的序列段兩兩合并后排序。
*/
//排序數(shù)組
NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
//第一趟排序是的子數(shù)組個(gè)數(shù)為ascendingArr.count
for (NSNumber *num in array) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
/**
分解操作 每一次歸并操作 tempArray的個(gè)數(shù)為（當(dāng)數(shù)組個(gè)數(shù)為偶數(shù)時(shí)tempArray.count/2;當(dāng)數(shù)組個(gè)數(shù)為奇數(shù)時(shí)tempArray.count/2+1）;當(dāng)tempArray.count == 1時(shí)，歸并排序完成
*/
while (tempArray.count != 1) {
NSInteger i = 0;
//當(dāng)數(shù)組個(gè)數(shù)為偶數(shù)時(shí) 進(jìn)行合并操作， 當(dāng)數(shù)組個(gè)數(shù)為奇數(shù)時(shí)，最后一位輪空
while (i < tempArray.count - 1) {
//將i 與i+1 進(jìn)行合并操作 將合并結(jié)果放入i位置上 將i+1位置上的元素刪除
tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
[tempArray removeObjectAtIndex:i + 1];
//i++ 繼續(xù)下一循環(huán)的合并操作
i++;
}
}
NSLog(@"歸并排序結(jié)果：%@", tempArray);
}
//合并
+ (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
// 合并序列數(shù)組
NSMutableArray *resultArray = [NSMutableArray array];
// firstIndex是第一段序列的下標(biāo) secondIndex是第二段序列的下標(biāo)
NSInteger firstIndex = 0, secondIndex = 0;
// 掃描第一段和第二段序列，直到有一個(gè)掃描結(jié)束
while (firstIndex < array1.count && secondIndex < array2.count) {
// 判斷第一段和第二段取出的數(shù)哪個(gè)更小，將其存入合并序列，并繼續(xù)向下掃描
if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
} else {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
}
// 若第一段序列還沒(méi)掃描完，將其全部復(fù)制到合并序列
while (firstIndex < array1.count) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
}
// 若第二段序列還沒(méi)掃描完，將其全部復(fù)制到合并序列
while (secondIndex < array2.count) {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
// 返回合并序列數(shù)組
return resultArray.copy;
}
算法分析
歸并排序算法的性能
歸并排序算法的性能
時(shí)間復(fù)雜度
歸并排序的形式就是一棵二叉樹(shù)，它需要遍歷的次數(shù)就是二叉樹(shù)的深度，而根據(jù)完全二叉樹(shù)的可以得出它的時(shí)間復(fù)雜度是O(N*log N)。
空間復(fù)雜度
算法處理過(guò)程中，需要一個(gè)大小為n的臨時(shí)存儲(chǔ)空間用以保存合并序列。
算法穩(wěn)定性
在歸并排序中，相等的元素的順序不會(huì)改變，所以它是穩(wěn)定的算法。
歸并排序和堆排序、快速排序的比較
若從空間復(fù)雜度來(lái)考慮：首選堆排序，其次是快速排序，最后是歸并排序。
若從穩(wěn)定性來(lái)考慮，應(yīng)選取歸并排序，因?yàn)槎雅判蚝涂焖倥判蚨际遣环€(wěn)定的。
若從平均情況下的排序速度考慮，應(yīng)該選擇快速排序。
