点击刷新
public static void mergSort(Comparable[] data,int min,int max){
int mid = (min + max)/2;
//递归的过程
if(max > min){
mergSort(data,min,mid);
mergSort(data,mid+1,max);
merge(data,min,mid,max);
}
}
//支持方法：合并2个有序集，借助于申请一个与两个有序集大小之和相等的空间。
public static void merge(Comparable[] data,int min,int mid,int max){
Comparable[] temp = new
Comparable[max+1];
//Comparable[] temp = new Comparable[max - min + 1];错误！！！
int begin1 = min;
int begin2 = mid + 1;
int index = min;//注意index是从min开始的！！！
while(begin1 <= mid &&
begin2 <= max){
if(data[begin1].compareTo(data[begin2])
< 0)
temp[index++] =
data[begin1++];
else
temp[index++] = data[begin2++];
}
if(begin1 > mid)//左边走完
for(int i = begin2;i <= max;i++)
temp[index++] = data[i];
if(begin2 > max)//右边走完
for(int i = begin1;i <= mid;i++)
temp[index++] = data[i];
for(int i = min;i <= max;i++)//对应的位置！！！！，复制临时数组
data[i] = temp[i];
}
}
/******************************************************** *函数名称：Merge *参数说明：pDataArray 无序数组； * int *pTempArray 临时存储合并后的序列 * bIndex 需要合并的序列1的起始位置 * mIndex 需要合并的序列1的结束位置 并且作为序列2的起始位置 * eIndex 需要合并的序列2的结束位置 *说明： 将数组中连续的两个子序列合并为一个有序序列 *********************************************************/ void Merge(int* pDataArray, int *pTempArray, int bIndex, int mIndex, int eIndex) { int mLength = eIndex - bIndex; //合并后的序列长度 int i = 0; //记录合并后序列插入数据的偏移 int j = bIndex; //记录子序列1插入数据的偏移 int k = mIndex; //记录子序列2掺入数据的偏移 while (j < mIndex && k < eIndex) { if (pDataArray[j] <= pDataArray[k]) { pTempArray[i++] = pDataArray[j]; j++; } else { pTempArray[i++] = pDataArray[k]; k++; } } if (j == mIndex) //说明序列1已经插入完毕 while (k < eIndex) pTempArray[i++] = pDataArray[k++]; else //说明序列2已经插入完毕 while (j < mIndex) pTempArray[i++] = pDataArray[j++]; for (i = 0; i < mLength; i++) //将合并后序列重新放入pDataArray pDataArray[bIndex + i] = pTempArray[i]; } /******************************************************** *函数名称：BottomUpMergeSort *参数说明：pDataArray 无序数组； * iDataNum为无序数据个数 *说明： 自底向上的归并排序 *********************************************************/ void BottomUpMergeSort(int* pDataArray, int iDataNum) { int *pTempArray = (int *)malloc(sizeof(int) * iDataNum); //临时存放合并后的序列 int length = 1; //初始有序子序列长度为1 while (length < iDataNum) { int i = 0; for (; i + 2*length < iDataNum; i += 2*length) Merge(pDataArray, pTempArray, i, i + length, i + 2*length); if (i + length < iDataNum) Merge(pDataArray, pTempArray, i, i + length, iDataNum); length *= 2; //有序子序列长度*2 } free(pTempArray); }
© 著作权归作者所有
发表评论
