归并排序理解及实现

￡神魔★判官ぃ 2023-06-16 15:57 32阅读 0赞

## 一、归并排序理解 ##

归并排序非常重要，在计算机科学中，归并排序是一种高效、通用、基于比较的排序算法。此外，归并排序还是稳定的，因为相同元素的相对次序在排序后不会发生变化。大概有两个步骤：  
**1、将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。  
2、将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。**

## 2、图解过程 ##

（摘自网络）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdhbmcxMjIz_size_16_color_FFFFFF_t_70]

## 3、JAVA代码实现 ##

public class MergeSortTest { 
        public static void main(String[] args) { 
            int arr[] = { 3,2,1,4,5,6,0,-1,9,7,8};
            int result[] = merSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(result));
    
        }
    
        private static int[] merSort(int[] arr, int left, int right) { 
            if(left < right){ 
                int mid = (left + right) / 2;
                //递归调用使左右两边都有序
                merSort(arr,left,mid);
                merSort(arr,mid + 1,right);
                merge(arr,left,mid,right);
            }
            return arr;
        }
    
        private static void merge(int[] arr, int left, int mid, int right) { 
            int[] temp = new int[right - left + 1];
            int i = left; //左半部分开始索引
            int j = mid + 1; //右半部分开始索引
            int k = 0;//合并临时数组的开始索引
            while (i <= mid && j <= right){ //左右部分上的数字排序到temp上，直到左右子序列一个循环完，左右两部分有一个循环完，循环就结束
                if(arr[i] < arr[j]){ 
                    //左半部分开始索引比右半部分开始索引小，则将左半部分这个元素放入temp开始位置上，
                    // 然后左边的索引+1右移，判断下一个元素，temp数组的开始缩阴也要右移+1，即
                    // temp[k] = arr[i];
                    // i++;
                    // k++;
                    //上面三步可以归结为一行代码：
                    temp[k++] = arr[i++];
                }else { //左边比右边大，就把右边的值放入temp数组
                    temp[k++] = arr[j++];
                }
            }
            //跳出上面循环肯定是因为左右部分中至少有一个循环完了，剩下的没循环完的进入下面循环,将剩下的放入temp数组
            while (i <= mid){ //说明左边有剩余元素，放入temp
                temp[k++] = arr[i++];
            }
            while (j <= right){ 
                temp[k++] = arr[j++];
            }
            //最后一步，将temp数组元素拷入arr,由于是拷贝，先将k置0。
            k = 0;
            while (left <= right){ 
                arr[left++] = temp[k++];
            }
    
        }
    }

## 4、时间复杂度 ##

归并排序的时间复杂度为O(nlogn)。  
归并排序需要一个跟待排序数组同等空间的临时数组，因此，使用归并排序时需要考虑是否有空间上的限制。如果没有空间上的限制，归并排序是一个不错的选择。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdhbmcxMjIz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191127102859377.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdhbmcxMjIz,size_16,color_FFFFFF,t_70