# C ++中合并排序算法的怪异行为

``````#include <bits/stdc++.h>

using namespace std;

int merge(int *ar, int l, int r) {
int aux[r - l + 1], s1 = 0, s2 = (r - l) / 2 + 1;

for (int i = 0; i < r - l + 1; i++)
aux[i] = ar[l + i];
for (int k = 0; k < r - l + 1; k++) {
if (s1 > ((r - l) / 2))
ar[l + k] = aux[s2++];
else
if (s2 > r)
ar[l + k] = aux[s1++];
else
if (aux[s1] <= aux[s2])
ar[l + k] = aux[s1++];
else
ar[l + k] = aux[s2++];
}
//for (int i = 0; i < 17; i++) cout << ar[i] << " ";
//cout << endl;
return 0;
}

void  mergesort(int *ar, int l, int r) {
if (l >= r)
return;
int mid = (l + r) / 2;
mergesort(ar, l, mid);
mergesort(ar, mid + 1, r);
merge(ar, l, r);
}

int main() {
int ar[] ={ 34, 54, 56, 42, 32, 46, 99, 85, 5, 45, 34, 54, 6, 56, 54, 64, 5 },
l = 0, r = sizeof(ar) / sizeof(int) - 1;
mergesort(ar, l, r);
for (int i = 0; i < r + 1; i++)
cout << ar[i] << " ";
return 0;
}
``````

``````5 5 6 16 16 16 32 16 34 34 16 46 54 54 16 56 99
``````

``````        5 5 6 32 34 34 42 45 46 54 54 54 56 56 56 64 99
``````

[我在这里打印了空格。]

chqrlie

`r`作为最后一个元素的索引传递非常令人困惑在C和C ++中，在最后一个元素之后传递元素的索引是比较惯用`r - l`的，数组的长度也应这样。使用这种方法，就不会出现容易出错`+1`/`-1`调整的情况。

``````#include <iostream>

using namespace std;

void merge(int *ar, int l, int r) {
int len = r - l;
int mid = len / 2;
int s1 = 0, s2 = mid;
int aux[len];

for (int i = 0; i < len; i++)
aux[i] = ar[l + i];
for (int k = l; k < r; k++) {
if (s1 >= mid)
ar[k] = aux[s2++];
else
if (s2 >= len)
ar[k] = aux[s1++];
else
if (aux[s1] <= aux[s2])
ar[k] = aux[s1++];
else
ar[k] = aux[s2++];
}
}

void mergesort(int *ar, int l, int r) {
if (r - l >= 2)
return;
int mid = l + (r - l) / 2;
mergesort(ar, l, mid);
mergesort(ar, mid, r);
merge(ar, l, r);
}

int main() {
int ar[] = { 34, 54, 56, 42, 32, 46, 99, 85, 5, 45, 34, 54, 6, 56, 54, 64, 5 };
int len = sizeof(ar) / sizeof(ar[0]);
mergesort(ar, 0, len);
for (int i = 0; i < len; i++)
cout << ar[i] << " ";
cout << endl;
return 0;
}
``````

0 条评论