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

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; // 被调整的结点的值放人最终位置
    }

}

7.归并排序 7.1.基本思想

  归并排序就是利用归并的思想实现的排序方法。而且充分利用了完全二叉树的深度是的特性,因此效率比较高。其基本原理如下:对于给定的一组记录,利用递归与分治技术将数据序列划分成为越来越小的半子表,在对半子表排序,最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。 
  经过第一轮比较后得到最小的记录,然后将该记录的位置与第一个记录的位置交换;接着对不包括第一个记录以外的其他记录进行第二次比较,得到最小记录并与第二个位置记录交换;重复该过程,知道进行比较的记录只剩下一个为止。

7.2.复杂度分析

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

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