八大排序算法之堆排序

飞熊 • 2023年4月17日上午11:03 • 后端漫谈 • 阅读 202

“ 堆排序指利用堆这种数据结构所设计的一种排序算法。堆是一个近似于完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。”

01

数组实现二叉堆的性质

性质一: 索引为i的左孩子的索引是 (2*i+1);

性质二: 索引为i的右孩子的索引是 (2*i+2);

性质三: 索引为i的父结点的索引是 floor((i-1)/2);

如下图

例如，对于最大堆{110,100,90,40,80,20,60,10,30,50,70}而言: 索引为0的左孩子的所有是1；索引为0的右孩子是2；索引为8的父节点是3。

时间复杂度

时间复杂度：O(N*log(N))
稳定性：不稳定

—

代码实现

//编写一个堆排序的方法
public static void headSort(int[] arr) {

    //将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
    for (int i = arr.length / 2 -1; i >= 0; i--) {
        adjustHead(arr,i, arr.length);
    }

    //将堆顶元素与末尾元素交换，将最大元素“沉”到数组末尾
    for (int i = arr.length -1; i > 0; i--) {

        //交换
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        adjustHead(arr,0,i);
    }

}

/**
 * 完成以i对应的非叶子节点的树调整成大顶堆
 * @param arr 待调整的数组
 * @param i 表示非叶子节点再数组中的索引
 * @param length 表示对多少个元素继续调整，length是再逐渐减少
 */
public static void adjustHead(int[] arr,int i,int length) {

    int temp = arr[i];//取出当前元素的值，保存再临时变量
    //k = i*2+1 是i节点的左子节点
    for (int k = i*2+1; k < length; k=k*2+1) {

        if (k+1 < length && arr[k] < arr[k+1]) { //说明左子节点的值小于右子节点的值
            k++;
        }

        if (arr[k] > temp) {//如果子节点大于父节点
            arr[i] = arr[k];//把较大的值赋给当前节点
            i = k;//i指向k继续循环比较
        } else {
            break; //退出
        }

    }

    //for循环结束后，我们已经将以i为父节点的树的最大值，放在了最顶部（局部）
    arr[i] = temp;//将temp值放到调整后的位置

}