算法-->合并排序

分手后的思念是犯贱 2022-06-12 08:39 147阅读 0赞

package 合并排序;
    
    public class HeBing {
        static final int SIZE = 15;
    
        static void mergeOne(int a[], int b[], int n, int len) {
            int i, j, k, s, e;
            s = 0;
            // 第一次合并，每段len个
            while (s + len < n) {
                e = s + 2 * len - 1;
                if (e >= n) {
                    e = n - 1;// 最后一段可能少于len个节点
                }
                // 相邻的有序段合并
                k = s;
                i = s;
                j = s + len;
                // 如果两个有序表都未结束的时候,循环比较
                while (i < s + len && j <= e) {
                    // 如果较小的元素赋值到数组b中
                    if (a[i] <= a[j]) {
                        b[k++] = a[i++];
                    } else {
                        b[k++] = a[j++];
                    }
                }
                // 未合并的部分复制 到数组 B中
                while (i < s + len) {
                    b[k++] = a[i++];
                }
                while (j <= e) {
                    // 未合并的部分复制 到数组 B中
                    b[k++] = a[j++];
                }
                // 下一对有序段中左段的开始下标
                s = e + 1;
            }
            // 将剩余的一个有序段从数组A中复制到数组 B中
            if (s < n) {
                for (; s < n; s++) {
                    b[s] = a[s];
                }
            }
        }
    
        // 合并排序
        static void mergeSort(int a[], int n) {
            int h, count, len, f;
            /// 排序步骤
            count = 0;
            // 有序序列的长度
            len = 1;
            // 标志
            f = 0;
            int[] p = new int[n];
            // 交换再a和p之间的合并
            while (len < n) {
                if (f == 1) {
                    // p合并到a
                    mergeOne(p, a, n, len);
                } else {
                    // a合并到p
                    mergeOne(a, p, n, len);
                }
                // 增加有序序列的长度
                len = len * 2;
                // 使得f再0-1之间切换
                f = 1 - f;
                count++;
                // 输出每步排序的结果
                System.out.printf("第" + count + "步排序 的结果");
                for (h = 0; h < SIZE; h++) {
                    System.out.print(" " + a[h]);
                }
                System.out.print("\n");
            }
            // 如果进行了排序
            if (f == 1) {
                // 将内存p中的数组复制回数组a
                for (h = 0; h < n; h++) {
                    a[h] = p[h];
                }
            }
        }
    
        public static void main(String[] args) {
            HeBing he = new HeBing();
            int[] shuzu = new int[SIZE];
            int i;
            for (i = 0; i < SIZE; i++) {
                shuzu[i] = (int) (100 + Math.random() * (100 + 1));
            }
            System.out.print("排序前 的数组为：\n");
            for (i = 0; i < SIZE; i++) {
                System.out.print(" " + shuzu[i]);
            }
            System.out.print("\n");
            mergeSort(shuzu, SIZE);
            System.out.print("排序后 的数组为：\n");
            for (i = 0; i < SIZE; i++) {
                System.out.print(shuzu[i] + " ");
            }
            System.out.print("\n");
        }
    }

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220612/184db24eb0de4ca795b82a2118fd0000.png