首页 计算机科学 算法与数据结构

# 堆简介

  • 堆结构就是用数组实现的完全二叉树结构
  • 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
  • 完全二叉树中如果每棵子树的最小值都在顶部就是小跟堆
  • 堆结构的 heapInsert 与 heapify 操作
  • 堆结构的增大和减少
  • 优先级队列结构，就是堆结构
heapInsert操作
import java.util.Arrays;
/**
 * @Author: LightRain
 * @Description: heapInsert 操作
 * @DateTime: 2023-05-06 16:28
 * @Version：1.0
 **/
public class HeapSorting {
    /**
     * @Author: LightRain
     * @Date: 2023/5/6 16:47
     * @Param: [arr, index]
     * @Return: void
     * @Description: 某个数现在处在 index 位置，往上继续移动
     * @since 17
     */
    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;
        }
    }
    /**
     * @Author: LightRain
     * @Date: 5/5/2023 下午 6:38
     * @Param: [arr, i, j]
     * @Return: void
     * @Description: 交换
     * @since 17
     */
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
heapify操作
import java.util.Arrays;
/**
 * @Author: LightRain
 * @Description: heapify 操作
 * @DateTime: 2023-05-06 16:28
 * @Version：1.0
 **/
public class HeapSorting {
    /**
     * @Author: LightRain
     * @Date: 2023/5/6 16:48
     * @Param: [arr, index, hespSize]
     * @Return: void
     * @Description: 某个数在 index 位置，能否往下移动
     * @since 17
     */
    public static void heapify(int[] arr, int index, int hespSize) {
        // 左孩子的下标
        int left = index * 2 + 1;
        // 下方还有孩子的时候进入 while 循环
        while (left < hespSize) {
            // 两个孩子中，谁的值大，把下标给 largest
            int largest = left + 1 < hespSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // 父和较大的孩子之间，谁的值大，把下标给 largest
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
    /**
     * @Author: LightRain
     * @Date: 5/5/2023 下午 6:38
     * @Param: [arr, i, j]
     * @Return: void
     * @Description: 交换
     * @since 17
     */
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
# 堆排序
import java.util.Arrays;
/**
 * @Author: LightRain
 * @Description: 堆排序时间复杂度：O (N*logN) 空间复杂度：O (1)
 * @DateTime: 2023-05-06 16:28
 * @Version：1.0
 **/
public class HeapSorting {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        int[] arr = new int[]{90, 61, 92, 31, 78, 59};
        heapSort(arr);
        System.out.println("Arrays.stream(arr).toArray() = " + Arrays.toString(Arrays.stream(arr).toArray()));
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
    }
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //O(N)
//        for (int i = 0; i < arr.length; i++) {
//            heapInsert(arr, i);
//        }
        // 将数组变成大根堆 O (N)
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
        //O (N*logN) 的时间复杂度 空间复杂度为 O (1)
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        //O(N)
        while (heapSize > 0) {
            //O(logN)
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }
    /**
     * @Author: LightRain
     * @Date: 2023/5/6 16:47
     * @Param: [arr, index]
     * @Return: void
     * @Description: 某个数现在处在 index 位置，往上继续移动
     * @since 17
     */
    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;
        }
    }
    /**
     * @Author: LightRain
     * @Date: 2023/5/6 16:48
     * @Param: [arr, index, hespSize]
     * @Return: void
     * @Description: 某个数在 index 位置，能否往下移动
     * @since 17
     */
    public static void heapify(int[] arr, int index, int hespSize) {
        // 左孩子的下标
        int left = index * 2 + 1;
        // 下方还有孩子的时候进入 while 循环
        while (left < hespSize) {
            // 两个孩子中，谁的值大，把下标给 largest
            int largest = left + 1 < hespSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // 父和较大的孩子之间，谁的值大，把下标给 largest
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
    /**
     * @Author: LightRain
     * @Date: 5/5/2023 下午 6:38
     * @Param: [arr, i, j]
     * @Return: void
     * @Description: 交换
     * @since 17
     */
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
  1. 数组扩容并不会影响性能：O (N*logN)=O (N) 水平
  2. 使用系统自带堆结构不能高效自定义需求，需要自己手写堆结构完成自定义需求
  3. 有些情况下是必须手写堆结构才可以做到高效的
  4. 如果只需要给定一个数字然后弹出，可以使用语言自带堆结构 API 完成
# 堆排序扩展题目
  • 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过 K，并且 K 相对于数组来说比较小。
  • 请选择一个合适的排序算法针对这个数据进行排序。
import java.util.Arrays;
import java.util.PriorityQueue;
/**
 * @Author: LightRain
 * @Description: 小根堆排序
 * @DateTime: 2023-05-06 17:47
 * @Version：1.0
 **/
public class SmallRootHeap {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        int[] arr = new int[]{90, 61, 92, 31, 78, 59};
        sortedArrDistanceLessk(arr,3);
        System.out.println("Arrays.stream(arr).toArray() = " + Arrays.toString(Arrays.stream(arr).toArray()));
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
    }
    public static 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] 位置
            arr[i] = heap.poll();
        }
        while (!heap.isEmpty()){
            // 将每个数组弹出放入 arr [i++]
            arr[i++]= heap.poll();
        }
    }
}
# 比较器
  • 比较器的实质就是重载比较运算符。
  • 比较器可以很好的应用在特殊标准的排序上。
  • 比较器可以很好的应用在根据特殊标准排序的结构上。
Student.java
import java.util.Comparator;
/**
 * @Author: LightRain
 * @Description: 自定义比较器的实现
 * @DateTime: 2023-05-09 13:11
 * @Version：1.0
 **/
public class Student {
    public String name;
    public int id;
    public int age;
    public Student(String name, int id, int age) {
        this.name = name;
        this.id = id;
        this.age = age;
    }
    /**
     * @Author: LightRain
     * @Description: 自定义比较器需要实现 Comparator<?> 接口并且重写 compare 方法来实现自定义
     * @DateTime: 2023-05-09 13:11
     * @Version：1.0
     **/
    public static class IdAscendingComparator implements Comparator<Student> {
        // 返回负数的时候，第一个参数排在前面
        // 返回正数的时候，第二个参数排在前面
        // 返回 0 的时候，谁在前面无所谓
        @Override
        public int compare(Student o1, Student o2) {
            return o1.id - o2.id;
        }
    }
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", id=" + id +
                ", age=" + age +
                '}';
    }
}
Main.java
import java.util.Arrays;
/**
 * @Author: LightRain
 * @Description: 自定义比较器的使用
 * @DateTime: 2023-05-09 13:33
 * @Version：1.0
 **/
public class Main {
    public static void main(String[] args) {
        // 创建对象 根据 id 升序排列
        Student s1 = new Student("A", 2, 20);
        Student s2 = new Student("B", 3, 21);
        Student s3 = new Student("C", 1, 22);
        // 将对象添加到一个数组中
        Student[] students = {s1, s2, s3};
        // 进行数组排序并添加排序策略
        Arrays.sort(students, new Student.IdAscendingComparator());
        System.out.println("students = " + Arrays.toString(students));
    }
}
# 桶排序思想下的排序
  • 计数排序
  • 基数排序
  • 分析：
    • 桶排序思想下的排序都是不基于比较的排序
    • 时间复杂度为 O (N)，额外空间复杂度为 O (M)
    • 应用范围有限，需要样本的数据状况满足桶的划分
# 计数排序代码
import java.util.Arrays;
/**
 * 计数排序
 * 中间数组 通过数组下标来表示原始数组的值，来统计每个元素出现的次数
 * 然后新建一个数组将 中间数组 出现了几次，我就打印几次 到新的数组
 * <p>
 * 计数排序自己的理解：
 * 就是将原始数组中的数值出现的频率（次数）记录在新数组下标中，
 * 然后通过遍历循环这个新数组赋值给另一个新数组
 *
 * 时间复杂度
 * 从代码看，第一个 for 循环时间复杂度是 O (k), 第二个是 O (n), 第三个是 O (k), 第四个是 O (n)，所以总的是 O (k+n), 特别当 n==k 的时候，时间复杂度是 O (n)。
 * 计数排序不需要比较操作，也不需要交换操作，是一种简单的排序方式，但是这是一种空间换时间的排序方式，类似的空间换时间的排序还有桶排序等。
 * 特别的当 O (k)>=O (nlogn) 的时候，计数排序就不那么有效了。
 */
public class CountingSort {
    public static void main(String[] args) {
        int[] arr= new int[]{90, 61,92,31,78,59};
        int[] jspx = jspx(arr);
        System.out.println("Arrays.stream(arr).toArray() = " + Arrays.toString(Arrays.stream(jspx).toArray()));
    }
    public static int[] jspx(int[] a) {
        // 一：求取最大值和最小值，计算中间数组的长度：中间数组是用来记录原始数据中每个值出现的频率
        int max = a[0], min = a[0];
        for (int i : a) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        // 二：有了最大值和最小值能够确定中间数组的长度
        // 存储 5-0+1 = 6
        int[] pxA = new int[max - min + 1];
        // 三。循环遍历旧数组计数排序：就是统计原始数组值出现的频率到中间数组 B 中
        for (int i : a) {
            // 数的位置 上 + 1
            pxA[i - min] += 1;
        }
        // 四。遍历输出
        // 创建最终数组，就是返回的数组，和原始数组长度相等，但是排序完成的
        int[] result = new int[a.length];
        // 记录最终数组的下标
        int index = 0;
        // 先循环每一个元素  在计数排序器的下标中
        for (int i = 0; i < pxA.length; i++) {
            // 循环出现的次数，pxA [i]: 这个数出现的频率
            for (int j = 0; j < pxA[i]; j++) {
                // 以为原来减少了 min 现在加上 min，值就变成了原来的值
                result[index++] = i + min;
            }
        }
        return result;
    }
}
# 基数排序代码
import java.util.Arrays;
/**
 * @Author: LightRain
 * @Description: 基数排序
 * @DateTime: 2023-05-09 14:09
 * @Version：1.0
 **/
public class RadixSort {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        int[] arr = new int[]{90, 61, 92, 31, 78, 59};
        radixSort(arr);
        System.out.println("Arrays.stream(arr).toArray() = " + Arrays.toString(Arrays.stream(arr).toArray()));
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
    }
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxbits(arr));
    }
    /**
     * @Author: LightRain
     * @Date: 2023/5/9 14:13
     * @Param: [arr]
     * @Return: void
     * @Description: 求最大位值有几个十进制位
     * @since 17
     */
    public static int maxbits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            max = Math.max(max, i);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }
    /**
     * @Author: LightRain
     * @Date: 2023/5/9 14:23
     * @Param: [arr, l, r, digit]
     * @Return: void
     * @Description: arr [begin...end] 排序
     * digit 表示这个数组中最大的值有几个十进制位
     * @since 17
     */
    public static void radixSort(int[] arr, int l, int r, int digit) {
        // 固定长度
        final int radix = 10;
        int i = 0;
        int j = 0;
        // 有多少个数准备多少个辅助空间
        int[] bucket = new int[r - l + 1];
        // 有多少位就进出几次，有多少个十进制位就要进行多次进桶和出桶操作
        for (int d = 1; d <= digit; d++) {
            //10 个空间
            //count [0] 当前为 (d 位) 是 0 的数字有多少个
            //count [1] 当前为 (d 位) 是 (0 和 1) 的数字有多少个
            //count [2] 当前为 (d 位) 是 (0、1 和 2) 的数字有多少个
            //count [i] 当前为 (d 位) 是 (0~i) 的数字有多少个
            //count[0...9]
            int[] count = new int[radix];
            for (i = l; i <= r; i++) {
                //d 如果为 1 就去取出个位数字
                //d 如果为 2 就去取出十位数字
                //d 如果为 3 就去取出呗百位数字
                j = getDigit(arr[i], d);
                count[j]++;
            }
            for (i = 1; i < radix; i++) {
                // 把 count 处理成前缀和，累加和
                count[i] = count[i] + count[i - 1];
            }
            // 数组从右往左遍历
            for (i = r; i >= l; i--) {
                // 每个数根据你现在到了第几位，把那个位的数字取出来
                j = getDigit(arr[i], d);
                // 根据 count 值 - 1，添加到辅助数组里面
                bucket[count[j] - 1] = arr[i];
                // 单个个位的瓷频 --
                count[j]--;
            }
            for (i = l, j = 0; i <= r; i++, j++) {
                // 将辅助空间数据导入到源数组中
                arr[i] = bucket[j];
            }
        }
    }
    /**
     * @Author: LightRain
     * @Date: 2023/5/9 14:40
     * @Param: [x, d]
     * @Return: int
     * @Description: 获取数字
     * @since 17
     */
    public static int getDigit(int x, int d) {
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }
}
# 排序算法的稳定性及其汇总
  • 同样值的个体之间，如果不因为排序改变相对次序，就是这个排序是有稳定性的，否则就没有。
  • 不具备稳定性的排序：
    • 选择排序
    • 快速排序
    • 堆排序
  • 具备稳定性的排序：
    • 冒泡排序
    • 插入排序
    • 归并排序
    • 一切桶排序思想下的排序
  • 目前没有找到时间复杂度 O (N*logN), 额外空间复杂度 O (1), 又稳定的排序。
排序算法时间复杂度空间复杂度稳定性
选择排序O(N²)O(1)×
冒泡排序O(N²)O(1)√
插入排序O(N²)O(1)√
归并排序O(N*logN)O(N)√
快速排序 (随机)O(N*logN)O(logN)×
堆排序O(N*logN)O(1)×
  • 如果有空间的限制就使用堆排序。
  • 需要稳定性的时候使用归并排序。
  • 一般选择快速排序，经过常数实验快速排序是最快的排序，能用快排就用快排。
# 常见的坑
  1. 归并排序的额外空间复杂度可以变成 O (1), 但是非常难，不需要掌握，有兴趣可以搜‘归并排序’内部缓存法，但是会丧失稳定性。
  2. “原地归并排序” 的帖子都是垃圾，会让归并排序的时间复杂度变成 O (N²)。
  3. 快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜 “01 stable sort”。
  4. 所有的改进都不重要，因为目前没有找到时间复杂度 O (N*logN)，额外复杂度 O (1)，又稳定的排序。
  5. 有一道题目，是奇数放在数组左边，偶数放在数组右边，还有求原始的相对次序不变，碰到这个问题可以怼面试官。
# 工程上对排序的改进
  1. 充分利用 O (N*logN) 和 O (N²) 排序各自的优势。
  2. 稳定性的考虑。