题解 | 三三归并-头脑风暴 #排序#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here

        int[] temp = arr;
        int len = 1;
        while (len < temp.length) {
            int index = 0;
            while (true) {
                int base = index * 3 * len;
                // merge
                if (base >= temp.length) {
                    break;
                }

                int lena, lenb, lenc;
                if (base + len >= temp.length) {
                    lena = temp.length - base;
                } else {
                    lena = len;
                }
                int[] a = new int[lena];
                System.arraycopy(temp, base, a, 0, lena);

//                 System.out.println("a:");
//                 for (int i = 0; i < a.length; i++) {
//                     System.out.print(a[i]+" ");
//                 }
//                 System.out.println();

                if (base + lena + len >= temp.length) {
                    lenb = temp.length - base - lena;
                } else {
                    lenb = len;
                }
                int[] b = new int[lenb];
                System.arraycopy(temp, base + lena, b, 0, lenb);

//                 System.out.println("b:");
//                 for (int i = 0; i < b.length; i++) {
//                     System.out.print(b[i]+" ");
//                 }
//                 System.out.println();

                if (base + lena + lenb + len >= temp.length) {
                    lenc = temp.length - base - lena - lenb;
                } else {
                    lenc = len;
                }
                int[] c = new int[lenc];
                System.arraycopy(temp, base + lena + lenb, c, 0, lenc);

//                 System.out.println("c:");
//                 for (int i = 0; i < c.length; i++) {
//                     System.out.print(c[i]+" ");
//                 }
//                 System.out.println();

                int pointa = 0;
                int pointb = 0;
                int pointc = 0;

                int[] out = new int[lena + lenb + lenc];
                int point = 0;
                while (true) {
                    if (pointa == lena) {
                        if (pointb == lenb) {
                            if (pointc == lenc) {
                                break;
                            } else {
                                out[point++] = c[pointc++];
                            }
                        } else {
                            if (pointc == lenc) {
                                out[point++] = b[pointb++];
                            } else {
                                if (b[pointb] < c[pointc]) {
                                    out[point++] = b[pointb++];
                                } else {
                                    out[point++] = c[pointc++];
                                }
                            }
                        }
                    } else if (pointb == lenb) {
                        if (pointc == lenc) {
                            out[point++] = a[pointa++];
                        } else {
                            if (a[pointa] < c[pointc]) {
                                out[point++] = a[pointa++];
                            } else {
                                out[point++] = c[pointc++];
                            }
                        }
                    } else if (pointc == lenc) {
                        if (a[pointa] < b[pointb]) {
                            out[point++] = a[pointa++];
                        } else {
                            out[point++] = b[pointb++];
                        }
                    } else { // all
                        if (a[pointa] < b[pointb]) {
                            if (a[pointa] < c[pointc]) {
                                out[point++] = a[pointa++];
                            } else {
                                out[point++] = c[pointc++];
                            } 
                        } else {
                            if (b[pointb] < c[pointc]) {
                                out[point++] = b[pointb++];
                            } else {
                                if (a[pointa] < c[pointc]) {
                                    out[point++] = a[pointa++];
                                } else {
                                    out[point++] = c[pointc++];
                                }
                            }
                        }
                    }

                }

//                 System.out.println(out.length);
//                 for (int i = 0; i < out.length; i++) {
//                     System.out.print(out[i] + " ");
//                 }
//                 System.out.print("\n");
                System.arraycopy(out, 0, temp, base, out.length);
                index++;
            }
            len = len * 3;
//             for (int i = 0; i < temp.length; i++) {
//                 System.out.print(temp[i] + " ");
//             }
//             System.out.print("\n");
        }
        return temp;
    }
}