​ 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。需要额外的存储空间，时间复杂度： T(n) = Θ(nlgn)。

基本原理及实现

基本原理：使用递归、分治思想，将待排序数组分割成字数组，将排序后的字数组合并。

  • ① 当数组只包含一个元素时，直接返回该元素即可。
  • ② 取数组中间位置元素，递归调用左侧和右侧数组，进行归并排序。
  • ③ 将左侧和右侧排序后的有序数组进行合并。

使用Swift进行功能实现，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * 归并排序 - 算法思想
 * 使用递归、分治的思想。
 * ① 当数组只包含一个元素时，直接返回该元素即可。
 * ② 取数组中间位置元素，递归调用左侧和右侧数组，进行归并排序。
 * ③ 将左侧和右侧排序后的有序数组进行合并。
 *
 **/
func mergeSort<T:Comparable>(array: Array<T>, start:Int , end:Int) -> Array<T>{
    if start >= end {//① 只有一个元素，直接返回即可
        return [array[start]];
    }else{
        let middle = (start + end) / 2;
        //② 递归调用，给左侧数组排序
        let leftSortArray = mergeSort(array:array,start:start,end:middle);
        //② 递归调用，给右侧数组排序
        let rightSortedArray = mergeSort(array: array, start: middle + 1, end: end);
        
        //③ 合并有序数组
        var leftIndex = 0;
        var rightIndex = 0;
        let leftCount = leftSortArray.count;
        let rightCount = rightSortedArray.count;
        var retArray:Array<T> = [];
	// 两个有序数组均存在值时，依次插入最小值
        while leftIndex < leftCount && rightIndex < rightCount {
            let leftValue = leftSortArray[leftIndex];
            let rightValue = rightSortedArray[rightIndex];
            if leftValue < rightValue {
                retArray.append(leftValue);
                leftIndex += 1;
            }else{
                retArray.append(rightValue);
                rightIndex += 1;
            }
        }
        // 将左侧有序数组剩余部分依次插入到排序结果中
        while leftIndex < leftCount {
            let leftValue = leftSortArray[leftIndex];
            retArray.append(leftValue);
            leftIndex += 1;
        }
        // 将右侧有序数组剩余部分依次插入到排序结果中
        while rightIndex < rightCount {
            let rightValue = rightSortedArray[rightIndex];
            retArray.append(rightValue);
            rightIndex += 1;
        }
        
        return retArray;
    }
}

//调用方法
func callMergeSort<T:Comparable>(array:Array<T>)->Array<T>{
    let count = array.count;
    if count > 0 {
        return mergeSort(array: array, start: 0, end: count - 1);
    }else{
        return [];
    }

}

测试用例及结果

1
2
3
4
5
6
7
8
9
//测试用例
var intArray =  [16,4,7,9,8,11,11,15,24,1];
print("待排序数组：\(intArray)");
let sortedArray = callMergeSort(array: intArray);
print("排序后数组：\(sortedArray)");

//程序输出
待排序数组：[16, 4, 7, 9, 8, 11, 11, 15, 24, 1]
排序后数组：[1, 4, 7, 8, 9, 11, 11, 15, 16, 24]
1
2
3
4
5
6
7
8
9
//测试用例
var stringArray =  ["Java","C#","Python","Objective-C","Swift","PHP","BASIC","Pasical","Assembly"];
print("待排序数组：\(stringArray)");
let sortedStringArray = callMergeSort(array: stringArray);
print("排序后数组：\(sortedStringArray)");

//程序输出
待排序数组：["Java", "C#", "Python", "Objective-C", "Swift", "PHP", "BASIC", "Pasical", "Assembly"]
排序后数组：["Assembly", "BASIC", "C#", "Java", "Objective-C", "PHP", "Pasical", "Python", "Swift"]