1、常见的数据结构有哪些？

一共八大数据结构分类

• 数组
• 栈：先进后出
• 队列：先进先出
• 链表
  • 单链表： 链表中的元素的指向只能指向链表中的下一个元素或者为空，元素之间不能相互指向。也就是一种线性链表。
  • 双向链表： 是这样一个有序的结点序列，每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有两种指针，即left和right。left指针指向左边结点，right指针指向右边结点。
  • 循环链表： 是在单向链表和双向链表的基础上，将两种链表的最后一个结点指向第一个结点从而实现循环。
• 树
• 散列表：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
• 堆：堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：
  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。
• 图：
  • 图是由结点的有穷集合V和边的集合E组成
  • 按照顶点指向的方向可分为无向图和有向图

2、堆和栈的区别？

1. 栈内存
   • 栈内存首先是一片内存区域，存储的都是局部变量。
   • 凡是定义在方法中的都是局部变量（方法外的是全局变量），for循环内部定义的也是局部变量。
   • 是先加载函数才能进行局部变量的定义，所以方法先进栈，然后再定义变量，变量有自己的作用域，一旦离开作用域，变量就会被释放。
   • 栈内存的更新速度很快，因为局部变量的生命周期都很短。
2. 堆内存
   • 存储的是数组和对象（其实数组就是对象），凡是new建立的都是在堆中。
   • 堆中存放的都是实体（对象），实体用于封装数据，而且是封装多个（实体的多个属性），如果一个数据消失，这个实体也没有消失，还可以用，所以堆是不会随时释放的。
   • 但是栈不一样，栈里存放的都是单个变量，变量被释放了，那就没有了。
   • 堆里的实体虽然不会被释放，但是会被当成垃圾，Java有垃圾回收机制不定时的收取。
3. 堆与栈的区别
   • 栈内存存储的是局部变量而堆内存存储的是实体；
   • 栈内存的更新速度要快于堆内存，因为局部变量的生命周期很短；
   • 栈内存存放的变量生命周期一旦结束就会被释放，而堆内存存放的实体会被垃圾回收机制不定时的回收。

3、常见的树知道哪些？

1. 二叉树
2. 二叉查找树
3. 平衡二叉树
   • 平衡查找树之AⅥL树
   • 平衡二叉树之红黑树
4. B树
5. B+树
6. B*树

4.快速排序

1. 每一轮排序选择一个基准点（pivot）进行分区。
   • 让小于基准点的元素的进入一个分区，大于基准点的元素的进入另一个分区。
   • 当分区完成时，基准点元素的位置就是其最终位置。
2. 在子分区内重复以上过程，直至子分区元素个数少于等于 1，这体现的是分而治之的思想 （divide-and-conquer）。
3. 从以上描述可以看出，一个关键在于分区算法，常见的有洛穆托分区方案、双边循环分区方案、霍尔分区方案。

5.希尔排序

1. 首先选取一个间隙序列，如 (n/2，n/4 … 1)，n 为数组长度。
2. 每一轮将间隙相等的元素视为一组，对组内元素进行插入排序，目的有二：
   • 少量元素插入排序速度很快
   • 让组内值较大的元素更快地移动到后方
3. 当间隙逐渐减少，直至为 1 时，即可完成排序。

• 算法实现：

private static void shell(int[] a) {
    int n = a.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // i 代表待插入元素的索引
        for (int i = gap; i < n; i++) {
            int t = a[i]; // 代表待插入的元素值
            int j = i;
            while (j >= gap) {
                // 每次与上一个间隙为 gap 的元素进行插入排序
                if (t < a[j - gap]) { // j-gap 是上一个元素索引，如果 > t，后移
                    a[j] = a[j - gap];
                    j -= gap;
                } else { // 如果 j-1 已经 <= t, 则 j 就是插入位置
                    break;
                }
            }
            a[j] = t;
            System.out.println(Arrays.toString(a) + " gap:" + gap);
        }
    }
}

6.插入排序

1. 将数组分为两个区域，排序区域和未排序区域，每一轮从未排序区域中取出第一个元素，插入到排序区域（需保证顺序）。
2. 重复以上步骤，直到整个数组有序。

• 算法实现：

// 修改了代码与希尔排序一致
public static void insert(int[] a) {
    // i 代表待插入元素的索引
    for (int i = 1; i < a.length; i++) {
        int t = a[i]; // 代表待插入的元素值
        int j = i;
        System.out.println(j);
        while (j >= 1) {
            if (t < a[j - 1]) { // j-1 是上一个元素索引，如果 > t，后移
                a[j] = a[j - 1];
                j--;
            } else { // 如果 j-1 已经 <= t, 则 j 就是插入位置
                break;
            }
        }
        a[j] = t;
        System.out.println(Arrays.toString(a) + " " + j);
    }
}

7.选择排序

1. 将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放入排序子集。
2. 重复以上步骤，直到整个数组有序。

算法实现：

public static void selection(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        // i 代表每轮选择最小元素要交换到的目标索引
        int s = i; // 代表最小元素的索引
        for (int j = s + 1; j < a.length; j++) {
            if (a[s] > a[j]) { // j 元素比 s 元素还要小, 更新 s
                s = j;
            }
        }
        if (s != i) {
            swap(a, s, i);
        }
        System.out.println(Arrays.toString(a));
    }
}

   public static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

• 优化点：为减少交换次数，每一轮可以先找最小的索引，在每轮最后再交换元素

与冒泡排序比较

1. 二者平均时间复杂度都是 $O(n^2)$
2. 选择排序一般要快于冒泡，因为其交换次数少
3. 但如果集合有序度高，冒泡优于选择
4. 冒泡属于稳定排序算法，而选择属于不稳定排序
   • 稳定排序指，按对象中不同字段进行多次排序，不会打乱同值元素的顺序。
   • 不稳定排序则反之。

稳定排序与不稳定排序

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class StableVsUnstable {

    public static void main(String[] args) {
        System.out.println("=================不稳定================");
        Card[] cards = getStaticCards();
        System.out.println(Arrays.toString(cards));
        selection(cards, Comparator.comparingInt((Card a) -> a.sharpOrder).reversed());
        System.out.println(Arrays.toString(cards));
        selection(cards, Comparator.comparingInt((Card a) -> a.numberOrder).reversed());
        System.out.println(Arrays.toString(cards));

        System.out.println("=================稳定=================");
        cards = getStaticCards();
        System.out.println(Arrays.toString(cards));
        bubble(cards, Comparator.comparingInt((Card a) -> a.sharpOrder).reversed());
        System.out.println(Arrays.toString(cards));
        bubble(cards, Comparator.comparingInt((Card a) -> a.numberOrder).reversed());
        System.out.println(Arrays.toString(cards));
    }

    public static void bubble(Card[] a, Comparator<Card> comparator) {
        int n = a.length - 1;
        while (true) {
            int last = 0; // 表示最后一次交换索引位置
            for (int i = 0; i < n; i++) {
                if (comparator.compare(a[i], a[i + 1]) > 0) {
                    swap(a, i, i + 1);
                    last = i;
                }
            }
            n = last;
            if (n == 0) {
                break;
            }
        }
    }

    private static void selection(Card[] a, Comparator<Card> comparator) {
        for (int i = 0; i < a.length - 1; i++) {
            // i 代表每轮选择最小元素要交换到的目标索引
            int s = i; // 代表最小元素的索引
            for (int j = s + 1; j < a.length; j++) {
                if (comparator.compare(a[s], a[j]) > 0) {
                    s = j;
                }
            }
            if (s != i) {
                swap(a, s, i);
            }
        }
    }

    public static void swap(Card[] a, int i, int j) {
        Card t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    enum Sharp {
        diamond, club, heart, spade, black, red
    }
    static Card[] getStaticCards() {
        List<Card> list = new ArrayList<>();
        Card[] copy = Arrays.copyOfRange(Card.cards, 2, 13 * 4 + 2);
        list.add(copy[7]);
        list.add(copy[12]);
        list.add(copy[12+13]);
        list.add(copy[10]);
        list.add(copy[9]);
        list.add(copy[9+13]);
        return list.toArray(new Card[0]);
    }


    static Map<String, Integer> map = Map.ofEntries(
            Map.entry("RJ", 16),
            Map.entry("BJ", 15),
            Map.entry("A", 14),
            Map.entry("K", 13),
            Map.entry("Q", 12),
            Map.entry("J", 11),
            Map.entry("10", 10),
            Map.entry("9", 9),
            Map.entry("8", 8),
            Map.entry("7", 7),
            Map.entry("6", 6),
            Map.entry("5", 5),
            Map.entry("4", 4),
            Map.entry("3", 3),
            Map.entry("2", 2)
    );

    static class Card {
        private Sharp sharp;
        private final String number;
        private final int numberOrder;
        private final int sharpOrder;

        public Card(Sharp sharp, String number) {
            this.sharp = sharp;
            this.number = number;
            this.numberOrder = map.get(number);
            this.sharpOrder = sharp.ordinal();
        }

        private static final Card[] cards;

        static {
            cards = new Card[54];
            Sharp[] sharps = {Sharp.spade, Sharp.heart, Sharp.club, Sharp.diamond};
            String[] numbers = {"A", "K", "Q", "J", "10", "9", "8", "7", "6", "5", "4", "3", "2"};
            int idx = 2;
            for (Sharp sharp : sharps) {
                for (String number : numbers) {
                    cards[idx++] = new Card(sharp, number);
                }
            }
            cards[0] = new Card(Sharp.red, "RJ");
            cards[1] = new Card(Sharp.black, "BJ");
        }

        @Override
        public String toString() {
            return switch (sharp) {
                case heart -> "[\033[31m" + "♥" + number + "\033[0m]";
                case diamond -> "[\033[31m" + "♦" + number + "\033[0m]";
                case spade -> "[\033[30m" + "♠" + number + "\033[0m]";
                case club -> "[\033[30m" + "♣" + number + "\033[0m]";
                case red -> "[\033[31m" + "\uD83C\uDFAD" + "\033[0m]";
                case black -> "[\033[30m" + "\uD83C\uDFAD" + "\033[0m]";
            };
        }
    }
}

都是先按照花色排序（♠♥♣♦），再按照数字排序（AKQJ...）

• 不稳定排序算法按数字排序时，会打乱原本同值的花色顺序

[[♠7], [♠2], [♠4], [♠5], [♥2], [♥5]]
[[♠7], [♠5], [♥5], [♠4], [♥2], [♠2]]

原来 ♠2 在前 ♥2 在后，按数字再排后，他俩的位置变了

• 稳定排序算法按数字排序时，会保留原本同值的花色顺序，如下所示 ♠2 与 ♥2 的相对位置不变

[[♠7], [♠2], [♠4], [♠5], [♥2], [♥5]]
[[♠7], [♠5], [♥5], [♠4], [♠2], [♥2]]

8.冒泡排序

1. 依次比较数组中相邻两个元素大小，若 a[j] > a[j+1]，则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排至最后。
2. 重复以上步骤，直到整个数组有序。

算法实现：

//工具类
public class Utils {
    public static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
  
}

public static void bubble(int[] a) {
    for (int j = 0; j < a.length - 1; j++) {
        // 一轮冒泡
        boolean swapped = false; // 是否发生了交换
        for (int i = 0; i < a.length - 1 - j; i++) {
            System.out.println("比较次数" + i);
            if (a[i] > a[i + 1]) {
                // 交换元素
                Utils.swap(a, i, i + 1);
                swapped = true;
            }
        }
        System.out.println("第" + j + "轮冒泡"
                           + Arrays.toString(a));
        if (!swapped) {
            break;
        }
    }
}

• 优化点1：每经过一轮冒泡，内层循环就可以减少一次
• 优化点2：如果某一轮冒泡没有发生交换，则表示所有数据有序，可以结束外层循环。

进一步优化

public static void bubble_v2(int[] a) {
    int n = a.length - 1;
    while (true) {
        int last = 0; // 表示最后一次交换索引位置
        for (int i = 0; i < n; i++) {
            System.out.println("比较次数" + i);
            if (a[i] > a[i + 1]) {
                Utils.swap(a, i, i + 1);
                last = i;
            }
        }
        n = last;
        System.out.println("第轮冒泡"
                           + Arrays.toString(a));
        if (n == 0) {
            break;
        }
    }
}

• 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序，直接退出外层循环即可。

9.二分查找

1. 前提：有已排序数组 A（假设已经做好）
2. 定义左边界 L、右边界 R，确定搜索范围，循环执行二分查找（3、4两步）
3. 获取中间索引 M = Floor((L+R) /2)
4. 中间索引的值 A[M] 与待搜索的值 T 进行比较
   • A[M] == T 表示找到，返回中间索引
   • A[M] > T，中间值右侧的其它元素都大于 T，无需比较，中间索引左边去找，M - 1 设置为右边界，重新查找
   • A[M] < T，中间值左侧的其它元素都小于 T，无需比较，中间索引右边去找， M + 1 设置为左边界，重新查找
5. 当 L > R 时，表示没有找到，应结束循环

算法实现：

public static int binarySearch(int[] a, int t) {
    int l = 0, r = a.length - 1, m;
    while (l <= r) {
        m = (l + r) / 2;
        if (a[m] == t) {
            return m;
        } else if (a[m] > t) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return -1;
}

测试代码

public static void main(String[] args) {
    int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};
    int target = 47;
    int idx = binarySearch(array, target);
    System.out.println(idx);
}

解决整数溢出问题

当 l 和 r 都较大时，l + r 有可能超过整数范围，造成运算错误，解决方法有两种：

int m = l + (r - l) / 2;

还有一种是：

int m = (l + r) >>> 1;