归并排序

浏览数：25 / 时间：2015年06月08日

技术分享

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);
        }
    }

void Merge(int* pDataArray,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];
}

技术分享

/******************************************************** 
*函数名称：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);  
}