现在的位置: 首页 > 操作系统 > 正文

Java实现归并排序算法

2020年02月10日 操作系统 ⁄ 共 1792字 ⁄ 字号 评论关闭

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

    基本思想

      可以将一组数组分成A,B两组依次类推,当分出来的小组只有一个数据时,就可以认为这个小组已经达到了有序然后合并相邻的两个小组这样先通过递归的分解数组,再合并数组就可以完成 归并排序

    两个数组的合并算法实现

public class Merge { public static void main(String[] args) { int[] arrayA = new int[] { 1, 6, 3, 4, 5 }; int[] arrayB = new int[] { 2, 7, 8, 9 }; int[] temp = new int[9]; mergeArray(arrayA, arrayA.length, arrayB, arrayB.length, temp); for (int i : temp) { System.out.print(i + " "); } } /** * 将数组 arrayA[] 和 arrayB[] 合并到 arrayC[] */ private static void mergeArray(int arrayA[], int lengthA, int arrayB[], int lengthB, int temp[]) { int i = 0, j = 0, k = 0; while (i < lengthA && j < lengthB) { // 将两个有序的数组合并,排序到辅助数组temp中 if (arrayA[i] > arrayB[j]) { temp[k++] = arrayB[j++]; } else { temp[k++] = arrayA[i++]; } } while (i < lengthA) { // 如果arrayA[] 中还没有合并完的,则直接将arrayA[]中没有合并的数组复制到辅助数组中 temp[k++] = arrayA[i++]; } while (j < lengthB) { // 如果arrayB[] 中还没有合并完的,则直接将arrayB[]中没有合并的数组复制到辅助数组中 temp[k++] = arrayB[j++]; } }}

    算法实现

public class MergeSorter { public void sort(int[] array) { int[] auxArray = new int[array.length]; mergeSort(array, auxArray, 0, array.length - 1); } /** * 基于分治思想,执行归并排序 */ private void mergeSort(int[] array, int[] auxArray, int low, int high) { int pidedIndex = 0; if (low < high) { pidedIndex = (low + high) / 2; mergeSort(array, auxArray, low, pidedIndex); // 左边递归归并排序 mergeSort(array, auxArray, pidedIndex + 1, high); // 右边递归归并排序 mergeArray(array, auxArray, low, pidedIndex, high); // 合并分治结果 } } private void mergeArray(int[] array, int[] temp, int low, int pidedIndex, int high) { int i = low; // 指向左半分区的指针 int j = pidedIndex + 1; // 指向右半分区的指针 int k = 0; // 指向辅助数组的指针 while (i <= pidedIndex && j <= high) { if (array[i] > array[j]) { temp[k++] = array[j++]; } else { temp[k++] = array[i++]; } } while (i <= pidedIndex) { temp[k++] = array[i++]; } while (j <= high) { temp[k++] = array[j++]; } // 最后把辅助数组的元素复制到原来的数组中去,归并排序结束 for (i = low, k = 0; i <= high; i++, k++) { array[i] = temp[k]; } }}

本文永久更新链接地址:http://www.xuebuyuan.com/Linux/2017-02/141165.htm

以上就上有关Java实现归并排序算法的全部内容,学步园全面介绍编程技术、操作系统、数据库、web前端技术等内容。

抱歉!评论已关闭.