归并排序

发表于 | 分类于

核心思想是分治法，将数组1分为2，通过递归，把数组拆分成很多个小数组（只有2个元素），然后对小数组进行排序，排序完之后进行合并。

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
64
65
66
67
68
69
70
void mergeArray(int targetArr[], int start, int mid, int last, int tmpArr[])
{
    int k = 0;
    int backupStart = start;
    
    // 把数组1分为2
    int leftArrLast = mid;
    int rightArrStart = mid+1;
    
    // 合并2个数组
    while (start <= leftArrLast && rightArrStart <= last) {
        
        // 如果左边元素比右边元素大
        if (targetArr[start] <= targetArr[rightArrStart]) {
            // 把左边元素放入临时数组中
            tmpArr[k] = targetArr[start];
            start++;
            
        }else{
            // 如果右边元素较小，把右边元素放入临时数组中
            tmpArr[k] = targetArr[rightArrStart];
            rightArrStart++;
        }
        
        k++;
    }
    
    // 左边2边，肯定会有1边多出有元素没比较
    
    // 把左边剩余的部分放入临时数组中
    while (start <= leftArrLast) {
        tmpArr[k] = targetArr[start];
        k++;
        start++;
    }
    
    // 把右边剩余部分放入临时数组中
    while (rightArrStart <= last) {
        tmpArr[k] = targetArr[rightArrStart];
        k++;
        rightArrStart++;
    }
    
    // 把排序好的合并数组放入原来数组中，注意原来数组的开始索引，从backStart+i开始
    for (int i = 0; i < k; i++) {
        targetArr[backupStart+i] = tmpArr[i];
    }
    
}

void mergeSort(int targetArr[], int start, int last, int tmpArr[])
{
    
    // 传入1个临时的 tmpArr 是为了节省内存开销
    
    if (start < last) {
        
        // 1分为2，分而治之
        int mid = (start+last)/2;
        
        // 对左边元素进行排序
        mergeSort(targetArr, start, mid, tmpArr);
        
        // 对右边元素进行排序, 索引从 mid+1 开始
        mergeSort(targetArr, mid+1, last, tmpArr);
        
        // 合并左右2边的排序数组
        mergeArray(targetArr, start, mid, last, tmpArr);
    }
}