分治算法与合并排序示例

#include <stdio.h>
#include <memory.h>
#include <algorithm>

using namespace std;

#define MAX_N 10

void merge_sort(int seq[], int len);

// 打印数组
void my_print(int seq[], int len)
{
for (int i = 0; i < len; i++)
printf("%d\n", seq[i]);
}

int main()
{
int arr[] = {9, 8, 7, 6, 1, 3, 2, 4, 5, 0};
merge_sort(arr, MAX_N);

my_print(arr, MAX_N);
return 0;
}

// 归并
void merge(int seq[], int s1[], int l1, int s2[], int l2)
{
int i = 0, j = 0, k = 0;

while(i < l1 && j < l2) {
if (s1[i] < s2[j])
seq[k++] = s1[i++];
else
seq[k++] = s2[j++];
}

while (i < l1)
seq[k++] = s1[i++];

while (j < l2)
seq[k++] = s2[j++];
}

// 分治递归
void merge_sort_rec(int seq[], int len)
{
if (len < 4) {
sort(seq, seq+len); // 不复杂化了，主要体现以下分治算法和合并排序
}
else {
int l1 = len / 2, l2 = len - l1;

int *pSeq1 = new int[l1];
int *pSeq2 = new int[l2];
memcpy(pSeq1, seq, sizeof(int)*l1);
memcpy(pSeq2, seq+l1, sizeof(int)*l2);

merge_sort_rec(pSeq1, l1); // 分治
merge_sort_rec(pSeq2, l2); // 分治

merge(seq, pSeq1, l1, pSeq2, l2); // 合并

delete[] pSeq1;
delete[] pSeq2;
}
}

//合并排序对外接口
void merge_sort(int seq[], int len)
{
merge_sort_rec(seq, len);
}