我在 Java 中实现了一种三向排序算法。说我以下数组：
int myArray[] = {8,3,5,7,9,2,3,5,5,6}
2 3 3 5 5 5 6 7 8 9显然，我需要成为。除了“2”之外，我的算法正在运行。事实上，我得到以下输出：
3 3 5 5 5 6 7 2 8 9
我不知道为什么...
/*
* DESCRIPTION OF mergeThreeWay ALGORITHM
*
* merges sorted subarrays A[start...firstThird], A[firstThird+1,secondThird], and A[secondThird+1,stop]
*
* There are 3 possible cases when one merges :
* 1) all 3 sub-arrays have elements left
* 2) only 2 sub-arrays have elements left
* 3) only 1 sub-arrays have elements
*
* What action to take?
* For case 1) select the smallest element from the 3 sub-arrays and add it to the temporary array
* 2) select the smallest element from the 2 sub-arrays and add it to the temporary array
* 3) this sub-array is sorted - add all elements to the temporary array
*
* Finally, copy the temporary array to the original array
*
* The algorithm uses while loops to iterate trough the sub-arrays until one sub-array has no elements left (all of its elements have been copied to the temp array)
*/
public static void mergeThreeWay(int A[], int start, int firstThird, int secondThird, int stop) {
int p1 = start;
int p2 = firstThird;
int p3 = secondThird;
int tmp[] = new int[A.length]; // I need a temporary array of the same size as A because the sub-arrays keep their index, for example, a sub-array would look like this : [0, 0, 0, 0, 2, 9, 0, 0, 0, 0]
int tmpIndex = start;
// As long as tmpIndex as not reached the end of the array, execute the loop
while(tmpIndex <= stop) {
// Get the smallest elements of the three sub-arrays
while (p1 < firstThird && p2 < secondThird && p3 <= stop) {
if (A[p1] <= A[p2] && A[p1] <= A[p3]) {
tmp[tmpIndex++] = A[p1++];
}
else if (A[p2] <= A[p1] && A[p2] <= A[p3]) {
tmp[tmpIndex++] = A[p2++];
}
else if (A[p3] <= A[p1] && A[p3] <= A[p2]) {
tmp[tmpIndex++] = A[p3++];
} else {
tmpIndex++;
}
}
// Get the smallest elements of the two remaining sub-arrays
while (p1 < firstThird && p2 < secondThird) {
if (A[p1] <= A[p2]){
tmp[tmpIndex++] = A[p1++];
} else{
tmp[tmpIndex++] = A[p2++];
}
}
while (p1 < firstThird && p3 < stop) {
if (A[p1] <= A[p3]) {
tmp[tmpIndex++] = A[p1++];
} else {
tmp[tmpIndex++] = A[p3++];
}
}
while (p2 < secondThird && p3 < stop) {
if (A[2] <= A[p3]) {
tmp[tmpIndex++] = A[p2++];
} else {
tmp[tmpIndex++] = A[p3++];
}
}
// Complete with the remaining elements
while (p1 < firstThird) tmp[tmpIndex++] = A[p1++];
while (p2 < secondThird) tmp[tmpIndex++] = A[p2++];
while (p3 <= stop) tmp[tmpIndex++] = A[p3++];
tmpIndex++;
}
System.out.println(Arrays.toString(tmp));
for(int k=start; k <= stop; k++) {
A[k] = tmp[k];
}
}
主要方法
public static void main (String args[]) throws Exception {
int myArray[] = {8,3,5,7,9,2,3,5,5,6}; // an example array to be sorted. You'll need to test your code with many cases, to be sure it works.
mergeSortThreeWay(myArray,0,myArray.length-1);
System.out.println("Sorted array is:\n");
for (int i=0;i<myArray.length;i++) {
System.out.print(myArray[i]+" ");
}
}
}
合并排序三路
// sorts A[start...stop]s the same as the element at
public static void mergeSortThreeWay(int A[], int start, int stop) {
if(start < stop) {
// DIVIDE
int firstThird = start + (stop - start) / 3;
int secondThird = start + 2 * (stop - start) / 3;
// CONQUER
mergeSortThreeWay(A, start, firstThird); // A[start..midLeft] SORTED
mergeSortThreeWay(A, firstThird+1, secondThird); // A[midLeft..midRight] SORTED
mergeSortThreeWay(A, secondThird+1, stop); // A[midRight..stop] SORTED
// MERGER
mergeThreeWay(A, start, firstThird, secondThird, stop);
}
}