图片源于网络
归并排序：
归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法，算法主要采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序比较占用内存，但却是一种效率高且稳定的算法。
算法思想
-
把序列分成元素尽可能相等的两半。
-
把两半元素分别进行排序。
-
把两个有序表合并成一个。
综上可知，归并排序其实要做两件事：
（1）“分解”——将序列每次折半划分。
（2）“合并”——将划分后的序列段两两合并后排序。合并相邻有序子序列
图-归并排序示例图
合并相邻有序子序列过程：
合并相邻有序子序列1
合并相邻有序子序列2
范例代码
/**
归并排序
@param array 需要排序的Array
*/
+ (void)megerSort:(NSMutableArray *)array
{
/**
归并排序其实要做两件事：
（1）“分解”——将序列每次折半划分。
（2）“合并”——将划分后的序列段两两合并后排序。
*/
//排序数组
NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
//第一趟排序是的子数组个数为ascendingArr.count
for (NSNumber *num in array) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
/**
分解操作 每一次归并操作 tempArray的个数为（当数组个数为偶数时tempArray.count/2;当数组个数为奇数时tempArray.count/2+1）;当tempArray.count == 1时，归并排序完成
*/
while (tempArray.count != 1) {
NSInteger i = 0;
//当数组个数为偶数时 进行合并操作， 当数组个数为奇数时，最后一位轮空
while (i < tempArray.count - 1) {
//将i 与i+1 进行合并操作 将合并结果放入i位置上 将i+1位置上的元素删除
tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
[tempArray removeObjectAtIndex:i + 1];
//i++ 继续下一循环的合并操作
i++;
}
}
NSLog(@"归并排序结果：%@", tempArray);
}
//合并
+ (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
// 合并序列数组
NSMutableArray *resultArray = [NSMutableArray array];
// firstIndex是第一段序列的下标 secondIndex是第二段序列的下标
NSInteger firstIndex = 0, secondIndex = 0;
// 扫描第一段和第二段序列，直到有一个扫描结束
while (firstIndex < array1.count && secondIndex < array2.count) {
// 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
} else {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
}
// 若第一段序列还没扫描完，将其全部复制到合并序列
while (firstIndex < array1.count) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
}
// 若第二段序列还没扫描完，将其全部复制到合并序列
while (secondIndex < array2.count) {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
// 返回合并序列数组
return resultArray.copy;
}
算法分析
归并排序算法的性能
归并排序算法的性能
时间复杂度
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(N*log N)。
空间复杂度
算法处理过程中，需要一个大小为n的临时存储空间用以保存合并序列。
算法稳定性
在归并排序中，相等的元素的顺序不会改变，所以它是稳定的算法。
归并排序和堆排序、快速排序的比较
-
若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
-
若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
-
若从平均情况下的排序速度考虑，应该选择快速排序。
网友评论