简谈归并排序
归并排序算法是一种思想挺有意思的排序算法。具体内容还是从算法实现思想、时间复杂度、算法稳定性以及算法实现四个方面介绍。
1
算法实现思想
1、第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2、第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3、第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4、重复步骤3直到某一指针超出序列尾；
5、将另一序列剩下的所有元素直接复制到合并序列尾。
2
举例说明 ：假设存在数列：{4，189，80，290，35，8，2}
初始状态：4，189，80，290，35，8，2
第一次归并后：{4，189}，{80，290}，{35，8}，{2} 比较次数：3
第二次归并后：{4，80，189，290}，{2，8，35} 比较次数：4
第三次归并后：{2，4，8，35，80，189，290} 比较次数：4
总比较次数：3+4+4 = 11
3
时间复杂度 O(n log n)
4
算法稳定性 ： 稳定
5
算法实现
C语言实现
void Merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex){
int i = startIndex;
int j = midIndex + 1;
int k = startIndex;
while (i != midIndex && j != endIndex) {
if (sourceArr[i] > sourceArr[j]) {
tempArr[k++] = sourceArr[j ++];
}else{
tempArr[k++] = sourceArr[i ++];
}
}
while (i != midIndex + 1) {
tempArr[k++] = sourceArr[i++];
}
while (j != endIndex + 1) {
tempArr[k ++] = sourceArr[j++];
}
for (i = startIndex; i < endIndex; i ++) {
sourceArr[i] = tempArr[i];
}
}
//recursion operation
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex){
int midIndex;
if (startIndex < endIndex) {
midIndex = (startIndex + endIndex)/2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex + 1, endIndex);
Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
}
}Objective-C语言实现
- (NSArray *)mergeWithArray:(NSArray *)sourceArray
startIndex:(NSInteger)startIndex
midIndex:(NSInteger)midIndex
endIndex:(NSInteger)endIndex{
NSMutableArray *sourceMutableArray = [NSMutableArray arrayWithArray:sourceArray];
NSMutableArray *tempMutableArray = [[NSMutableArray alloc] init];
NSInteger i = startIndex;
NSInteger j = midIndex + 1;
NSInteger k = startIndex;
while (i != midIndex && j != endIndex){
if (sourceMutableArray[i] > sourceMutableArray[j]) { //tempMutableArray[k] = sourceMutableArray[j];
[tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[j]];
k ++;
j ++;
}else{
//tempMutableArray[k] = sourceMutableArray[i];
[tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[i]];
k ++;
i ++;
}
}
while (i != midIndex + 1) {
[tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[i]];
k ++;
i ++;
}
while (j != endIndex + 1) {
[tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[j]];
k ++;
j ++;
}
for (i = startIndex; i < endIndex; i ++) {
[sourceMutableArray replaceObjectAtIndex:i withObject:tempMutableArray[i]];
}
return sourceMutableArray;
}
- (NSArray *)mergeSortWithArray:(NSArray *)sourceArray
startIndex:(NSInteger)startIndex
endIndex:(NSInteger)endIndex{
if (startIndex < endIndex) {
NSInteger midIndex = (startIndex + endIndex)/2;
NSArray *tempArray = [self mergeSortWithArray:sourceArray
startIndex:startIndex
endIndex:endIndex];
NSArray *tempArray2 = [self mergeSortWithArray:tempArray
startIndex:midIndex + 1
endIndex:endIndex];
return [self mergeWithArray:tempArray2
startIndex:startIndex
midIndex:midIndex
endIndex:endIndex];
}
return nil;
}Swift语言实现
func mergeSort(array: [Int])-> [Int]{
var helper = Array(count: array.count, repeatedValue: 0)
var array = array
mergeSort(&array, helper: &helper, low: 0, high: array.count - 1) return array
}
func mergeSort(inout array: [Int], inout helper:[Int], low: Int, high: Int){
guard low < high else{
return
}
let middle = (high + low)/2 + low
mergeSort(&array, helper: &helper, low: low, high: middle)
mergeSort(&array, helper: &helper, low: middle + 1, high: high)
merge(&array, helper: &helper, low: low, middle: middle, high: high)
}
func merge(inout array: [Int], inout helper: [Int], low: Int, middle:Int, high:Int){
for i in low...high{
helper[i] = array[i]
}
var helperLeft = low
var helpeRight = middle + 1
var current = low
while helperLeft <= middle && helpeRight <= high{
if helperLeft <= helpeRight{
array[current] = helper[helperLeft]
helperLeft++
}else{
array[current] = helper[helpeRight]
helpeRight++
}
current++
}
guard middle - helperLeft >= 0 else{
return
}
for i in 0...middle - helperLeft{
array[current+i] = helper[helperLeft + i]
}
}最后，感谢大家阅读，如有问题，欢迎大家留言！！!
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2017-03-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读