赞
踩
归并排序(Merge Sort) 是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并排序利用二路归并来进行排序的一种算法,通过将原数列分割成两个子序列,再对子序列进行同样的分割操作,直到子序列有序,再不断地通过二路归并将两个有序的子序列合并,最后合并成一个完整的序列。归并排序有递归和非递归的写法。
最好和最坏情况时间复杂度都为
O
(
n
log
n
)
\ O(n \log n)
O(nlogn),因为归并时并不会因数列已排好序而减少操作,不能辨别数列已有序的情况。
目标是将一个数列排序,递归的写法是将原数列分成两个长度差不多的子数列列,然后分别进行排序,再将两个排好序的数列归并成一个新的有序数列。这个对子序列排序就是一个规模减半的原问题。
每个数列都拆成两半分别排序,当子数列只剩下一个元素的时候就已经排好了,不用继续拆分了,这是递归边界。
关于中间位置mid的求法,另一种是
(
l
e
f
t
+
r
i
g
h
t
)
/
2
(left + right) / 2
(left+right)/2, 这个 left 和 right 相加是有可能溢出的,虽然一般不可能,因为int型最大值为
2
31
−
1
\ 2^{31}-1
231−1, 溢出需要数组大小超过
2
30
\ 2^{30}
230, 这时数组要占4G内存。但是在参数合法时,应该保证没问题,所以使用了
m
i
d
=
l
e
f
t
+
(
r
i
g
h
t
−
l
e
f
t
)
/
2
mid = left + (right - left) / 2
mid=left+(right−left)/2, 这样在left和right很大时计算就不会溢出。
void mergeSort(int a[], int left, int right)
{
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
因为开辟内存是在 merge() 内部的,所以排序时将会频繁开辟和释放内存,这就耗费了很多时间,实际只需要一个和原来数组一样大的临时数组即可。为避免这个问题,可以先开辟一个临时数组,然后递归排序交给另一个函数去做。
现在修改了 merge(), 不在里面另外开辟临时数组,而是借助外面开辟好的。doMergeSort() 才是实际递归归并排序的,同样传入一个临时数组首地址。mergeSort() 开辟一个临时数组,然后传给 doMergeSort()。这样就不用
void merge(int a[], int left, int mid, int right, int tempArray[]) { int lenA = mid - left + 1, lenTemp = right - left + 1; //归并到临时数组中 int ia = left, ib = mid + 1; for (int k = left; k <= right; k++) { if ((ib > right) || (ia <= mid) && (a[ia] <= a[ib])) tempArray[k] = a[ia++]; else tempArray[k] = a[ib++]; } //拷贝回数组a for (int i = left; i <= right; i++) a[i] = tempArray[i]; } void doMergeSort(int a[], int left, int right, int tempArray[]) { if (left < right) { int mid = left + (right - left) / 2; doMergeSort(a, left, mid, tempArray); doMergeSort(a, mid + 1, right, tempArray); merge(a, left, mid, right, tempArray); } } void mergeSort(int a[], int length) { int* tempArray = (int*)malloc(length * sizeof(int)); doMergeSort(a, 0, length - 1, tempArray); free(tempArray); }
递归写法比较简单,但是函数调用耗费的时间也比较多,非递归写法可以更快。
非递归写法是对数列进行分段,每段从1开始,然后每两段进行归并。之后每段的长度倍增,再进行归并,如此循环,直到分段的长度不小于原数列长度为止。
void mergeSortNonRecursion(int a[], int length)
{
int* tempArray = (int*)malloc(length * sizeof(int));
for (int len = 1; len < length; len *= 2) {
int mergeLen = 2 * len;
for (int i = 0; i + len < length; i += mergeLen) {
int right = (i + mergeLen <= length) ? (i + mergeLen-1) : (length - 1);
merge(a, i, i + len - 1, right, tempArray);
}
}
free(tempArray);
}
归并排序的时间复杂度虽然为
O
(
n
l
g
n
)
\ O(n lg n)
O(nlgn), 但是系数比较大。
插入排序最坏情况下时间复杂度为
O
(
n
2
)
\ O(n^2)
O(n2), 最好情况下为
O
(
n
)
\ O(n)
O(n), 系数较小,在数组长度较小时,使用插入排序会更快。所以在递归时,当子数列较小时,可以用插入排序来代替归并排序来加速。这个较小可以选取
l
o
g
2
(
n
)
\ log_2(n)
log2(n)左右,我这里测试乘0.9更好
emsp; 因为上面的插入排序是void insertionSort(int a[], int length), 参数是数组长度而不是范围,所以首地址应为 a + left, 数组长度为 right - left +1
int lowBound = (int)(log2(length)*0.9); if (lowBound < 4) lowBound = 4; void doMergeSort(int a[], int left, int right, int tempArray[], int lowBound) { if (left < right) { //数组长度不超过16时用插入排序代替归并排序 if (right - left + 1 <= lowBound) insertionSort(a +left, right - left + 1); else { int mid = left + (right - left) / 2; doMergeSort(a, left, mid, tempArray); doMergeSort(a, mid + 1, right, tempArray); merge(a, left, mid, right, tempArray); } } }
经过测试(单次测试,非平均), 加速后还是能快一点的,递归和非递归加速后的时间相差不多。 log a n = log n + log a \log an = \log n + \log a logan=logn+loga,增长量为常数,所以当数据量 n n n很大的时候,增长a倍, a n log a n n log n = a + a log a log n ≈ 1 \frac{an \log an}{n \log n} = a +\frac{a \log a}{\log n} \approx 1 nlognanlogan=a+lognaloga≈1,看起来就像是线性的。
数组长度 | 50万 | 100万 | 200万 | 400万 | 800万 |
---|---|---|---|---|---|
递归归并排序(频繁开辟内存) | 259ms | 520ms | 1057 ms | 2141ms | 4225ms |
递归归并排序 | 104ms | 214 ms | 417 ms | 864 ms | 1744ms |
非递归归并排序 | 85ms | 175 ms | 358ms | 717 ms | 1471ms |
加速的递归归并排序 | 68ms | 145 ms | 290 ms | 582 ms | 1209 ms |
上面对两个有序序列进行归并时,并没有考虑一种情况,那就是左边最大值小于等于左边最小值,这种情况说明已经有序,无需进行多余的归并操作。
所以只在左边最大值大于左边最小值时才合并:
if (a[mid] > a[mid+1])
merge(a, left, mid, right)
这避免了很多无效的归并操作,可以提升一部分速度。
上面的归并中,是先将数组归并到辅助数组中,然后再复制回原数组。其实这没有必要。因为归并到辅助数组后,把辅助数组看作原数组,把原数组看作辅助数组就好了。
递归算法的的话就需要一个参数来标记归并方向。非递归写法就更适合了,因为都是归并方向都是统一的。
即采用 非递归 + 角色互换 + 小数组用插入替换 + 测试数组有序,因为 角色互换必须往另一个数组复制,所以避免不了多余的复制。但是当数组有序时,直接复制即可,无需归并,避免了归并时的比较操作。
最终,800万长度的数组750ms, 远胜于加速递归的 1200ms。
//用到的插入排序 void insertSort(int a[], int length) { for (int i = 0; i < length; i++) { int val = a[i], j; for (j = i - 1; j >= 0 && a[j] > val; j--) { a[j + 1] = a[j]; } a[j + 1] = val; } } //无复制的归并 void mergeNoCopy(int src[], int left, int mid, int right, int dest[]) { //归并到临时数组中 int ia = left, ib = mid + 1; for (int k = left; k <= right; k++) { if ((ib > right) || (ia <= mid) && (src[ia] <= src[ib])) dest[k] = src[ia++]; else dest[k] = src[ib++]; } } void mergeSort(int a[], int length) { int* tempArray = (int*)malloc(length * sizeof(int)); int *src = a, *dest = tempArray, *t = nullptr; int minStep = (int)(log(length)); if (minStep < 4) minStep = 4; //小数组用插入代替 for (int begin = 0; begin < length; begin += minStep) { int end = (begin + minStep < length) ? (begin + minStep) : length; insertSort(a + begin, end - begin); } for (int len = minStep; len < length; len += len) { int mergeLen = len + len; for (int left = 0; left < length; left += mergeLen) { int right = (left + mergeLen <= length) ? (left + mergeLen - 1) : (length - 1); //有序则避免归并 if (left + len >= length || a[left + len - 1] <= a[left + len]) memcpy(dest + left, src + left, sizeof(int) * (right - left + 1)); else mergeNoCopy(src, left, left + len - 1, right, dest); } t = src; src = dest; dest = t; } //归并到临时数组要复制回来 if (src != a) memcpy(a, tempArray, sizeof(int) * length); free(tempArray); }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。