Merge Sort C++ 实现

共四个文件

1. mergesort.h //mergesort fuction declare

2. mergesort.cpp //mergesort function define

3. main.cpp //test function

4. Makefile

1. mergesort.h

/*********************************************
 * Author: zhuxianfeng
 * Time: Wed 05 Nov 2008 10:38:53 AM CST
 * Filename: mergesort.h
 * Description:
 *********************************************/

#ifndef MERGESORT_H
#define MERGESORT_H

/**
 * 归并排序，memerge sort
 * 时间复杂度为O(nlgn)
 */
template<class T>
void mergesort(T array[], const int first, const int last);

/**
 * 对已经排好序的两个子数组进行排序
 */
template<class T>
void merge(T array[], const int first, const int last);

#endif


2. mergesort.cpp

/*********************************************
 * Author: zhuxianfeng
 * Time: Wed 05 Nov 2008 10:43:52 AM CST
 * Filename: mergesort.cpp
 * Description:
 *********************************************/

#include "mergesort.h"

/**
 * 归并排序，memerge sort
 * 时间复杂度为O(nlgn)
 */
template<class T>
void mergesort(T array[], const int first, const int last) {
    if (first < last) {
        int mid = (first + last) / 2;
        mergesort(array, first, mid);
        mergesort(array, mid + 1, last);
        merge(array, first, last);
    }
}

/**
 * 对已经排好序的两个子数组进行排序
 */
template<class T>
void merge(T array[], const int first, const int last) {
    const int mid = (first + last) / 2;
    const int length = last - first + 1;
    T data[length];
    int i = first;
    int j = mid + 1;
    int index = 0;
    while (i <= mid && j <= last) {
        if (array[i] < array[j]) {
            data[index++] = array[i++];
        } else {
            data[index++] = array[j++];
        }
    }
    //接下来这两个循环只会进入一个

    while (i <= mid) {
        data[index++] = array[i++];
    }
    while (j <= last) {
        data[index++] = array[j++];
    }

    //复制数组

    for (index=0; index<length; index++) {
        array[first + index] = data[index];
    }
}


3. Source Download

文件:	merge_sort.tar.gz
大小:	20KB
下载:	下载