关于归并排序的一种变型算法

算法"/>

关于归并排序的一种变型算法

关于归并排序的一种变型算法

普通归并排序主要代码如下：

void Merge(int* num,int left,int mid,int right)
{int temp[right - left + 1];int l = left;int r = mid + 1;int index = 0;while(l <= mid && r <= right){if(num[l] < num[r])temp[index++] = num[l++];else temp[index++] = num[r++];}while(l <= mid)temp[index++] = num[l++];while(r <= right)temp[index++] = num[r++];for(int i = 0;i < index;i++)num[i + left] = temp[i];
}
void MergeSort(int* num,int left,int right)
{if(left >= right)return;int mid = (left + right) / 2;MergeSort(num,left,mid);MergeSort(num,mid + 1,right);Merge(num,left,mid,right);
}

该归并排序在Merge的过程中，因为temp数组的开辟浪费了较多的空间，另外将temp复制到num的过程中也消耗了大量的时间。

因此，现在利用num数组的索引来在Merge的过程中对数组进行排序，从而达到减少空间以及时间的效果。

说明：

1.link[i]是在num[i]后面的第一个数（递增排序即为第一个比num[i]大的数）在num中的索引，最大数对应的link则为0。

2.num从索引1开始存储数字

例如：

num数组如下：
index      1  2  3  4  5 
num[index] 21 39 47 12 28对应的link数组为：
index       0 1 2 3 4 5
link[index] 4 5  0 1 2

具体代码如下：

int link[length + 1]//length为num数组的长度，link[0]是哨兵结点，存储某分段的起始索引
int Merge(int* num,int left,int mid)
{int l = left;int r = mid;int k = 0;while(l != 0 && m != 0){if(num[l] < num[m]){link[k] = l;k = l;l = link[l];}else{link[k] = m;k = m;m = link[m];}}if(l == 0)link[k] = m;else link[k] = l;return link[0];
}
int MergeSort(int* num,int left,int right)
{if(left >= right)return left;int mid = (left + right) / 2;int l = MergeSort(num,left,mid);int m = MergeSort(num,mid + 1,right);int out = Merge(num,l,m);return out;
}