【大话数据结构&算法】归并排序

小鱼儿 2022-07-19 01:50 193阅读 0赞

**归并排序算法的基本步骤：**

1、把0~length-1的数组分成左数组和右数组；  
2、对左数组和右数组进行迭代排序；  
3、将左数组和右数组进行合并，那么生成的整个数组就是有序的数据数组。

--------------------

**归并排序基本算法实现如下：**

void _merge_data_in_array(int[] array, int start,int middle,int end){
                 int[] mergeArray = null;
                 int left = start;
                 int right = end;
                 int m = middle;
                 int mid = middle + 1;
                 int k = 0;
                 while(left <= m && mid <= right){
                       if(array[left] < array[mid]){
                             mergeArray[k++] = array[left++];
                      } else{
                             mergeArray[k++] = array[mid++];
                      }
                }
    
                 while(left <= m){
                       mergeArray[k++] = array[left++];
                }
    
                 while(mid <= right){
                       mergeArray[k++] = array[mid++];
                }
    
                 for(int i = 0;i < k;i++){
                      array[start + i] = mergeArray[i];
                }
          }

--------------------

**java代码实现如下：**

public class Merge_Sort {
    
           public static void main(String[] args) {
                 int[] array = {
       4,9,2,3,6,0,7,1,5};
                 merge_sort(array,8);
                 for (int i = 0; i < array.length; i++) {
                      System. out.println(array[i]);
                }
          }
    
           //判断参数合法性，调用合并函数进行迭代操作
           public static void merge_sort(int[] array, int length){
                 if(null == array && 0 == length){
                       return;
                }
                 _merge_sort(array,0,length - 1);
          }
    
           //进行迭代操作
           public static void _merge_sort(int[] array, int start,int end){
                 while(start < end){
                       int middle = start + ((end -start) >> 1);//求middle,没看懂
    //                 int middle = (start + end) / 2;
                       //对左数组进行迭代排序
                       _merge_sort(array,start,middle);
                       //对右数组进行迭代排序
                       _merge_sort(array,middle + 1,end);
                       //将迭代排序后的左数组和右数组进行合并
                       _merge_data_in_array(array,start,middle,end);
                }
    
          }
    
           //对合并后的队列进行合并操作
           public static void _merge_data_in_array(int[] array, int start,int middle,int end){
                 int[] mergeArray = null;
                 int left = start;
                 int right = end;
                 int m = middle;
                 int mid = middle + 1;
                 int k = 0;
                 while(left <= m && mid <= right){
                       if(array[left] < array[mid]){
                             mergeArray[k++] = array[left++];
                      } else{
                             mergeArray[k++] = array[mid++];
                      }
                }
    
                 while(left <= m){
                       mergeArray[k++] = array[left++];
                }
    
                 while(mid <= right){
                       mergeArray[k++] = array[mid++];
                }
    
                 for(int i = 0;i < k;i++){
                      array[start + i] = mergeArray[i];
                }
          }
    
    }

--------------------

> **时间复杂度**：
> 
> 归并排序中可选区merge()函数内的“归并排序”作为基本操作。merge()函数的作用是将两个有序的序列归并为一个整体有序的序列。“归并操作”即为将待归并表中的元素复制到一个存储归并结果的表中的过程。在顺序表中，merge()函数的“归并操作”执行次数为要归并的两个子序列中元素个数之和。**归并排序的时间复杂度和初始序列无关，平均情况下为O(nlogn)\{以2为底\}，最好情况下为O(nlogn)\{以2为底\}，最坏情况下为O(nlogn)\{以2为底\}。**

--------------------

> **空间复杂度**：
> 
> 因为归并排序需要转存整个待排序列，因此空间复杂度为**O(n)**。