#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <time.h>
#include <sys/timeb.h>
#define MAX 20
using namespace std;
int* create_list(int len) {
int* list = (int *)malloc(sizeof(int) * len);
memset(list, 0, sizeof(int) * len);
for (int i = 0; i < len; i++) {
list[i] = rand() % 200;
}
return list;
}
void print_list(int list[], int len) {
if (NULL == list || len <= 0) {
return;
}
int line = 0;
for (int i = 0; i < len; i++, line ++) {
if (line > 9)
{
cout << endl;
line = 0;
}
cout << list[i] << " ";
}
cout << endl;
}
long getSysTime() {
struct timeb tb;
ftime(&tb);
return tb.time * 1000 + tb.millitm;
}
// 合并算法 从小到大
void Merge(int list[], int start, int end, int mid, int* tmp) {
int i_start = start;
int i_end = mid;
int j_start = mid + 1;
int j_end = end;
// 表示辅助空间有多少元素
int length = 0;
// 合并两个有序序列
while (i_start <= i_end && j_start <= j_end) {
if (list[i_start] < list[j_start]) {
tmp[length++] = list[i_start++];
} else {
tmp[length++] = list[j_start++];
}
}
// i序列
while (i_start <= i_end) {
tmp[length++] = list[i_start++];
}
// j序列
while (j_start <= j_end) {
tmp[length++] = list[j_start++];
}
// 辅助空间的数据赋值给原空间
for (int i = 0; i < length; i++) {
list[start + i] = tmp[i];
}
}
void MergeSort(int list[], int start, int end, int* tmp) {
if (start >= end) {
return;
}
// 取中间点
int mid = (start + end) / 2;
// 分组
/// 左半边
MergeSort(list, start, mid, tmp);
/// 右半边
MergeSort(list, mid + 1, end, tmp);
// 合并
Merge(list, start, end, mid, tmp);
}
int main(int argc, char* argv[]) {
srand((unsigned int)time(NULL));
int *list = create_list(MAX);
// 辅助空间
int *tmp = (int *)malloc(sizeof(int) * MAX);
print_list(list, MAX);
MergeSort(list, 0, MAX - 1, tmp);
print_list(list, MAX);
// 释放
free(tmp);
free(list);
return 0;
}
网友评论