Java中8种常见的排序方法(9)

public static void merge(int[] data, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (data[i] < data[j]) {
                temp[k++] = data[i++];
            } else {
                temp[k++] = data[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = data[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = data[j++];
        }
        // 把新数组中的数覆盖nums数组
        for (int k2 = 0; k2 < temp.length; k2++) {
            data[k2 + low] = temp[k2];
        }
    }

private static int[] heapSort(int[] data) {
        data = buildMaxHeap(data); // 初始建堆,array[0]为第一趟值最大的元素
        for (int i = data.length - 1; i > 1; i--) {
            int temp = data[0]; // 将堆顶元素和堆低元素交换,即得到当前最大元素正确的排序位置
            data[0] = data[i];
            data[i] = temp;
            adjustDownToUp(data, 0, i); // 整理,将剩余的元素整理成堆
        }
        return data;
    }

// 构建大根堆:将array看成完全二叉树的顺序存储结构
    private static int[] buildMaxHeap(int[] array) {
        // 从最后一个节点array.length-1的父节点(array.length-1-1)/2开始,直到根节点0,反复调整堆
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            adjustDownToUp(array, i, array.length);
        }
        return array;
    }

// 将元素array[k]自下往上逐步调整树形结构
    private static void adjustDownToUp(int[] array, int k, int length) {
        int temp = array[k];
        for (int i = 2 * k + 1; i < length - 1; i = 2 * i + 1) { // i为初始化为节点k的左孩子,沿节点较大的子节点向下调整
            if (i < length && array[i] < array[i + 1]) { // 取节点较大的子节点的下标
                i++; // 如果节点的右孩子>左孩子,则取右孩子节点的下标
            }
            if (temp >= array[i]) { // 根节点 >=左右子女中关键字较大者,调整结束
                break;
            } else { // 根节点 <左右子女中关键字较大者
                array[k] = array[i]; // 将左右子结点中较大值array[i]调整到双亲节点上
                k = i; // 【关键】修改k值,以便继续向下调整
            }
        }
        array[k] = temp; // 被调整的结点的值放人最终位置
    }

// 3.选择排序:直接选择排序
    private static int[] chooseSort(int[] data) {
        // 循环次数
        for (int i = 0; i < data.length; i++) {
            // 逐个比较
            for (int j = i + 1; j < data.length; j++) {
                if (data[i] > data[j]) {
                    int temp = data[i];
                    data[i] = data[j];
                    data[j] = temp;
                }
            }
        }

return data;

}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/e3c7ef191ec5f9cba3335d3d026fea11.html