堆排序算法(代码实现) [数据结构][Java]

堆排序算法(代码实现)

具体代码实现如下:

/*
    这里我们来编写堆排序的算法实现(这里我们以升序排序为例)
     */
//首先我们定义一个将指定结点引导的子树转换为大顶堆的方法(我们要从堆中最后一个叶子结点的位置开始遍历转化)

/**
     * @param arr arr是我们传入的代操作的数组
     * @param i  i就是我们当前正在操作的非叶子结点(指向某个非叶子结点, 因为我们只有是非叶子结点的时候我们才会去执行转换为对应的大顶堆的算法)
     * @param length length表示我们要对多少个元素进行调整, 当我们将整个数组转换为大顶堆结构之后我们就要进行元素位置的交换, 每当我们将堆顶元素和数组中最后一个元素交换位置之后我们的length值都要进行一个自减的操作
     */
public static void adjustHeap(int [] arr, int i, int length) { //这里我们就以第一次调用这个方法为例: 也就是从当前我们要操作的是最后一个非叶子结点位置
    //先将我们的当前的非叶子结点的值保存下来, 因为我们可能会让这个位置的值和它的左右子节点中的某一个的值进行一个交换
    int temp = arr[i];

    //循环遍历当前节点的左子树或者是右子树, 直到我们的找到我们目前处理的非叶子结点要保存到的位置为止
    for (int k = 2 * i + 1; k < length; k = k * 2 + 1){ // 沿着堆往下一直找, 每一次都是找节点的左子节点, 然后判断左子节点和右子节点的值,找出较大的值和我们的当前的非叶子结点进行一个比较
        if(k + 1 < length && arr[k] < arr[k + 1]){// 如果此时左子节点的值小于我们的右子节点的值, 那么就让k++,k++之后k就是执行了右子节点的索引位置
            k++;
        }
        //如果判断完之后发现我们的左子节点的值要比我们的右子节点的值大, 这个时候就执行k++的操作, 那么我们的k就会是执行了左子节点的位置
        // 我们可以发现我们的k始终指向的是左子节点和右子节点中比较大的哪个

        if(temp < arr[k]){ //如果我们的当前的非叶子结点的值小于我们的当前的k执行的比较大的子节点的值,那么就执行赋值操作,并且更新我们的变量i,
            arr[i] = arr[k]; //将对应的比较大的值放到非叶子结点的位置
            i = k; //更新我们的i值,从对应的子树继续开始遍历
        }else{
            //如果判断出来我们的这个非叶子结点的值要比左右子节点的值都大的时候这个时候就结束循环,就说明当前的这个非叶子结点的位置的值已经是调整好了
            //也就是说对应的非叶子结点引导的二叉树中所有的位置都是符合我们的大顶堆的结构的条件的
            break;
        }
    }

    //当我们的for循环结束之后我们的目标位置的值还没有改变,这个时候我们进行一个赋值的操作,才算是真正的完成了这次的操作(也就是将当前非叶子结点所引导的结点变成了一个大顶堆结构)
    arr[i] = temp; //当循环结束的时候i位置就是指向了这次操作的非叶子结点要插入的位置
}

//这里我们给出执行最终的堆排序的方法
/**
     * @param arr 表示我们传入的待操作的数组, 我们要对这个传入的数组进行一个堆排序
     */
public static void heapSort(int [] arr){
    //① 我们开始的时候肯定要是从最后一个非叶子结点的位置开始遍历的, 那么我们首先就是要定位到我们的数组中的最后一个非叶子结点的位置
    for (int i = arr.length/2 - 1; i >= 0; i--) {//从最后一个非叶子结点开始遍历,每当完成一次转换之后我们就要向前遍历,去操作倒数第二个非叶子结点,然后是倒数第三个...,一直到最终操作堆顶元素为为止
        //注意: 这个时候只是执行第一步,将我们的数组转化为一个符合大顶堆要去的一个结构, 所以传入的length始终是arr.length,是不会变的
        adjustHeap(arr, i, arr.length);
    }

    //② 将堆顶元素好末尾元素进行一个元素交换, 将最大的元素沉到数组末端
    //③ 然后重新调整结构, 让我们的数组中剩余元素继续满足大顶堆的要求, 这个时候我们的传入adjustHeap()方法的length值就是要改变的了,每次一交换一次之后传入的length值都要减一
    //我们第一次排为大顶堆之后进行一个交换之后我们都是只有根节点是不满足大顶堆的要求, 所以我们之后都只需
 //要将头结点进行一个排序即可

    for (int j = arr.length -1 ; j > 0; j--){
        int temp = arr[j];
        arr[j] = arr[0];
        arr[0] = temp;

        adjustHeap(arr,0,j);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

然后给出测试代码:

@Test
public void test13(){
    //创建一个待排序数组
    int arr [] = {11,3,34,43,5343,242,54,-1};
    System.out.println("排序前的数组为: ");
    System.out.println(Arrays.toString(arr));

    //调用我们的堆排序算法
    ArraySort.heapSort(arr);

    System.out.println("排序后的数组为: ");
    System.out.println(Arrays.toString(arr));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14