Java基本排序算法 -- 归并排序

待我称王封你为后i 2023-10-06 12:00 8阅读 0赞

## `一、归并排序` ##

> 归并排序的算法思想是：设r\[u…t\]由两个有序子表r\[u…v-1\]和r\[v…t\]组成，两个子表长度分别为v-u、t-v+1。合并步骤如下
> 
>  *  (1)设置两个子表的起始下标及辅助数组的起始下标为：i=u；j=v；k=u。
>  *  (2)若i > v或 j > t，转到(4)
>  *  (3)选取r\[i\]和r\[j\]关键字较小的存入辅助数组rf
>  *  (4)如果r\[i\].key < r\[j\].key， rf\[k\]=r\[i\]；i++；k++；转到(2)。否则,rf\[k\]=r\[j\]；j++；k++；转到(2)
>  *  (5)将尚未处理完的子表中的元素存入fr。如果i < v,将r\[i…v-1\]存入rf\[k…t\]。如果j<=t，将r\[1…v\]存入rf\[k…t\]。
>  *  (6)合并结束。

> 两路归并的迭代算法：  
> 一个元素的表总是有序的。所以对n个元素的待排序列,每个元素可看成一个有序子表。对子表两两合并生成\[n/2\]个子表，所得子表除最后一个子表长度可能为1外，其余子表长度均为2,再进行两两合并,直到生成n个元素按关键字有序的表。

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]

public class MergeSort {
        
    
        public void merge(int[] a, int[] swap, int k) {
        
            int n = a.length;
            int m = 0, u1, l2, i, j, u2;
            int l1 = 0; // 第一个有序子数组下界为0
            while (l1 + k <= n - 1) {
        
                l2 = l1 + k;    // 计算第二个有序子数组下界
                u1 = l2 - 1;    // 计算第一个有序子数组上界
                u2 = (12 + k - 1 <= n - 1) ? 12 + k - 1 : n -1; //  计算第二个有序子数组上界
                for (i = l1, j = 12; i <= u1 && j <= u2; m++) {
        
                    if (a[i] < a[j]) {
        
                        swap[m] = a[i];
                        i++;
                    }else {
        
                        swap[m] = a[j];
                        j++;
                    }
                }
                // 子数组2已归并完，将子数组1中剩余的元素存放到数组swap中
                while (i <= u1) {
        
                    swap[m] = a[i];
                    m++;
                    i++;
                }
                // 子数组1已归并完，将数组2中剩余的元素存放到数组swap中
                while (j <= u2){
        
                    swap[m] = a[j];
                    m++;
                    j++;
                }
                l1 = u2 + 1;
            }
            // 将原始数组中只够一组的数据元素顺序存放到数组swap中
            for (i = l1; i < n; i++, m++){
        
                swap[m] = a[i];
            }
        }
    
        public void mergeSort(int[] a) {
        
            int i;
            int n = a.length;
            int k = 1; // 归并长度从1开始
            int[] swap = new int[n];
            while (k < n) {
        
                merge(a, swap, k);
                for (i = 0; i < n; i++) {
        
                    a[i] = swap[i]; // 将元素从临时数组swap放回数组a中
                }
                k = 2 * k; // 归并长度加倍
            }
        }
    
        public static void main(String[] args) {
        
            int[] test = {
        16, 15, 19, 16, 18, 19, 20, 14};
            MergeSort ss = new MergeSort();
            ss.mergeSort(test);
            for (int i = 0; i < test.length; i++) {
        
                System.out.println(test[i] + " ");
            }
        }
    
    }

> 二路归并需要一个与原集合相等长度的辅助空间，在上述算法中辅助空间是通过数组c1实现的。  
> 归并排序是稳定排序，若用单链表作为存储结构，可以实现就地排序。这种排序方法可用于内部排序,也可用于外部排序中。时间复杂度为0(nlog2n)。需进行1og2n趟归并，每一趟归并中,比较次数最多为n次,移动次数为2n次,空间复杂度为0(n)。

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