고전 알고리즘 을 병합 하여 정렬 하 는 C 구현 방법

예전 에 병합 정렬 알고리즘 을 쓴 적 이 있 지만 시간 이 지나 서 어떻게 썼 는 지 잊 어 버 렸 어 요.마침 알고리즘 을 복습 할 때 이 문제 에 부 딪 혔 을 때 다시 써 서 부 딪 힌 문제 들 을 기록 하 였 다.
핵심 은 두 개의 배열 로 분 단 된 두 배열 의 변 수 를 기록 한 다음 에 순서대로 크기 를 비교 하면 된다 는 것 이다.여기 디 테 일 한 가지 주의 가 필요 합 니 다. arrtemp1[mid + 1 - low] = INT_MAX; 이 코드 는 보초병 을 설치 하 는 데 사용 되 는데, 이런 방법 으로 배열 이 비어 있 는 지 아 닌 지 를 판단 하 는 것 을 피 할 수 있다.
구체 적 인 알고리즘 의 위조 코드 는 Chapter 2 알고리즘 기초, P17 을 참고 할 수 있다.
원본 코드 는 다음 과 같 습 니 다:

// =====================【     】==================
// @ author : zhyh2010
// @ date : 20150606
// @ version : 1.0
// @ description : 
// =====================【    】==================

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define NUM 20
int arr[NUM] = { 0 };
int arr_temp1[NUM] = { 0 };
int arr_temp2[NUM] = { 0 };

void init()
{
    time_t tm;
    time(&tm);
    srand((unsigned int)tm);

    int max_item = 100;
    for (int i = 0; i != NUM; i++)
        arr[i] = rand() % max_item;
}

void display(int * arr)
{
    for (int i = 0; i != NUM; i++)
        printf("%-10d", arr[i]);
    printf("
");
}

void merge(int low, int mid, int high)
{
    for (int ii = 0; ii != mid + 1 - low; ii++)
    {
        arr_temp1[ii] = arr[low + ii];
    }
    arr_temp1[mid + 1 - low] = INT_MAX;

    for (int ii = 0; ii != high - mid; ii++)
    {
        arr_temp2[ii] = arr[mid + 1 + ii];
    }
    arr_temp2[high - mid] = INT_MAX;

    int i = 0;
    int j = 0;
    for (int k = low; k != high + 1; k++)
    {       
        if (arr_temp1[i] < arr_temp2[j])
            arr[k] = arr_temp1[i++];
        else
            arr[k] = arr_temp2[j++];
    }
}

void mergeSort(int low, int high)
{
    if (low >= high)
        return;

    int mid = (low + high) / 2;
    mergeSort(low, mid);
    mergeSort(mid + 1, high);
    merge(low, mid, high);
}


void main()
{
    init();
    printf("     
");
    display(arr);

    mergeSort(0, NUM - 1);
    printf("     
");
    display(arr);
}