力扣算法前置知识——复杂度+简单排序算法(3)

2024 年 7 月 23 日 19点热度 0人点赞 0条评论

文章目录

堆排序

堆结构

完全二叉树，要不然是满二叉树，要不然是按顺序填的二叉树，下图都是完全二叉树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7zv1iQXq-1651585085625)(../ZNV/%E7%AC%94%E8%AE%B0%E5%9B%BE%E7%89%87/%E5%8A%9B%E6%89%A3%E7%AE%97%E6%B3%95/image-20220502150922887.png)]

根节点位置为0

左节点位置 2*i+1
右节点位置 2*i+2
父节点位置 (i-1)/2

heapinsert操作

开始的步骤，数组的数据进行完全二叉树的插入，并且不断调正，保证全树为大根堆

heapify操作

去除最大值也就是根节点被拿去后，将最后一个节点放置在根节点，并调整全树仍然为大根堆

O(logN)级别的调整代价

堆排序

数组为：3 5 9 4 6 7 0

构建堆流程：

第一次插入：0是根节点，符合大根堆
第二次插入：5作为新加入节点，比3大所以和根节点交换，5是根节点，3是左孩子，符合大根堆
第三次插入：9作为新加入节点，比5大所以和根节点交换，9是根节点，3是左孩子，5是右孩子，符合大根堆
第四次插入：4作为新加入节点，比3大所以和父节点交换，4是父节点，3是左孩子，再比较父节点这里就是根节点比9小所以不变，符合大根堆

…

最后结构为：

9
6 7
3 4 5 0

此时将最大值也就是根节点9移除，最后一位移动到根节点，总节点数减1

继续变换为大根堆，结构为：

7
6 5
3 4 0

此时将最大值也就是根节点7移除，最后一位移动到根节点，总节点数减1

继续变换为大根堆，结构为：

周而复始，数组有序 9 7 6 5 4 3 0

堆排序的时间复杂度为O(NlogN)，空间复杂度为O(1)

package com.xyp.part03;

public class code01 {
    


    public static void heapSort(int[] arr) {
    
        if (arr == null || arr.length < 2) {
    
            return;
        }
        for (int i = 0; i < arr.length; i++) {
     // O(N)
            heapInsert(arr, i); // O(logN)
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
     // O(N)
            heapify(arr, 0, heapSize);// O(logN)
            swap(arr, 0, --heapSize);// O(1)
        }
    }


    /** * 调换父结点和当前节点的位置 * * @param arr * @param index */
    public static void heapInsert(int[] arr, int index) {
    
        while (arr[index] > arr[(index - 1) / 2]) {
    
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }


    /** * 堆化：调整树为大根堆结构 * * @param arr * @param index * @param heapSize */
    public static void heapify(int[] arr, int index, int heapSize) {
    
        int left = index * 2 + 1; //获取左孩子的下标

        //有孩子节点的时候
        while (left < heapSize) {
    
            //左右孩子值比较，获取值大的节点位置
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;

            //父节点和较大孩子值比较，获取值大的节点位置
            largest = arr[largest] > arr[index] ? largest : index;

            //如果还是本身，则终止
            if (largest == index) {
    
                break;
            }

            //不是本身，是孩子的值更大，交换位置
            swap(arr, largest, index);

            //孩子作为父结点再去比较
            index = largest;
            left = index * 2 + 1;

        }
    }

    /** * 交换两个数 * * @param arr * @param i * @param j */
    public static void swap(int[] arr, int i, int j) {
    
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    public static void main(String[] args) {
    
        int[] arr = {
    3, 5, 9, 4, 6, 7, 0};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));

    }

}

上面code是采用两步走，先构建初始数组大根堆，再逐个取出根节点

还可以采用一种方法将第一步初始化大根堆替换掉，先认识数组就是完全二叉树的，直接进行heapify方法，也就是将下面第一步的heapinsert for循环替换为下面code

for(int i = arr.length-1;i >=0;i--){
    
    heapify(arr,i,arr.length);
}

补充：

若只想移动固定k个距离就可以使得数组有序，应该如何？可采用系统自带的堆

public void sortedArrDistanceLessK(int[] arr, int k) {
    
    //默认小根堆
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    int index = 0;
    for (; index <= Math.min(arr.length, k); index++) {
    
        heap.add(arr[index]);
    }
    int i = 0;
    for (; index < arr.length; i++, index++) {
    
        heap.add(arr[index]);
        arr[i] = heap.poll();
    }
    while (!heap.isEmpty()) {
    
        arr[i++] = heap.poll();
    }

桶排序

不基于比较的排序

计数排序

没有基于比较的排序，比较浅显的例子：员工年龄，范围设置稍微大点0-200，这样就直接申请长度为201数组，每个元素都是该年龄的员工count

基数排序

三位数排序，比如是这样的数组[13，21，11，52，62]，申请两个数组空间，一个是count[10]，另外一个是bucket[和原数组等长]

第一次排序：

第一位数比较，也就是个位数，先使用计数法：
- count数组值 0 2 2 1 0 0 0 0 0 0
- count下标值 0 1 2 3 4 5 6 7 8 9
再使用前缀和：
- count数组值 0 2 4 5 5 5 5 5 5 5
- count下标值 0 1 2 3 4 5 6 7 8 9
从右往左依次填数到bucket，对应的count值依次减一
- bucket数组值 21 11 52 62 13
- bucket下标值 0 1 2 3 4
- count数组值 0 0 2 4 5 5 5 5 5 5
- count下标值 0 1 2 3 4 5 6 7 8 9
最后，赋给原数组，改变其排序
- 新原数组值 21 11 52 62 13

第二次排序：

同理，比较第二位，但此时是新原数组来进行排序

具体代码逻辑如下

package com.xyp.part03;

/** * 基数排序 */
public class code04 {
    

    public static void radixSort(int[] arr) {
    
        if (arr == null || arr.length < 2) {
    
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxbits(arr));
    }

    /** * 求最大值的位数 * * @param arr * @return */
    public static int maxbits(int[] arr) {
    
        int max = Integer.MIN_VALUE;
        for (int value : arr) {
    
            max = Math.max(max, value);
        }
        int res = 0;
        while (max != 0) {
    
            res++;
            max /= 10;
        }
        return res;
    }

    /** * @param arr * @param L * @param R * @param digit 最大值的位数 */
    public static void radixSort(int[] arr, int L, int R, int digit) {
    
        final int radix = 10; //0-9 数字
        int i = 0, j = 0;

        // 创建原始数组等长新数组
        int[] bucket = new int[R - L + 1];


        // 最大值有多少位就循环多少次
        for (int d = 1; d <= digit; d++) {
    

            // 创建长度为10的计数数组
            int[] count = new int[radix];

            // 计数法:count数组的每个元素表示该下标值的原始数的个数
            // eg:原始数组值 13 21 11 52 62，d=1
            // count数组值 0 2 2 1 0 0 0 0 0 0
            // count下标值 0 1 2 3 4 5 6 7 8 9
            for (i = L; i <= R; i++) {
    
                j = getDigit(arr[i], d);
                count[j]++;
            }

            // 前缀和数组
            // eg:原始数组值 13 21 11 52 62，d=1
            // count数组值 0 2 4 5 5 5 5 5 5 5
            // count下标值 0 1 2 3 4 5 6 7 8 9
            for (i = 1; i < radix; i++) {
    
                count[i] = count[i] + count[i - 1];
            }

            // 从右往左
            // eg:原始数组值 13 21 11 52 62，d=1
            // bucket数组值 21 11 52 62 13
            // bucket下标值 0 1 2 3 4
            // count数组值 0 0 2 4 5 5 5 5 5 5
            // count下标值 0 1 2 3 4 5 6 7 8 9
            for (i = R; i >= L; i--) {
    
                j = getDigit(arr[i], d);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }

            // 赋给原数组,改变其排序
            // eg:原始数组值 13 21 11 52 62，d=1
            // 新原数组值 21 11 52 62 13
            for (i = L, j = 0; i <= R; i++, j++) {
    
                arr[i] = bucket[j];
            }
        }
    }

    /** * 取每个数的每位数字 * @param x * @param d * @return */
    private static int getDigit(int x, int d) {
    
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }

}