大家好，我是小鸭酱，博客地址为：http://www.cnblogs.com/xiaoyajiang
以下实现归并排序，第一部分含有哨兵（算法来自《算法导论》），第二部分不含哨兵
第一部分，含有哨兵的归并排序：
#include<iostream>
using namespace std;
void myMERGE(int * A, int p, int q, int r)
{
int n1 = q - p + 2;
int n2 = r - q + 1;
int L[n1];
int R[n2];
for(int i = 0; i < n1-1; ++i)
L[i] = A[p + i];
L[n1-1] = INT_MAX;
for(int j = 0; j < n2-1; ++j)
R[j] = A[q + j + 1];
R[n2-1] = INT_MAX;
int i = 0;
int j = 0;
for(int k = p; k <= r; ++k)
A[k] = L[i] < R[j] ? L[i++] : R[j++];
}
void MERGE_SORT(int *A, int p, int r)
{
if(r > p)
{
int q = (r + p) / 2;
MERGE_SORT(A, p, q);
MERGE_SORT(A, q+1, r);
myMERGE(A, p, q, r);
}
}
int main()
{
int b[4] = {4,3,2,1};
MERGE_SORT(b,0,3);
for(int i = 0; i < 4; ++i)
cout << b[i] << endl;
return 0;
}
-----------------------------------------------------
#include<iostream>
using namespace std;
void myMERGE(int *A, int p, int q, int r)
{
int n1 = q - p + 2;
int n2 = r - q + 1;
int L[n1];
int R[n2];
for(int i = 0; i < n1 - 1; ++ i)
{
L[i] = A[p + i];
}
L[n1 - 1] = 0;
for(int j = 0; j < n2 - 1; ++ j)
{
R[j] = A[q + 1 + j];
}
R[n2 - 1] = 0;
int i = 0;
int j = 0;
for(int k = p; k <= r; ++k)
{
A[k] = L[i] > R[j] ? L[i++] : R[j++];
}
}
void MERGE_DESCSORT(int *A, int p, int r)
{
if(r > p)
{
int q = (r + p) / 2;
MERGE_DESCSORT(A, p, q);
MERGE_DESCSORT(A, q + 1, r);
myMERGE(A, p, q, r);
}
}
int main()
{
int b[] = {1,2,3,4,5};
MERGE_DESCSORT(b, 0, 4);
for(int i = 0; i < 5; ++i)
{
cout << b[i] << endl;
}
return 0;
}
第二部分，不含有哨兵的归并排序：
#include<iostream>
using namespace std;
void myMERGE2(int *A, int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int L[n1];
int R[n2];
for(int i = 0; i < n1; ++i)
L[i] = A[p + i];
for(int j = 0; j < n2; ++j)
R[j] = A[q + 1 + j];
int i = 0;
int j = 0;
int k = p;
while(i < n1 && j < n2)
A[k++] = L[i] < R[j]?L[i++]:R[j++];
while(i < n1)
A[k++] = L[i++];
while(j < n2)
A[k++] = R[j++];
}
void MERGE_SORT2(int *A, int p, int r)
{
if(p < r)
{
int q = (r + p) / 2;
MERGE_SORT2(A, p, q);
MERGE_SORT2(A, q + 1, r);
myMERGE2(A, p, q, r);
}
}
int main()
{
int b[] = {5,4,3,2,1};
MERGE_SORT2(b,0,4);
for(int i = 0; i < 5; ++i)
cout << b[i] << endl;
return 0;
}