归并排序是递归的一个重要应用,不断把数组对半拆分,直到拆成单个元素。之后再将拆分的数组按正确顺序一级一级组合起来。以下演示的算法使用了大小相等的第二个数组用于按序组合拆分后的结果。之后会把所有排好序的元素覆盖到原数组上。

归并排序的算法有如下特征:

  • 三个method,mergeSortmergeSortHelpermerge
  • mergeSortHelper会调用自身

以下是一个AP计算机归并排序的示例代码。

import java.util.Arrays;

public class SortTest
{
   public static void mergeSort(int[] elements)
   {
      int n = elements.length;
      int[] temp = new int[n];
      mergeSortHelper(elements, 0, n - 1, temp);
   }

   private static void mergeSortHelper(int[] elements,
                                       int from, int to, int[] temp)
   {
       if (from < to)
       {
          int middle = (from + to) / 2;
          mergeSortHelper(elements, from, middle, temp);
          mergeSortHelper(elements, middle + 1, to, temp);
          merge(elements, from, middle, to, temp);
       }
   }

   private static void merge(int[] elements, int from,
                             int mid, int to, int[] temp)
   {
      int i = from;
      int j = mid + 1;
      int k = from;

      while (i <= mid && j <= to)
      {
         if (elements[i] < elements[j])
         {
            temp[k] = elements[i];
            i++;
         }
         else
         {
            temp[k] = elements[j];
            j++;
         }
         k++;
      }

      while (i <= mid)
      {
         temp[k] = elements[i];
         i++;
         k++;
      }

      while (j <= to)
      {
         temp[k] = elements[j];
         j++;
         k++;
      }

      for (k = from; k <= to; k++)
      {
         elements[k] = temp[k];
      }
   }

   public static void main(String[] args)
   {
      int[] arr1 = {86, 3, 43};
      System.out.println(Arrays.toString(arr1));
      mergeSort(arr1);
      System.out.println(Arrays.toString(arr1));
   }
}


0:00

Under what condition will a merge sort execute faster?

无论数组是什么内容,归并排序的递归和循环都需要完整执行,因而耗时不变。
3

Which sort should be the fastest most of the time?

归并排序因为利用了折半的模式,通过记录部分的排序结果规避了很多不必要的工作量,永远比选择排序快,在绝大部分情况下比插入排序快。
3


陈 欣

AADPS创始人

发表评论