归并算法的中心是归并两个已经有序的数组

1. 思想演示：非递归

public static void merge( int[] arrayA, int sizeA,
int[] arrayB, int sizeB,
int[] arrayC )
{
int aDex=0, bDex=0, cDex=0;

while(aDex < sizeA && bDex < sizeB) // neither array empty
if( arrayA[aDex] < arrayB[bDex] )
arrayC[cDex++] = arrayA[aDex++];
else
arrayC[cDex++] = arrayB[bDex++];

while(aDex < sizeA) // arrayB is empty,
arrayC[cDex++] = arrayA[aDex++]; // but arrayA isn‘t

while(bDex < sizeB) // arrayA is empty,
arrayC[cDex++] = arrayB[bDex++]; // but arrayB isn‘t
} // end merge()

2. 算法实现：递归

public void mergeSort() // called by main()
{ // provides workspace
long[] workSpace = new long[nElems];
recMergeSort(workSpace, 0, nElems-1);
}
//-----------------------------------------------------------
private void recMergeSort(long[] workSpace, int lowerBound,
int upperBound)
{
if(lowerBound == upperBound) // if range is 1,
return; // no use sorting
else
{ // find midpoint
int mid = (lowerBound+upperBound) / 2;
// sort low half
recMergeSort(workSpace, lowerBound, mid);
// sort high half
recMergeSort(workSpace, mid+1, upperBound);
// merge them
merge(workSpace, lowerBound, mid+1, upperBound);
} // end else
} // end recMergeSort()
//-----------------------------------------------------------
private void merge(long[] workSpace, int lowPtr,
int highPtr, int upperBound)
{
int j = 0; // workspace index
int lowerBound = lowPtr;
int mid = highPtr-1;
int n = upperBound-lowerBound+1; // # of items

while(lowPtr <= mid && highPtr <= upperBound)
if( theArray[lowPtr] < theArray[highPtr] )
workSpace[j++] = theArray[lowPtr++];
else
workSpace[j++] = theArray[highPtr++];

while(lowPtr <= mid)
workSpace[j++] = theArray[lowPtr++];

while(highPtr <= upperBound)
workSpace[j++] = theArray[highPtr++];

for(j=0; j<n; j++)
theArray[lowerBound+j] = workSpace[j];
} // end merge()
//-----------------------------------------------------------

Java 归并排序,布布扣,bubuko.com

Java 归并排序