归并排序算法是一种思想挺有意思的排序算法。具体内容还是从算法实现思想、时间复杂度、算法稳定性以及算法实现四个方面介绍。
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]
}
}
最后,感谢大家阅读,如有问题,欢迎大家留言!!!