我是 Java 的新手，并尝试在 Java 中实现归并排序。但是，即使在多次运行该程序之后，我得到的不是所需的排序输出，而是与输出相同的用户给定输入。如果有人能帮助我理解这种意想不到的行为，我将不胜感激。
import java.io.*;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) throws IOException {
BufferedReader R = new BufferedReader(new InputStreamReader(System.in));
int arraySize = Integer.parseInt(R.readLine());
int[] inputArray = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
inputArray[i] = Integer.parseInt(R.readLine());
}
mergeSort(inputArray);
for (int j = 0; j < inputArray.length; j++) {
System.out.println(inputArray[j]);
}
}
static void mergeSort(int[] A) {
if (A.length > 1) {
int q = A.length / 2;
int[] leftArray = Arrays.copyOfRange(A, 0, q);
int[] rightArray = Arrays.copyOfRange(A, q + 1, A.length);
mergeSort(leftArray);
mergeSort(rightArray);
A = merge(leftArray, rightArray);
}
}
static int[] merge(int[] l, int[] r) {
int totElem = l.length + r.length;
int[] a = new int[totElem];
int i, li, ri;
i = li = ri = 0;
while (i < totElem) {
if ((li < l.length) && (ri < r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i++;
li++;
} else {
a[i] = r[ri];
i++;
ri++;
}
} else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i++;
ri++;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li++;
i++;
}
}
}
}
return a;
}
}
这是您的代码的更正版本：
import java.io.*;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) throws IOException{
BufferedReader R = new BufferedReader(new InputStreamReader(System.in));
int arraySize = Integer.parseInt(R.readLine());
int[] inputArray = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
inputArray[i] = Integer.parseInt(R.readLine());
}
mergeSort(inputArray);
for (int j = 0; j < inputArray.length; j++) {
System.out.println(inputArray[j]);
}
}
static void mergeSort(int[] A) {
if (A.length > 1) {
int q = A.length/2;
//changed range of leftArray from 0-to-q to 0-to-(q-1)
int[] leftArray = Arrays.copyOfRange(A, 0, q-1);
//changed range of rightArray from q-to-A.length to q-to-(A.length-1)
int[] rightArray = Arrays.copyOfRange(A,q,A.length-1);
mergeSort(leftArray);
mergeSort(rightArray);
merge(A,leftArray,rightArray);
}
}
static void merge(int[] a, int[] l, int[] r) {
int totElem = l.length + r.length;
//int[] a = new int[totElem];
int i,li,ri;
i = li = ri = 0;
while ( i < totElem) {
if ((li < l.length) && (ri<r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i++;
li++;
}
else {
a[i] = r[ri];
i++;
ri++;
}
}
else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i++;
ri++;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li++;
i++;
}
}
}
}
//return a;
}
}
当你在
AmergeSort() A = merge(leftArray,rightArray);
这对
inputArraymain()您需要从
mergeSort()merge()static int[] mergeSort(int[] A) {
...
return A;
}
在
main() int[] mergedArray = mergeSort(inputArray);
for (int j = 0; j < mergedArray.length; j++) {
System.out.println(mergedArray[j]);
}
问题是 java 是按值传递而不是按引用传递...当您在合并方法中分配给数组 A 时，您正在更改对 A 的引用的副本而不是对 A 本身的引用。因此，您需要将 A 传递到合并方法中并对 A 进行结构更改。
问题出在这里：
A = merge(leftArray,rightArray);
现在您的合并数组执行此操作：
static int[] merge(int[] l, int[] r) {
int[] a = new int[totElem];
// bunch of code
return a;
}
开始时，A 是对 inputArray 的引用。但是随后您将其重新分配为合并后出现的任何内容。不幸的是，这并没有触及 main 方法中 inputArray 的内容。这基本上是在说“哦，看看你所做的所有工作……把它扔掉！”
你可以用类似的东西改变它
static int[] mergeSort(int[] A) {
// A = merge... // not this
return merge... // use this
}
然后在你的主要方法中，你可以做
int[] merged = mergeSort(inputArray);
for(int i : merged) System.out.println(i);
public class MergeSort{
public static void sort(int[] in){
if(in.length <2) return; //do not need to sort
int mid = in.length/2;
int left[] = new int[mid];
int right[] = new int[in.length-mid];
for(int i=0; i<mid; i++){ //copy left
left[i] = in[i];
}
for(int i=0; i<in.length-mid; i++){ //copy right
right[i] = in[mid+i];
}
sort(left);
sort(right);
merge(left, right, in);
}
private static void merge(int[] a, int[] b, int[] all){
int i=0, j=0, k=0;
while(i<a.length && j<b.length){ //merge back
if(a[i] < b[j]){
all[k] = a[i];
i++;
}else{
all[k] = b[j];
j++;
}
k++;
}
while(i<a.length){ //left remaining
all[k++] = a[i++];
}
while(j<b.length){ //right remaining
all[k++] = b[j++];
}
}
public static void main(String[] args){
int[] a = {2,3,6,4,9,22,12,1};
sort(a);
for(int j=0; j<a.length; j++){
System.out.print(a[j] + " ");
}
}
}
public void sort(int[] randomNumbersArrray)
{
copy = randomNumbersArrray.clone();
mergeSort(0 , copy.length - 1);
}
private void mergeSort(int low, int high)
{
if(low < high)
{
int mid = ((low + high) / 2);
mergeSort(low, mid); //left side
mergeSort(mid + 1, high); // right side
merge(low, mid, high); //combine them
}
}
private void merge(int low, int mid, int high)
{
int temp[] = new int[high - low + 1];
int left = low;
int right = mid + 1;
int index = 0;
// compare each item for equality
while(left <= mid && right <= high)
{
if(copy[left] < copy[right])
{
temp[index] = copy[left];
left++;
}else
{
temp[index] = copy[right];
right++;
}
index++;
}
// if there is any remaining loop through them
while(left <= mid || right <= high)
{
if( left <= mid)
{
temp[index] = copy[left];
left++;
index++;
}else if(right <= high)
{
temp[index] = copy[right];
right++;
index++;
}
}
// copy back to array
for(int i = 0; i < temp.length; i++)
{
copy[low + i] = temp[i];
}
}
package Sorting;
public class MergeSort {
private int[] original;
private int len;
public MergeSort(int length){
len = length;
original = new int[len];
original[0]=10;
original[1]=9;
original[2]=8;
original[3]=7;
original[4]=6;
original[5]=5;
original[6]=4;
original[7]=3;
original[8]=2;
original[9]=1;
int[] aux = new int[len];
for(int i=0;i<len;++i){
aux[i]=original[i];
}
Sort(aux,0,len);
}
public void Sort(int[] aux,int start, int end){
int mid = start + (end-start)/2;
if(start < end){
Sort(aux, start, mid-1);
Sort(aux, mid, end);
Merge(aux, start, mid, end);
}
}
public void Merge(int[] aux, int start, int mid, int end){// while array passing be careful of shallow and deep copying
for(int i=start; i<=end; ++i)
auxilary[i] = original[i];
int i = start;
int k = start;
int j = mid+1;
while(i < mid && j <end){
if(aux[i] < aux[j]){
original[k++] = aux[i++];
}
else{
original[k++] = aux[j++];
}
}
if(i == mid){
while(j < end){
original[k++] = aux[j++];
}
}
if(j == end){
while(i < mid){
original[k++] = aux[i++];
}
}
}
public void disp(){
for(int i=0;i<len;++i)
System.out.print(original[i]+" ");
}
public static void main(String[] args) {
MergeSort ms = new MergeSort(10);
ms.disp();
}
}
上面的代码有点乱 切勿使用名称为“k”、“j”、“m”...的变量，这会使代码非常混乱
以更简单的方式遵循代码...
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
Integer[] itens = {2,6,4,9,1,3,8,7,0};
Integer[] tmp = new Integer[itens.length];
int left = 0;
int right = itens.length - 1;
mergeSort(itens, tmp, left, right);
System.out.println(Arrays.toString(itens));
}
private static void mergeSort(Integer[] itens, Integer[] tmpArray, int left, int right) {
if(itens == null || itens.length == 0 || left >= right){
return;
}
int midle = (left + right) / 2;
mergeSort(itens, tmpArray, left, midle);
mergeSort(itens, tmpArray, midle + 1, right);
merge(itens, tmpArray, left, midle + 1, right);
}
private static void merge(Integer[] itens, Integer[] tmpArray, int left, int right, int rightEnd) {
int leftEnd = right - 1;
int tmpIndex = left;
while (left <= leftEnd && right <= rightEnd){
if (itens[left] < itens[right] ){
tmpArray[tmpIndex++] = itens[left++];
} else {
tmpArray[tmpIndex++] = itens[right++];
}
}
while (left <= leftEnd) { // Copy rest of LEFT half
tmpArray[tmpIndex++] = itens[left++];
}
while (right <= rightEnd) { // Copy rest of RIGHT half
tmpArray[tmpIndex++] = itens[right++];
}
while(rightEnd >= 0){ // Copy TEMP back
itens[rightEnd] = tmpArray[rightEnd--];
}
}
}
不妨补充一下我对此的看法： 获取两个 int 数组并将它们合并。 其中“结果”是大小为 a.length + b.length
的数组public static void merge( int[] a, int[] b, int[] result )
{
int i = 0, j = 0;
while ( true )
{
if ( i == a.length )
{
if ( j == b.length )
return;
result[ i + j ] = b[ j ];
j++;
}
else if ( j == b.length )
{
result[ i + j ] = a[ i ];
i++;
}
else if ( a[ i ] < b[ j ] )
{
result[ i + j ] = a[ i ];
i++;
}
else
{
result[ i + j ] = b[ j ];
j++;
}
}
}
public class MyMergeSort {
private int[] array;
private int[] tempMergArr;
private int length;
public static void main(String a[]){
int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
MyMergeSort mms = new MyMergeSort();
mms.sort(inputArr);
for(int i:inputArr){
System.out.print(i);
System.out.print(" ");
}
}
public void sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergArr = new int[length];
doMergeSort(0, length - 1);
}
private void doMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Below step sorts the left side of the array
doMergeSort(lowerIndex, middle);
// Below step sorts the right side of the array
doMergeSort(middle + 1, higherIndex);
// Now merge both sides
mergeParts(lowerIndex, middle, higherIndex);
}
}
private void mergeParts(int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergArr[i] <= tempMergArr[j]) {
array[k] = tempMergArr[i];
i++;
} else {
array[k] = tempMergArr[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempMergArr[i];
k++;
i++;
}
}
}
非常简单易懂
static void sort(char[] data) {
int length = data.length;
if (length < 2)
return;
int mid = length / 2;
char[] left = new char[mid];
char[] right = new char[length - mid];
for(int i=0;i<mid;i++) {
left[i]=data[i];
}
for(int i=0,j=mid;j<length;i++,j++) {
right[i]=data[j];
}
sort(left);
sort(right);
merge(left, right, data);
}
static void merge(char[] left, char[] right, char[] og) {
int i = 0, j = 0, k = 0;
while(i < left.length && j < right.length) {
if (left[i] < right[j]) {
og[k++] = left[i++];
} else {
og[k++] = right[j++];
}
}
while (i < left.length) {
og[k++] = left[i++];
}
while (j < right.length) {
og[k++] = right[j++];
}
}
我有一个并行版本的归并排序。我受益于 RecursiveAction 和 ForkJoinPool。请注意，工人的数量可以设置为常量。但是，我将其设置为机器上可用处理器的数量。
import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
public class ParallelMergeSorter {
private int[] array;
public ParallelMergeSorter(int[] array) {
this.array = array;
}
public int[] sort() {
int numWorkers = Runtime.getRuntime().availableProcessors(); // Get number of available processors
ForkJoinPool pool = new ForkJoinPool(numWorkers);
pool.invoke(new ParallelWorker(0, array.length - 1));
return array;
}
private class ParallelWorker extends RecursiveAction {
private int left, right;
public ParallelWorker(int left, int right) {
this.left = left;
this.right = right;
}
protected void compute() {
if (left < right) {
int mid = (left + right) / 2;
ParallelWorker leftWorker = new ParallelWorker(left, mid);
ParallelWorker rightWorker = new ParallelWorker(mid + 1, right);
invokeAll(leftWorker, rightWorker);
merge(left, mid, right);
}
}
private void merge(int left, int mid, int right) {
int[] leftTempArray = Arrays.copyOfRange(array, left, mid + 1);
int[] rightTempArray = Arrays.copyOfRange(array, mid + 1, right + 1);
int leftTempIndex = 0, rightTempIndex = 0, mergeIndex = left;
while (leftTempIndex < mid - left + 1 || rightTempIndex < right - mid) {
if (leftTempIndex < mid - left + 1 && rightTempIndex < right - mid) {
if (leftTempArray[leftTempIndex] <= rightTempArray[rightTempIndex]) {
array[mergeIndex] = leftTempArray[leftTempIndex];
leftTempIndex++;
} else {
array[mergeIndex] = rightTempArray[rightTempIndex];
rightTempIndex++;
}
} else if (leftTempIndex < mid - left + 1) {
array[mergeIndex] = leftTempArray[leftTempIndex];
leftTempIndex++;
} else if (rightTempIndex < right - mid) {
array[mergeIndex] = rightTempArray[rightTempIndex];
rightTempIndex++;
}
mergeIndex++;
}
}
}
}
public class MergeTwoSortedArray {
public void approach_2(int[] arr1, int[] arr2) {
List<Integer> result = IntStream.concat(Arrays.stream(arr1), Arrays.stream(arr2)).boxed().sorted()
.collect(Collectors.toList());
System.out.println(result);
}
public void approach_3(Integer[] arr1, Integer[] arr2) {
List<Integer> al1 = Arrays.asList(arr1);
List<Integer> al2 = Arrays.asList(arr2);
List<Integer> result = new ArrayList<>();
int i = 0, j = 0;
while (i < al1.size() && j < al2.size()) {
if (al1.get(i) < al2.get(j)) {
result.add(al1.get(i));
i++;
} else {
result.add(al2.get(j));
j++;
}
}
while (i < al1.size()) {
result.add(al1.get(i));
i++;
}
while (j < al2.size()) {
result.add(al2.get(j));
j++;
}
System.out.println(result);
}
public static void main(String[] args) {
MergeTwoSortedArray obj = new MergeTwoSortedArray();
int[] arr1 = { 3, 6, 76, 85, 91 };
int[] arr2 = { 1, 6, 78, 89, 95, 112 };
obj.approach_2(arr1, arr2);
Integer[] arr3 = { 3, 6, 76, 85, 91 };
Integer[] arr4 = { 1, 6, 78, 89, 95, 112 };
obj.approach_3(arr3, arr4);
}
}