欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

归并排序的Java实现

程序员文章站 2024-03-16 12:21:04
...

题目:对于一个int数组,请编写一个归并排序算法,对数组元素排序。给定一个int数组A及数组的大小n,请返回排序后的数组。


算法思路:

  • 先用递归方法,默认排序方法为2路归并排序。看下图应该能立即理解:

归并排序的Java实现

  • 先使每个子序列有序,再将两个已经排序的序列合并成一个序列的操作。若将两个已经排序的有序表合并成一个有序表,称为二路归并。
public class MergeSort {
     public int[] mergeSort(int[] A) {
          //归并排序,递归做法,分而治之
          mSort(A, 0, A.length-1);
          return A;
     }

     public void mSort(int[] A, int low, int high) {
          if(low < high) {
               int mid = (low+mid)/2;//中点
               mSort(A, low, mid);
               mSort(A, mid+1, high);
               merge(A, low, mid, high);
          }
     }

     public void merge(int[] A, int low, int mid, int high) {
          //辅助数组
          int[] temp =new int[A.length];
          //左子序列的下标
          int i = low;
          //右子序列的下标
          int j = mid+1;
          //辅助数组的下标
          int tempIndex = low;
          while(i <= mid && j <= high) {
               if(A[i] < A[j]) {
                    temp[tempIndex++] = A[i++];
               } else {
                    temp[tempIndex++] = A[j++];
               }
          }
          for(; i <= mid; i++) {
               temp[copyIndex++] = A[i];
          }
          for(; j <= high; j++) {
               temp[copyIndex++] = A[j];
          }
          //复制已排好序的数组至原数组
          for(int v = low; v <= high; v++) {
               A[v] = temp[v];
          }
     }
}