（4）排序算法——合并排序

柔情只为你懂 2022-07-29 09:01 149阅读 0赞

合并排序算法的时间复杂度为O\*(n\*logn)

public class MergeSort { 
      /** The method for sorting the numbers */
      public static void mergeSort(int[] list) {
        if (list.length > 1) {
          // Merge sort the first half
          int[] firstHalf = new int[list.length / 2];
          System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
          mergeSort(firstHalf);
    
          // Merge sort the second half
          int secondHalfLength = list.length - list.length / 2;
          int[] secondHalf = new int[secondHalfLength];
          System.arraycopy(list, list.length / 2,
            secondHalf, 0, secondHalfLength);
          mergeSort(secondHalf);
    
          // Merge firstHalf with secondHalf
          int[] temp = merge(firstHalf, secondHalf);
          System.arraycopy(temp, 0, list, 0, temp.length);
        }
      }
    
      /** Merge two sorted lists */
      private static int[] merge(int[] list1, int[] list2) {
        int[] temp = new int[list1.length + list2.length];
    
        int current1 = 0; // Current index in list1
        int current2 = 0; // Current index in list2
        int current3 = 0; // Current index in temp
    
        while (current1 < list1.length && current2 < list2.length) {
          if (list1[current1] < list2[current2])
            temp[current3++] = list1[current1++];
          else
            temp[current3++] = list2[current2++];
        }
    
        while (current1 < list1.length)
          temp[current3++] = list1[current1++];
    
        while (current2 < list2.length)
          temp[current3++] = list2[current2++];
    
        return temp;
      }
    
      /** A test method */
      public static void main(String[] args) {
        int[] list = {
       2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
        mergeSort(list);
        for (int i = 0; i < list.length; i++)
          System.out.print(list[i] + " ");
      }
    }