Java中的归并排序

什么是归并排序？

合并排序是使用“分而治之”技术对数据进行排序的最常见算法。在该算法中，问题被分成子问题，然后排序后将它们合并在一起。假设我们有一个未排序的数字列表，这是某个主题的班级结果。要按升序对它们进行排序，我们需要将它们放在从低到高开始的列表中。在此合并排序算法中，列表将被分成更小的列表，以升序对它们进行排序，然后合并结果以便更好地理解。Java 中的归并排序可以通过数组 {6,9,8,2,4,1} 的示例来解释，将其视为 10 类测试的结果。（结果的）数组将被重复划分分成更小的块，直到它们的大小为 1。然后在对数字进行排序的同时进行合并过程。这将为我们提供从最低分到最高分的结果。 该数组将分为两个数组，每个数组包含 3 个元素，如下面步骤 2中所示，并继续划分，直到在步骤 4中达到统一。然后，合并排序算法开始一步一步地对数字进行排序（步骤 5 ），然后在步骤 6 和 7中将数字合并为一个更大的数组。

执行

在实现中，我们将用 Java 编写合并排序算法的代码。所需的变量将是输入数组和数组的长度。这两个参数将进一步用于引入更多参数来创建合并排序函数。让我们看一下下面的代码片段，了解 Java 中合并排序算法的一般工作原理。

Merge_Sort_Algo (Array, Beginning, End)
/** Three parameters required for the Merge Sort Algorithm
 * Array = values of the array
 * Beginning = the starting element of the array
 * End = the ending element of the array*/

if (Beginning < End) // condition check Beginning must be less than End

set Middle = (Beginning + End) / 2 // Assigning Middle to the array

Merge_Sort_Algo (Array, Beginning, Middle) /** Sorting and merging of elements from Beginning to the Middle */

Merge_Sort_Algo (Array, Middle +1, End) /** Sorting and merging of elements from Middle to the End */

Merge (Array, Beginning, Middle, End) // Merging both the sorted arrays

end of if

End Merge_Sort_Algo

首先通过if条件Beginning和End来确定Middle。然后在下一步中，从 Beginning 到 Middle 创建 2 个新子数组，另一个从 Middle +1 到 End 开始创建。将这些数组进行划分，直到其长度变为 1，然后通过合并函数将已排序的子数组 Beginning、Middle、Middle+1 和 End 全部合并回去以获得解。

例子

下面的Java代码解释了合并排序算法：

import java.util.Arrays;

class HelloWorld {

    public static void merge(

  int[] array, int[] new_array_1, int[] new_array_2, int left, int right) {
   // defining parameters

    int i = 0, j = 0, k = 0;

    while (i < left && j < right) {  // conditions for merging

        if (new_array_1[i] <= new_array_2[j]) {
            array[k++] = new_array_1[i++];
        }
        else {
            array[k++] = new_array_2[j++];
        }
    }

    while (i < left) {
        array[k++] = new_array_1[i++];
    }

    while (j < right) {
        array[k++] = new_array_2[j++];
    }
}

    public static void mergeSort(int[] array, int length) { /** required parameters */
	if (length < 2) {  //condition for the length of array
    	return;
	}

	int middle = length / 2;  // defining new parameter middle

	int [ ] new_array_1 = new int [middle]; /** defining the new first array after division */
	int [ ] new_array_2 = new int [length - middle]; /** defining the new second array */


	for (int i = 0; i < middle; i++) { /**applying condition for sorting of new array 1 */
    	new_array_1 [ i ] = array [ i ];
	}

	for (int i = middle; i < length ; i++) { /**applying condition for sorting of new array 2 */
    	new_array_2 [ i - middle] = array [ i ];
	}

	mergeSort (new_array_1, middle); /** calling merge sort function for new array 1 */
	mergeSort (new_array_2, length - middle); /** calling merge sort function for new array 2 */


	merge(array, new_array_1, new_array_2, middle, length - middle); /** calling function for merging of new array 1 and new array 2 */
}


    public static void main(String[] args) {

        int [ ] testScores = {6,9,8,2,4,1};
        int size = testScores.length;

        System.out.println("Original Array " + Arrays.toString(testScores) + "\n");

        mergeSort(testScores, size);

        System.out.println("After Merge Sort " + Arrays.toString(testScores) + "\n");
    }
}

输出

结论

Java 中的归并排序是一种从未排序的数字列表中获取已排序列表的简单算法。应用“分而治之”的基本方法从未排序的数组访问已排序的数组。