算法-归并排序

原理简单，代码也简单，但是不好理解，难理解的点在于递归，核心点在于merge。（递归过程难理解就运行起来看打印结果）

1、原理图解

归并排序原理

2、代码

// 归并排序
void msort(int arr[], int tempArr[], int left, int right)
{
    // 如果只有一个元素，那么不需要继续划分
    // 只有一个元素的区域，本生就是有序的，只需要被归并即可
    if (left < right)
    {
        // 找中间点
        int mid = (left + right) / 2;
        NSLog(@"msort left=%d mid=%d right=%d",left,mid,right);
        // 递归划分左半区
        msort(arr, tempArr, left, mid);
        // 递归划分右半区
        msort(arr, tempArr, mid + 1, right);
        // 合并已经排序的部分
        merge(arr, tempArr, left, mid, right);
    }
}

// 合并
void merge(int arr[], int tempArr[], int left, int mid, int right)
{
    NSLog(@"merge left=%d mid=%d right=%d",left,mid,right);
    // 标记左半区第一个未排序的元素
    int l_pos = left;
    // 标记右半区第一个未排序的元素
    int r_pos = mid + 1;
    // 临时数组元素的下标
    int pos = left;

    // 合并
    while (l_pos <= mid && r_pos <= right)
    {
        if (arr[l_pos] < arr[r_pos])  // 左半区第一个剩余元素更小
            tempArr[pos++] = arr[l_pos++];
        else  // 右半区第一个剩余元素更小
            tempArr[pos++] = arr[r_pos++];
    }

    // 合并左半区剩余的元素
    while (l_pos <= mid)
        tempArr[pos++] = arr[l_pos++];

    // 合并右半区剩余的元素
    while (r_pos <= right)
        tempArr[pos++] = arr[r_pos++];

    // 把临时数组中合并后的元素复制回原来的数组
    while (left <= right)
    {
        arr[left] = tempArr[left];
        left++;
    }
}
- (void)mergeTest {
    int arr[] = {6,1,5,3,9,2,10,8,4,7};
    int tempArr[10];
    msort(arr, tempArr, 0, 9);
    print_arr(arr, 10);
}

3、运行图解

msort left=0 mid=4 right=9
msort left=0 mid=2 right=4
msort left=0 mid=1 right=2
msort left=0 mid=0 right=1
merge left=0 mid=0 right=1
merge left=0 mid=1 right=2
msort left=3 mid=3 right=4
merge left=3 mid=3 right=4
merge left=0 mid=2 right=4
msort left=5 mid=7 right=9
msort left=5 mid=6 right=7
msort left=5 mid=5 right=6
merge left=5 mid=5 right=6
merge left=5 mid=6 right=7
msort left=8 mid=8 right=9
merge left=8 mid=8 right=9
merge left=5 mid=7 right=9
merge left=0 mid=4 right=9