排序算法——归并排序

• 排序逻辑

  将一个队列递归均分为两个数组，再将两个数组按序归并为一个数组

  • 初始队列

    

  • 均分为两个队列

    

  • 按序归并

    

• 代码示例（递归实现）

  /**
  * 归并排序：
  * 将一个数组递归均分为两个数组，再将两个数组归并为一个数组
  * @param arr
  * @param start 数组范围
  * @param end
  */
  public static void mergeSort(int[] arr, int start, int end){
      int middle = (start + end) / 2;
      if(start<end){
          //分为两个数组
          mergeSort(arr,start,middle);
          mergeSort(arr,middle+1, end);
          //合并
          merge(arr,start,middle,end);
      }
  }
  
  /**
  * 两个数组归并为一个数组
  * @param arr
  * @param start     两个数组的范围
  * @param middle
  * @param end
  */
  private static void merge(int[] arr, int start, int middle, int end) {
      //临时数组用来储存归并后的数据
      int[] temp = new int[end-start+1];
      //第一个数组的索引
      int i = start;
      //第二个数组的索引
      int j = middle+1;
      //临时数组的索引
      int index = 0;
      //两个数组逐一比较，小的放进临时数组
      while(i<=middle&&j<=end){
          if(arr[i]<arr[j]){
              temp[index++] = arr[i++];
          }else{
              temp[index++] = arr[j++];
          }
      }
      //两个数组中没有剩下的元素逐一放进临时数组
      while(i<=middle){
          temp[index++] = arr[i++];
      }
      while(j<=end){
          temp[index++] = arr[j++];
      }
      //将临时数组放进源数组
      for(int k=0;k<temp.length;k++){
          //源数组为arr[start,end]
          arr[k+start] = temp[k];
      }
  }
  

• 代码示例（迭代实现）

  public static void mergeItSort(int[] arr, int n){
      int i,left_min,left_max,right_min,right_max;
      int[] temp = new int[n];
      //i代表步长
      for(i=1; i<n; i*=2){
          for(left_min=0; left_min<n-i; left_min=right_max){
              left_max = right_min = left_min+i;
              right_max = right_min + i;
              if(right_max > n){
                  right_max = n;
              }
              //临时数组的指针
              int next = 0;
              while(left_min<left_max && right_min<right_max){
                  if(arr[left_min] < arr[right_min]){
                      temp[next++] = arr[left_min++];
                  }else{
                      temp[next++] = arr[right_min++];
                  }
              }
              //将左边剩下的部分放在右边尾部
              while(left_min<left_max){
                  arr[--right_min] = arr[--left_max];
              }
              //将临时数组中的数据放入原数组
              while(next>0){
                  arr[--right_min] = temp[--next];
              }
          }
  
  
      }
  }
  

• 事件复杂度

  O(nlogn)