【java】排序之堆排序

电玩女神 2022-10-02 15:41 164阅读 0赞

**堆排序原理**  
1.把从一个非叶子节点开始循环到根节点，把每一个父节点，左右孩子的最大值交换到父节点处。  
2.把根节点的值和最后一个元素的值交换。  
3.重新遍历堆，进行元素交换，使每一个节点都满足父节点》左孩子和右孩子的值。  
\{堆的概念：（知道可以忽略不看）  
堆是一棵顺序存储的完全二叉树。  
若每个节点的值大于等于其左、右孩子的值，这样的堆称为大根堆。  
若每个节点的值小于等于其左、右孩子的值，这样的堆称为小根堆。\}  
**图解一下**（这里我们使用大根堆）  
首先假设某个元素为序号为i，它的左孩子的位置为2i+1，右孩子的位置是2i+2。  
这里我们使用大根堆（此处演示一轮）  
![大根堆][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzcxNTc3_size_16_color_FFFFFF_t_70]  
*注意：从右向左，从下向上进行。且每轮完成后都要从(n-轮数)号元素重新开始进行。直到有序区的元素个数为n-1，整个排序过程完成。*

**代码实现**

package com.tulun.sort;
    
    import java.util.Arrays;
    import java.util.Random;
    // 此处用随机出来的数组
    public class HeapSort {
        public static void main(String[] args) {
            int[] arr = new int[10];
            Random rd = new Random();
            for (int i = 0; i < arr.length; i++) {
                arr[i] = rd.nextInt(100);
            }
    
            heapSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
    
     private static void heapSort(int[] arr) {
            int n = arr.length - 1;
    
            // 从第一个非叶子节点开始，把大值往父节点调整
            for (int i = (n - 1) / 2; i >= 0; --i) {
                adjust(arr, i, arr.length);
            }
    
            for (int i = n; i >= 0; --i) {
                //0 <=> i 它们的值进行交换
                int tmp = arr[0];
                arr[0] = arr[i];
                arr[i] = tmp;
                //再继续进行堆的调整 adjust
                adjust(arr, 0, i);
            }
        }
    
        /**
         * 堆的调整函数，把每一个节点，和其左右孩子节点的最大值放到当前节点
         * /
        private static void adjust(int[] arr, int i, int length) {
            int val = arr[i];
            for (int j = 2 * i + 1; j < length; j = 2 * j + 1) {
                // 先用j标识值最大的孩子
                if (j + 1 < length && arr[j + 1] > arr[j]) {
                    j++;
                }
    
                if (arr[j] > val) {
                    arr[i] = arr[j];
                    i = j;
                } else {
                    break;
                }
            }
            arr[i] = val;
        }
     }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzcxNTc3_size_16_color_FFFFFF_t_70]: /images/20220109/b06d4a7c62bb4bf684495a3855c1995f.png