c-合并排序-得到不正确的结果和损坏的数据(复制元素)

Question

我试图实现基本的Merge Sort，但出现了问题，它错误地复制了输入数组中的一些元素，甚至更改了一些元素，因此输出数组已损坏。我使用tmp[]作为全局声明的数组指针(全局声明中的long *tmp;->(我缺少什么或做错了什么？

此外，如何提高该算法的时间复杂度？

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void merge(long *arr, int l, int m, int r);
void mergeSort(long *arr, int l, int r);
//Global Declarations
long *tmp;
//Merge Sort
void Merge_Sort(long *Array, int Size) {
tmp = malloc(sizeof(long) * Size);
mergeSort(Array, 0, Size - 1);
}
//Merge Sort helper function
void mergeSort(long *arr, int l, int r) {
if (l >= r)
return;
// divide the array into two arrays
// call mergeSort with each array
// merge the two arrays into one
int m = l + ((r - l) / 2; //integer overflow
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
} 
//merge function
static void merge(long *arr, int l, int m, int r) {   
//tmp[] is a global array with the same size as arr[]
memcpy(&tmp[l], &arr[l], m - l + 1); //copy left subarray to tmp
memcpy(&tmp[m + 1], &arr[m + 1], r - m); //copy right subarray to tmp
int i = l;
int j = m + 1;
for (int k = l; k <= r; k++) {
if (i > m)
arr[k] = tmp[j++]; //if the left sub-array is exhausted
else
if (j > r)
arr[k] = tmp[i++]; //if the right sub-array is exhausted
else
if (tmp[j] < tmp[i])
arr[k] = tmp[j++]; //compare the current values
else
arr[k] = tmp[i++];
}
}
int main() {
long array[10] = {
-3153274050600690459,
6569843820458972605,
-6837880721686463424,
1876340121514080353,
-1767506107468465601,
-1913444019437311076,
-426543213433372251,
6724963487502039099,
-1272217999899710623,
3399373277871640777,
};
Merge_Sort(array, 10);
for (int i = 0; i < 10; i++) {
printf("%ldn". array[i]);
}
return 0;
}

输出(不正确(：

-1913444019437311076-426543213433722511404649812280951403885325237099428549285996894285492861503-17675061074684656016724963487502039099-12722179998997106233399373277871640777

预期输出：

-6837880721686463424-3153274050600690459-1913444019437311076-1767506107468465601-1272217999899710623-426543213433722511876340121514080353339937327787164077765698438204589726056724963487502039099

Answer 1

merge函数没有复制正确的字节数：

memcpy(&tmp[l], &arr[l], m - l + 1); //copy left subarray to tmp
memcpy(&tmp[m + 1], &arr[m + 1], r - m); //copy right subarray to tmp

您必须通过元素数量乘以元素大小来计算正确的字节数。还需要注意的是，左右子阵列是连续的，因此只需写入：

memcpy(&tmp[l], &arr[l], sizeof(*tmp) * (r - l + 1));

还有其他问题：

• 避免使用全局变量tmp，只需将其作为额外参数传递给mergeSort
• 必须在mergeSort()完成后释放临时数组

这是一个修改后的版本：

#include <stdlib.h>
#include <string.h>
//merge function
static void merge(long *arr, int l, int m, int r, long *tmp) {   
//tmp[] is a global array with the same size as arr[]
memcpy(&tmp[l], &arr[l], sizeof(*tmp) * (r - l + 1));
for (int k = l, i = l, j = m + 1; k <= r; k++) {
if (i <= m && (j > r || tmp[i] <= tmp[j]))
arr[k] = tmp[i++];
else
arr[k] = tmp[j++];
}
}
//Merge Sort helper function
static void mergeSort(long *arr, int l, int r, long *tmp) {
if (l < r) {
// divide the array into two arrays
// call mergeSort with each array
// merge the two arrays into one
int m = l + (r - l) / 2; //avoid integer overflow
mergeSort(arr, l, m, tmp);
mergeSort(arr, m + 1, r, tmp);
merge(arr, l, m, r);
}
} 
//Merge Sort
void Merge_Sort(long *array, int size) {
long *tmp = malloc(sizeof(*tmp) * size);
mergeSort(array, 0, Size - 1, tmp);
free(tmp);
}

关于您的另一个问题：如何提高此算法的时间复杂性

合并排序算法的时间复杂度为O(N*log(N((，与集合分布无关。这被认为是通用数据的最佳选择。如果你的数据恰好具有已知的特定特征，那么其他算法的复杂度可能会更低。

• 如果所有值都在一个小范围内，计数排序是一个很好的选择
• 如果存在许多重复项和少量K个不同的唯一值，则复杂性可以降低到O(N+K.log(K((
• 整数值可以使用基数排序进行排序，这对于大型数组更有效
• 如果数组几乎已排序，则插入排序或修改合并排序(通过一个初始测试来测试左右子数组是否已按顺序排列(也可以更快
• 使用Timsort可以使许多非随机分布的执行速度更快

以下是long阵列的radix_sort()的实现：

#include <stdlib.h>
#include <string.h>
void radix_sort(long *a, size_t size) {
size_t counts[sizeof(*a)][256] = {{ 0 }}, *cp;
size_t i, sum;
unsigned int n;
unsigned long *tmp, *src, *dst, *aa;
dst = tmp = malloc(size * sizeof(*a));
src = (unsigned long *)a;
for (i = 0; i < size; i++) {
unsigned long v = src[i] + (unsigned long)VAL_MIN;
for (n = 0; n < sizeof(*a) * 8; n += 8)
counts[n >> 3][(v >> n) & 255]++;
}
for (n = 0; n < sizeof(*a) * 8; n += 8) {
cp = &counts[n >> 3][0];
for (i = 0, sum = 0; i < 256; i++)
cp[i] = (sum += cp[i]) - cp[i];
for (i = 0; i < size; i++)
dst[cp[((src[i] + (unsigned long)VAL_MIN) >> n) & 255]++] = src[i];
aa = src;
src = dst;
dst = aa;
}
if (src == tmp)
memcpy(a, src, size * sizeof(*a));
free(tmp);
}