归并排序及Java实现

野性酷女 2021-09-28 13:06 331阅读 0赞

# 一、归并排序的思想 #

先使子序列有序，再使子序列段间有序，  
将两个有序序列合成一个，称为二路归并  
在待排序数据中，默认每个单独的数据都是有序的，每两个数据分为一个归并段，段内排序；每四个数据分为一个归并段，段内排序；每八个数据分为一个归并段，段内排序……直到所有数据有序（因为是按偶数分段的，所以当待排序数据个数为奇数时，最后总会剩余一个单独的数据，将其作为一个归并段就行）

### 1、复杂度、稳定性 ###

*  **时间复杂度**：最好情况：O(nlog2n)  
    最坏情况：O(nlog2n)
 *  **空间复杂度**：O(n)
 *  **稳定性**： 稳定

### 2、图解 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]  
在归并时，要进行段内排序，定义四个变量：start1, end1, start2, end2. 分别表示相邻两个归并段的起始位置和结束位置。开始排序：判断start1和start2的大小，start1<start2时，将start1放入新的数组的第一个位置，start1++，再和start2比较，小的那个数的下标+1，直到start1>end1，将剩余的值按序放入新数组。如 下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 1]

# 二、代码 #

public class TestDemo2 { 
        public static void merge(int[] array,int gap) { //每组的元素个数
            int[] tmpArr =  new int[array.length];  //定义新数组，用来保存每次归并结束的数据顺序。
            int i = 0;  //tmpArr的下标
            int start1 = 0; 
            int end1 = start1+gap-1;
            int start2 = end1+1;
            int end2 = start2+gap-1 < array.length ? start2+gap-1 : array.length-1;
    
            while (start2 < array.length) { //说明此时有两个对归并段
                //两个归并段都有数据
                while(start1 <= end1 && start2 <= end2) { 
               //判断s1和s2，小的值放入tmpArr，并且下标后移一位继续比较，直到开始位置>结束位置，退出while
                    if(array[start1] < array[start2]) { 
                        tmpArr[i++] = array[start1++];
                    }else { 
                        tmpArr[i++] = array[start2++];
                    }
                }
                while (start1 <= end1) { 
                    tmpArr[i++] = array[start1++];
                }
                while (start2 <= end2) { 
                    tmpArr[i++] = array[start2++];
                }
                //确定下一个归并段的开始和结束位置
                start1 = end2+1;
                end1 = start1+gap-1;
                start2 = end1+1;
                end2 = start2+gap-1 < array.length ? start2+gap-1 : array.length-1;
            }
            while (start1 < array.length) { 
                tmpArr[i++] = array[start1++];
            }
            for (int j = 0; j < tmpArr.length; j++) { 
                array[j] = tmpArr[j];
            }
        }
        public static void mergeSort(int[] array) { 
            for (int i = 1; i < array.length; i *= 2) { 
                merge(array,i);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]: /images/20210923/bc1537b7653046b2884947fbaca54950.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 1]: /images/20210923/cca412421fcf49fba73019f70876e535.png