public class mySort {
    
    // 冒泡排序
    public static void myBubbleSort(int[] array) {
        int lastExchange = array.length - 1;    //记录最后交换位置, 避免重复比较
        for (int i = lastExchange - 1; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    lastExchange = j;   //特性:最后交互位置后的元素已经有序
                }
            }
        }
    }
    
    
    // 插入排序
    public static void myInsertSort(int[] array) {
        for (int i = 1; i <= array.length - 1; ++i) {
            int temp = array[i];
            int j = 0; // 给值移位并寻找插入点
            for (j = i - 1; j >= 0 && array[j] > temp; --j) {
                array[j + 1] = array[j];
            }
            array[j + 1] = temp;
        }
    }

    
    // 选择排序
    public static void mySelectSort(int[] array) {
        for (int i = 0; i < array.length - 1; ++i) {
            int minIndex = i;
            // 每次选出一极值
            for (int j = i + 1; j < array.length - 1; ++j) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            // 极值归位
            if (minIndex != i) {
                int temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
            }
        }
    }

    
    // 希尔排序
    public static void myShellSort(int[] array) {
        int gap = 5;
        while (gap != 0) {
            //不必刻意分组, 组1->组2->组1->组2...轮流处理
            for (int j = gap; j <= array.length - 1; ++j) {
                int temp = array[j];
                int k = 0;
                for (k = j - gap; k >= 0 && array[k] > temp; k -= gap) {
                    array[k + gap] = array[k];
                }
                array[k + gap] = temp;
            }
            gap /= 2;   //重新分组
        }
    }

    
    // 快速排序
    public static void myQuickSort(int[] array) {
        myQuickSortCore(array, 0, array.length - 1);
    }
    private static void myQuickSortCore(int[] array, int left, int right) {
        if (left >= right) {   //递归出口
            return;
        }
        int mLeft = left;
        int mRight = right;
        
        int base = array[mLeft];  //第一个元素作为基准, left空位可占
        while(mLeft != mRight) {
            while (mRight > mLeft && array[mRight] >= base) {
                --mRight;
            }
            array[mLeft] = array[mRight];  //right可覆盖
            while (mRight > mLeft && array[mLeft] <= base) {
                ++mLeft;
            }
            array[mRight] = array[mLeft];
        }
        array[mRight] = base; //基准元素归位, l=r
        
        myQuickSortCore(array, left, mLeft - 1);  //递归基准以左
        myQuickSortCore(array, mRight + 1 , right);  //递归基准以右
    }
    
    
    // 归并排序
    public static void myMergeSort(int[] array) {
        // 每个分组中有两个来自上层迭代的有序组, gap为有序组长度, 2 * gap为分组长度
        for (int gap = 1; gap < array.length; gap *= 2) {
            int i = 0; // array下标
            // 分组并内部排序
            while (i + 2 * gap - 1 < array.length) {
                mergePiece(array, i, i + gap - 1, i + 2 * gap - 1);
                i += 2 * gap;
            }
            // 分组剩余部分排序, 只有超过一个gap才有内部排序的意义
            if (i + gap - 1 < array.length) {
                mergePiece(array, i, i + gap - 1, array.length - 1);
            }
        }
    }
    // 将array中有序的两段piecewise1 和 piecewise2 合并成整体有序
    public static void mergePiece(int[] array, int head, int mid, int tail) {
        int i = head; // piecewise1下标 [head, mid]
        int j = mid + 1; // piecewise2下标 [mid + 1, tail]
        // 临时数组, 保存结果
        int[] arrayTemp = new int[tail - head + 1]; // combine
        int k = 0; // combine下标
        while (i <= mid && j <= tail) {
            if (array[i] <= array[j]) {
                arrayTemp[k] = array[i];
                ++i;
                ++k;
            } else {
                arrayTemp[k] = array[j];
                ++j;
                ++k;
            }
        }
        // 复制多余部分 piecewise1
        while (i <= mid) {
            arrayTemp[k] = array[i];
            ++i;
            ++k;
        }
        // 复制多余部分 piecewise2
        while (j <= tail) {
            arrayTemp[k] = array[j];
            ++j;
            ++k;
        }
        // 结果复制到原始数组
        k = 0;
        i = head; // 重置下标, i piecewise1 + piecewise2
        while (i <= tail) {
            array[i] = arrayTemp[k];
            ++i;
            ++k;
        }
    }

    
    // 堆排序
    public static void myHeapSort(int[] array) {
        // 调整堆->大顶堆
        for (int i = array.length / 2 - 1; i >= 0; --i) { // 从最后非叶子节点开始
            adjustHeap(array, i, array.length);
        }
        // 调整堆->交换堆顶/末位元素
        for (int j = array.length - 1; j > 0; --j) {
            int temp = array[0];
            array[0] = array[j];
            array[j] = temp;
            adjustHeap(array, 0, j); // 只需调整堆顶父节点
        }
    }
    // 调整为大顶堆分布, node为父节点下标, adjustLen为涉及调整的长度(为排序使用)
    private static void adjustHeap(int[] array, int node, int adjustLen) {
        int temp = array[node]; // 拿出node形成可占空位
        for (int i = node * 2 + 1; i < adjustLen; i = node * 2 + 1) {
            if (i + 1 < adjustLen && array[i] < array[i + 1]) {
                ++i; // 得到最大子节点
            }
            if (array[i] > temp) {
                array[node] = array[i];
                node = i; // 为下一层迭代更新父节点node, 最后为叶子
            } else {
                break;
            }
        }
        array[node] = temp;
    }
    
    
    // 基数排序
    public static void myRadixSort(int[] array) {
        int d = maxBit(array);
        int dec = 1; //进制迭代
        final int R = 10;  //桶个数
        int[] tempArray = new int[array.length];  //临时数组, 代替桶存储数组, 代价是需记录下标/数量来分割桶
        int[] bucketCapacity = new int[R];  //桶计数 
        for (int i = 1; i <= d; ++i) {
            for (int j = 0; j < R; ++j) {
                bucketCapacity[j] = 0;   //清空桶容量
            }
            //计数1
            for (int j = 0; j < array.length; ++j) {
                int k = array[j] / dec % R;  
                ++bucketCapacity[k];
            }
            //计数2 变累计, 为分割
            for (int j = 1; j < R; ++j) {
                bucketCapacity[j] = bucketCapacity[j - 1] + bucketCapacity[j];
            }
            // 存储进桶
            for (int j = array.length - 1; j >= 0; --j) {
                int k = array[j] / dec % R; 
                tempArray[bucketCapacity[k] - 1] = array[j];
                --bucketCapacity[k];  
            }
            // 写出
            for(int j = 0; j < array.length; ++j) {
                array[j] = tempArray[j];
            }
            // 下一位
            dec *= 10;
        }
        
    }
    //求数组元素的最大位数
    private static int maxBit(int[] array) {
        int bit = 1;
        int dec = 10;
        for (int i = 0; i < array.length; ++i) {
            while (array[i] >= dec) {
                ++bit;
                dec *= 10;
            }
        }
        return bit;
    }
}