/*********************************************
* 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];
}
}
|
