我曾试图解决这个问题,但至今失败。这是我第一次处理排序算法,出于学术目的,所以我很可能在某个地方犯了一个简单的错误;不过我一直没能弄明白。
private int[] mergeAndDivide(int[] array) {
if (array.length < 2)
return array;
int[] arrayOne = Arrays.copyOfRange(array, 0, (array.length - 1) / 2);
int[] arrayTwo = Arrays.copyOfRange(array, ((array.length - 1) / 2 + 1), (array.length - 1));
arrayOne = mergeAndDivide(arrayOne);
arrayTwo = mergeAndDivide(arrayTwo);
return merge(arrayOne, arrayTwo);
}
private int[] merge(int[] arrayOne, int[] arrayTwo) {
int[] arrayMerged = new int[arrayOne.length + arrayTwo.length];
int i = 0;
while (i <= arrayOne.length - 1 && i <= arrayTwo.length - 1) {
if (arrayOne[i] > arrayTwo[i])
arrayMerged[i] = arrayTwo[i];
else
arrayMerged[i] = arrayOne[i];
}
int x = i;
while (i <= arrayOne.length - 1) {
arrayMerged[i + arrayTwo.length - 1] = arrayOne[i];
i++;
}
i = x;
while (i <= arrayTwo.length - 1) {
arrayMerged[i + arrayOne.length - 1] = arrayTwo[i];
i++;
}
return arrayMerged;
}
你的代码逻辑似乎不是合并排序.这才是正确的合并排序代码 。
public static void main(String[] args) {
int arr[] = {12, 11, 13, 5, 6, 7};
System.out.println("\nSorted array");
for(int i=0;i<=arr.length-1;i++){
System.out.println("Initial Arr element:"+arr[i]);
}
mergeS(arr, 0, arr.length-1);
System.out.println("\nSorted array");
for(int i=0;i<=arr.length-1;i++){
System.out.println("Sorted Arr element:"+arr[i]);
}
}
public static void mergeS(int[] arr,int startI,int endI){
//System.out.println("StartIndex:"+startI+" EndIndex:"+endI)
if (startI< endI)
{
// Find the middle point
int m = (startI+endI)/2;
// Sort first and second halves
mergeS(arr,startI, m);
mergeS(arr , m+1, endI);
// Merge the sorted halves
merge(arr, startI,m, endI);
}
}
public static void merge(int arr[], int startI, int midpoint, int endI){
// Find sizes of two subarrays to be merged
int n1 = midpoint - startI + 1;
int n2 = endI - midpoint;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[startI + i];
for (int j=0; j<n2; ++j)
R[j] = arr[midpoint + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = startI;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
在除法例程中 Arrays.copyOfRange
to参数是排他性的,这意味着它不会在结果中包含to索引。同样,在合并例程中,你必须使用2个变量来迭代2个数组,我在大多数地方将<=改为<,因为我认为这样看起来很干净。
import java.util.Arrays;
class Solution {
private static int[] mergeAndDivide(int[] array) {
if (array.length < 2) return array;
int[] arrayOne = Arrays.copyOfRange(array, 0, ((array.length - 1) / 2) + 1); // the final index is exclusive meaning it will not be included in the bisected array
int[] arrayTwo = Arrays.copyOfRange(array, ((array.length - 1) / 2 + 1), array.length);
arrayOne = mergeAndDivide(arrayOne);
arrayTwo = mergeAndDivide(arrayTwo);
return merge(arrayOne, arrayTwo);
}
private static int[] merge(int[] arrayOne, int[] arrayTwo) {
int[] arrayMerged = new int[arrayOne.length + arrayTwo.length];
int i = 0;
int j = 0;
while (i < arrayOne.length && j < arrayTwo.length) { // you need 2 variables to index first and second array;
if (arrayOne[i] > arrayTwo[j]) {
arrayMerged[i + j] = arrayTwo[j];
j++;
} else {
arrayMerged[i + j] = arrayOne[i];
i++;
}
}
while (i < arrayOne.length) {
arrayMerged[i + j] = arrayOne[i];
i++;
}
while (j < arrayTwo.length) {
arrayMerged[i + j] = arrayTwo[j];
j++;
}
return arrayMerged;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(mergeAndDivide(new int[]{3, 4, 5, 6, 1})));
}
}
Result : [1, 3, 4, 5, 6]
第二个参数 Arrays.copyOfRange()
是分片结束后第一个元素的索引。使用 array.length / 2
的值,并使用相同的值作为第二个分片的起始索引。
同样地,使用 <
而不要在合并方法中调整长度。还有一个错误:你用同样的索引 i
变成 arrayOne
, arrayTwo
和 arrayMerged
你应该在每个参数数组和合并数组中使用不同的索引。
下面是一个修改后的版本。
private int[] mergeAndDivide(int[] array) {
if (array.length < 2)
return array;
int[] arrayOne = Arrays.copyOfRange(array, 0, array.length / 2);
int[] arrayTwo = Arrays.copyOfRange(array, array.length / 2, array.length);
arrayOne = mergeAndDivide(arrayOne);
arrayTwo = mergeAndDivide(arrayTwo);
return merge(arrayOne, arrayTwo);
}
private int[] merge(int[] arrayOne, int[] arrayTwo) {
int[] arrayMerged = new int[arrayOne.length + arrayTwo.length];
int i = 0, j = 0, k = 0;
while (i < arrayOne.length && j < arrayTwo.length) {
if (arrayOne[i] <= arrayTwo[j])
arrayMerged[k++] = arrayOne[i++];
else
arrayMerged[k++] = arrayTwo[j++];
}
while (i < arrayOne.length) {
arrayMerged[k++] = arrayOne[i++];
}
while (j < arrayTwo.length) {
arrayMerged[k++] = arrayTwo[j++];
}
return arrayMerged;
}