归并排序图解版

归并排序过程探索

Code

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100;

int fr[N];
int bk[N];

///合并两个排好序的序列
void my_merge(int * s, int start, int mid, int over)
{
    cout << "合并开始" << '\n' << '\n';
    int fr_len = mid - start + 1;
    int bk_len = over - mid;
    cout << "前部分长度 " << fr_len << " 后部分长度 " << bk_len << '\n';

    for(int i = 0; i < fr_len; ++i)
        fr[i] = s[start + i];
    for(int i = 0; i < bk_len; ++i)
        bk[i] = s[mid + 1 + i];

    cout << "前部分元素" << '\n';
    for(int i = 0; i < fr_len; ++i)
        cout << fr[i] << ' ';
    cout << '\n';
    cout << "后部分元素" << '\n';
    for(int i = 0; i < bk_len; ++i)
        cout << bk[i] << ' ';
    cout << '\n';

    ///两个序列中的数相互比较，将较小的数先插入新的序列中
    int i = 0, j = 0, k = start;
    while(i < fr_len && j < bk_len)
    {
        cout << i << ' ' << fr[i] << ' ' << j << ' ' << bk[j] << '\n';
        if(fr[i] < bk[j])
            s[k++] = fr[i++];
        else
            s[k++] = bk[j++];
    }

    ///剩余元素合并
    while(i < fr_len)
        s[k++] = fr[i++];
    while(j < bk_len)
        s[k++] = bk[j++];

    cout << "此次排序结果 ： " << '\n';
    for(int t = 0; t < k; ++t)
        cout << s[t] << ' ';
    cout << '\n';
    cout << "本次合并结束" << '\n' << '\n';
}

void merge_sort(int * s, int start, int over)
{
    if(start < over)
    {
        int mid = (start + over) / 2;
        merge_sort(s, start, mid);
        merge_sort(s, mid + 1, over);
        my_merge(s, start, mid, over);
    }
}

int main()
{
    int s[] = {9, 4, 5, 7, 3, 6, 8, 2, 0, 1};
    int len = sizeof(s) / sizeof(int);
    int ans[len];
    merge_sort(s, 0, len - 1);
    for(int i = 0; i < len; ++i)
        cout << s[i] << ' ';
    cout << '\n';
    return 0;
}