//归并排序
void _mergeSort(int* a, int* tmp, int begin, int end)
{
if (begin >= end)
return;
int mid = (begin + end) >> 1;
_mergeSort(a, tmp, begin, mid);
_mergeSort(a, tmp, mid + 1, end);
int curL = begin, curR = mid + 1;
int i = begin;
//左右区间的较小值依次放入tmp中
while (curL <= mid && curR <= end)
{
if (a[curL] < a[curR])
tmp[i++] = a[curL++];
else
tmp[i++] = a[curR++];
}
while (curL <= mid)
{
tmp[i++] = a[curL++];
}
while (curR <= end)
{
tmp[i++] = a[curR++];
}
//此时在tmp中左右区间已合并为有序 将tmp的数据拷贝到原数组
for (i = begin; i <= end; i++)
{
a[i] = tmp[i];
}
}
void mergeSort(int* a, int begin, int end)//递归实现
{
int* tmp = (int*)malloc((end - begin + 1) * sizeof (int));
//为了避免每次递归都malloc一块空间 所以封装一个子函数用于递归
_mergeSort(a, tmp, begin, end);
free(tmp);
}
void mergeSort(int* a, int begin, int end)//非递归实现
{
if (begin >= end)
return;
int n = end - begin + 1;
int* tmp = (int*)malloc(n * sizeof (int));
if (tmp == NULL)
{
printf("mergeSort: malloc failed\n");
return;
}
int gap = 1;
while (gap < n)//如果这里写gap <= n / 2 当数组元素个数为奇数时gap可能会少迭代一次
{
for (int i = 0; i < n; i += 2 * gap)
{
if (i + gap >= n)//第二个区间不存在 (此时不管第一个区间是否完整都不用归并了)
break;
//到这里第一个区间存在且完整 第二个区间存在但可能不完整需要处理一下
int curL = i, curR = i + gap;
int endL = i + gap - 1, endR = i + 2 * gap - 1;
if (endR >= n)//对第二个区间的右边界进行修正
endR = n - 1;
int j = i;
while (curL <= endL && curR <= endR)
{
if (a[curL] < a[curR])
tmp[j++] = a[curL++];
else
tmp[j++] = a[curR++];
}
while (curL <= endL)
{
tmp[j++] = a[curL++];
}
while (curR <= endR)
{
tmp[j++] = a[curR++];
}
//tmp数据拷贝回原数组
for (j = i; j <= endR; j++)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
}
int main()
{
//int arr[] = { 9, 4, 5, 3, 7, 1, 8, 2, 6, 10 };
int arr[] = { 9, 4, 5, 4, 7, 1, 8, 1, 2, 6, 3, 10, -2 };
mergeSort(arr, 0, sizeof arr / sizeof (int) - 1);
printArray(arr, sizeof arr / sizeof (int));
return 0;
}
