基础算法——归并排序

归并排序

1. 基本思想

基本流程：

1. 确定分界点

2. 递归排序left,right

3. 归并——合二为一（重点）

2. 实现方法

• 双路归并，合二为一

• 时间复杂度为o(n)

算法思想：

1. 先把左边排好序，再把右边排好序

2. 用i,j分别指向数组1和数组2

3. 比较i,j指向的数据，若i中的数据小于j中的数据，则将i中的数据取出放到tmp[]数组中，i++

4. 继续比较，直到某一指针指向其所对应的数组末尾，则将另一指针后面的所有的数直接拿到tmp[]数组的末尾

5. 再将tmp[]数组中的数放回至想要存放数据的数组中

算法模板：

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    /*
    自己第一遍写写成这样了，多了一些if这种很没必要的判断
    if (i == mid+1)
        while(j <= r)  tmp[k++] = q[j++];
    else if (j == r+1)
        while(i <= mid)  tmp[k++] = q[i++];
    */

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

个人觉得可以将k从l起开始赋值，写成以下形式,最后一步for循环的赋值或许会更简便一点

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = l, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l; i <= r; ++i) q[i] = tmp[i];
}