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

4464 단어 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); }

좋은 웹페이지 즐겨찾기