# 数据结构与算法

# 平衡二叉树、二叉查找树、平衡二叉查找树、AVL树和红黑树的区别。

平衡二叉树：

①树的左右高度差不能超过1；

②任何往下递归的左子树与右子树，必须符合第一个性质；

③没有任何节点的空树或只有根节点的树也是平衡二叉树。

二叉查找树：二叉查找树要么是一颗空树，要么就是具有如下性质的二叉树：

①若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

②若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

③任意节点的左、右子树也分别为二叉查找树；

④没有键值相等的节点。

平衡二叉查找树：由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，又称AVL树，它是带有平衡条件的二叉查找树。它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

红黑树：主要特征是在每个节点上增加一个属性表示节点颜色，可以红色或黑色。红黑树和 AVL 树类似，都是在进行插入和删除时通过旋转保持自身平衡，从而获得较高的查找性能。与 AVL 树相比，红黑树不追求所有递归子树的高度差不超过 1，保证从根节点到叶尾的最长路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(log n)。红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除之后的自平衡调整。

红黑树在本质上还是二叉查找树，它额外引入了 5 个约束条件：① 节点只能是红色或黑色。② 根节点必须是黑色。③ 所有 NULL 节点都是黑色的。④ 一条路径上不能出现相邻的两个红色节点。⑤ 在任何递归子树中，根节点到叶子节点的所有路径上包含相同数目的黑色节点。这五个约束条件保证了红黑树的新增、删除、查找的最坏时间复杂度均为 O(log n)。如果一个树的左子节点或右子节点不存在，则均认定为黑色。红黑树的任何旋转在 3 次之内均可完成。

平衡二叉树、二叉查找树、平衡二叉查找树、AVL树和红黑树的区别：

平衡二叉树只是强调平衡而没有强调树中元素的有序性。

二叉查找树只是强调了树中数据的有序性而没有强调树的平衡。

平衡二叉查找树不但强调了数的平衡性，还强调了树中数据的有序性。

红黑树的平衡性不如 AVL 树，它维持的只是一种大致的平衡，不严格保证左右子树的高度差不超过 1。这导致节点数相同的情况下，红黑树的高度可能更高，也就是说平均查找次数会高于相同情况的 AVL 树。

在插入时，红黑树和 AVL 树都能在至多两次旋转内恢复平衡，在删除时由于红黑树只追求大致平衡，因此红黑树至多三次旋转可以恢复平衡，而 AVL 树最多需要 O(log n) 次。AVL 树在插入和删除时，将向上回溯确定是否需要旋转，这个回溯的时间成本最差为 O(log n)，而红黑树每次向上回溯的步长为 2，回溯成本低。因此面对频繁地插入与删除红黑树更加合适。

# ★★★★★ B树、B-树、B+树、B*树的区别。

B树：即二叉搜索树。 ①所有非叶子结点至多拥有两个儿子(Left和Right)； ②所有结点存储一个关键字； ③非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树。

B-树：是一种多路搜索树(并不是二叉的)。

①定义任意非叶子结点最多只有M个儿子，且M>2； ②根结点的儿子数为[2, M]； ③除根结点以外的非叶子结点的儿子数为[M/2, M]； ④每个结点存放至少M/2-1(取上整)和至多M-1个关键字；至少2个关键字，即根节点； ⑤非叶子结点的关键字个数=指向儿子的指针个数-1； ⑥非叶子结点的关键字：K[1], K[2], …, K[M-1]，且K[i] < K[i+1]； ⑦非叶子结点的指针：P[1], P[2], …, P[M]，其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树； ⑧所有叶子结点位于同一层。

例如M=3，对应的B-树如下：

B-树的搜索，从根结点开始，对结点内的关键字(有序)序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点。

B-树的特性： ①关键字集合分布在整颗树中； ②任何一个关键字出现且只出现在一个结点中； ③搜索有可能在非叶子结点结束； ④其搜索性能等价于在关键字全集内做一次二分查找； ⑤自动层次控制。由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为O(log₂n)。其中，M为设定的非叶子结点最多子树个数，N为关键字总数。所以B-树的性能总是等价于二分查找(与M值无关)，也就没有B树平衡的问题.由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并。

B+树：B+树是B-树的变体，也是一种多路搜索树。

①其定义基本与B-树同，除了以下特性； ②非叶子结点的子树指针与关键字个数相同； ③非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间)； ④为所有叶子结点增加一个链指针； ⑤所有关键字都在叶子结点出现。

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中)，其性能也等价于在关键字全集做一次二分查找；

B+的特性：

①所有关键字都出现在叶子结点的链表中(稠密索引)，且链表中的关键字恰好是有序的；

②不可能在非叶子结点命中；

③非叶子结点相当于是叶子结点的索引(稀疏索引)，叶子结点相当于是存储(关键字)数据的数据层；

④更适合文件索引系统。

例如M=3，对应的B+树如下：

B*树：是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。

B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3(代替B+树的1/2)； B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。 B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了)；

如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。所以，B*树分配新结点的概率比B+树要低，空间使用率更高。

总结

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点。 B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中。 B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。 B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3。

# 各种经典排序算法

①排序的分类

按照存储介质来分，可以分为内部排序和外部排序。

内部排序：数据一直在内存中进行的排序称为内部排序。
外部排序：当数据量很大时无法全部拷贝到内存需要使用外存的时候，称为外部排序。

按照排序的特点来分，内部排序包括比较排序和非比较排序。

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

比较排序包括插入/选择/交换/归并排序，非比较排序包括计数/基数/桶排序。插入排序包括直接插入/希尔排序，选择排序包括直接选择/堆排序，交换排序包括冒泡/快速排序。

按照数据排序的稳定性来分，可以分为稳定排序和不稳定排序。

稳定：如果数据m和n相等，排序前m在n的前面，排序后m仍在n的前面，则称为稳定排序。
不稳定：如果数据m和n相等，排序前m在n的前面，排序后m可能会出现在 n的后面，则称为不稳定排序。

②各排序算法时间复杂度对比

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	内部排序	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	内部排序	不稳定
插入排序	O(n²)	O(n)	O(n²)	O(1)	内部排序	稳定
希尔排序	O(n log n)	O(n log²n)	O(n log²n)	O(1)	内部排序	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	外部排序	稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(n log n)	内部排序	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	内部排序	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	外部排序	稳定
桶排序	O(n+k)	O(n+k)	O(n²)	O(n+k)	外部排序	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	外部排序	稳定

其中，n表示数据的数量，k表示数据的位数。

③排序算法思想

# 冒泡排序(Bubble Sort)的原理

比较相邻的元素，如果第一个比第二个大就进行交换，对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，每一轮排序后末尾元素都是有序的，这样元素越大的元素就会经由交换慢慢“沉”到数据的尾端，并且排序的无序数据每次减少一个(末尾有序的一个)，针对 n 个元素重复以上步骤 n - 1 次排序完毕。

public void bubbleSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        for (int index = 0; index < nums.length - 1 - i; index++) {
            if (nums[index] > nums[index + 1]){
           		swap(nums, index, index + 1);
            }   
        }
    }
}

1
2
3
4
5
6
7
8
9

当序列已经有序时仍会进行不必要的比较，可以设置一个标志记录是否有元素交换，如果没有直接结束比较。

public void betterBubbleSort(int[] nums) {
    boolean swap;
    for (int i = 0; i < nums.length - 1; i++) {
        swap = true;
        for (int index = 0; index < nums.length - 1 - i; index++) {
            if (nums[index] > nums[index + 1]) {
                swap(nums, index ,index + 1);
                swap = false;
            }
        }
        if (swap) break;
    }
}

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

动图演示

# 选择排序(Selection Sort)的原理

每次在未排序序列中找到最小元素，和未排序序列的第一个元素交换位置，再在剩余未排序序列中重复该操作直到所有元素排序完毕。

public void selectSort(int[] nums) {
    int minIndex;
    for (int index = 0; index < nums.length - 1; index++){
        minIndex = index;
        for (int i = index + 1;i < nums.length; i++){
            if(nums[i] < nums[minIndex])
                minIndex = i;
        }
        if (index != minIndex){
            swap(nums, index, minIndex);
        }
    }
}

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

动图演示

# 插入排序(Insertion Sort)的原理

每一趟将一个待排序记录按其关键字的大小插入到已排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

public void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int insertNum = nums[i];
        int insertIndex;
        for (insertIndex = i - 1; insertIndex >= 0 && nums[insertIndex] > insertNum; insertIndex--) {
            nums[insertIndex + 1] = nums[insertIndex];
        }
        nums[insertIndex + 1] = insertNum;
    }
}

1
2
3
4
5
6
7
8
9
10

直接插入没有利用到要插入的序列已有序的特点，插入第 i 个元素时可以通过二分查找找到插入位置 insertIndex，再把 i~insertIndex 之间的所有元素后移一位，把第 i 个元素放在插入位置上。

public void binaryInsertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int insertNum = nums[i];
        int insertIndex = -1;
        int start = 0;
        int end = i - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (insertNum > nums[mid])
                start = mid + 1;
            else if (insertNum < nums[mid])
                end = mid - 1;
            else {
                insertIndex = mid + 1;
                break;
            }
        }
        if (insertIndex == -1)
            insertIndex = start;
        if (i - insertIndex >= 0)
            System.arraycopy(nums, insertIndex, nums, insertIndex + 1, i - insertIndex);
        nums[insertIndex] = insertNum;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

动图演示

# 希尔排序(Shell Sort)的原理

又称缩小增量排序，是对直接插入排序的改进，把记录按下标的一定增量分组，对每组进行直接插入排序，每次排序后减小增量，当增量减至 1 时排序完毕。

public void shellSort(int[] nums) {
    for (int d = nums.length / 2; d > 0 ; d /= 2) {
        for (int i = d; i < nums.length; i++) {
            int insertNum = nums[i];
            int insertIndex;
            for (insertIndex = i - d; insertIndex >= 0 && nums[insertIndex] > insertNum; insertIndex -= d) {
                nums[insertIndex + d] = nums[insertIndex];
            }
            nums[insertIndex + d] = insertNum;
        }
    }
}

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

动图演示

# 归并排序(Merge Sort)的原理

归并排序基于归并操作，是一种稳定的排序算法。

**基本原理：**应用分治法将待排序序列分成两部分，然后对两部分分别递归排序，最后进行合并，使用一个辅助空间并设定两个指针分别指向两个有序序列的起始元素，将指针对应的较小元素添加到辅助空间，重复该步骤到某一序列到达末尾，然后将另一序列剩余元素合并到辅助空间末尾。

**适用场景：**数据量大且对稳定性有要求的情况。

 public void mergeSort(int[] arr) {
    int[] help = new int[arr.length];
    sort(arr, 0, arr.length - 1);
}
 
public void sort(int[] arr, int start, int end) {
    if (start == end) return;
    int mid = start + (end - start) / 2;
    sort(arr, start, mid);
    sort(arr, mid + 1, end);
    merge(arr, start, mid, end);
}
 
public void merge(int[] arr, int start, int mid, int end) {
    if (end + 1 - start >= 0) System.arraycopy(arr, start, help, start, end + 1 - start);
    int p = start;
    int q = mid + 1;
    int index = start;
    while (p <= mid && q <= end) {
        if (help[p] < help[q])
            arr[index++] = help[p++];
        else
            arr[index++] = help[q++];
    }
    while (p <= mid) arr[index++] = help[p++];
    while (q <= end) arr[index++] = help[q++];
}

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

动图演示

# 快速排序(Quick Sort)的原理

是对冒泡排序的一种改进，不稳定，平均/最好时间复杂度 O(nlogn)，元素基本有序时最坏时间复杂度 O(n²)，空间复杂度 O(logn)。

首先选择一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，一部分全部小于等于基准元素，一部分全部大于等于基准元素，再按此方法递归对这两部分数据进行快速排序。

快速排序的一次划分从两头交替搜索，直到 low 和 high 指针重合，一趟时间复杂度 O(n)，整个算法的时间复杂度与划分趟数有关。

最好情况是每次划分选择的中间数恰好将当前序列等分，经过 log(n) 趟划分便可得到长度为 1 的子表，这样时间复杂度 O(nlogn)。

最坏情况是每次所选中间数是当前序列中的最大或最小元素，这使每次划分所得子表其中一个为空表，这样长度为 n 的数据表需要 n 趟划分，整个排序时间复杂度 O(n²)。

public void quickSort(int[] nums, int start, int end) {
    if (start < end) {
        int pivotIndex = getPivotIndex(nums, start, end);
        quickSort(nums, start, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, end);
    }
}
 
public int getPivotIndex(int[] nums, int start, int end) {
    int pivot = nums[start];
    int low = start;
    int high = end;
    while (low < high) {
        while (low <= high && nums[low] <= pivot)
            low++;
        while (low <= high && nums[high] > pivot)
            high--;
        if (low < high)
            swap(nums, low, high);
    }
    swap(nums, start, high);
    return high;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

**优化：**当规模足够小时，例如 end - start < 10 时，采用直接插入排序。

动图演示

# 堆排序(Heap Sort)的原理

是对直接选择排序的改进，不稳定，时间复杂度 O(nlogn)，空间复杂度 O(1)。

将待排序记录看作完全二叉树，可以建立大根堆或小根堆，大根堆中每个节点的值都不小于它的子节点值，小根堆中每个节点的值都不大于它的子节点值。

以大根堆为例，在建堆时首先将最后一个节点作为当前节点，如果当前节点存在父节点且值大于父节点，就将当前节点和父节点交换。在移除时首先暂存根节点的值，然后用最后一个节点代替根节点并作为当前节点，如果当前节点存在子节点且值小于子节点，就将其与值较大的子节点进行交换，调整完堆后返回暂存的值。

public void add(int[] nums, int i, int num){
    nums[i] = num;
    int curIndex = i;
    while (curIndex > 0) {
        int parentIndex = (curIndex - 1) / 2;
        if (nums[parentIndex] < nums[curIndex])
            swap(nums, parentIndex, curIndex);
        else break;
        curIndex = parentIndex;
    }
}
 
public int remove(int[] nums, int size){
    int result = nums[0];
    nums[0] = nums[size - 1];
    int curIndex = 0;
    while (true) {
        int leftIndex = curIndex * 2 + 1;
        int rightIndex = curIndex * 2 + 2;
        if (leftIndex >= size) break;
        int maxIndex = leftIndex;
        if (rightIndex < size && nums[maxIndex] < nums[rightIndex])
            maxIndex = rightIndex;
        if (nums[curIndex] < nums[maxIndex])
            swap(nums, curIndex, maxIndex);
        else break;
        curIndex = maxIndex;
    }
    return result;
}

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

动图演示

# 计数排序(Counting Sort)的原理

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述：

找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加)；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

public void countingSort(int[] nums, maxValue) {
    int[] bucket = new int(maxValue + 1);
    int sortedIndex = 0;
    int arrLen = nums.length,
    int bucketLen = maxValue + 1;
    for (int i = 0; i < arrLen; i++) {
        if (!bucket[nums[i]]) {
            bucket[nums[i]] = 0;
        }
        bucket[nums[i]]++;
    }
    for (int j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            nums[sortedIndex++] = j;
            bucket[j]--;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 桶排序(Bucket Sort)的原理

将待排序数据分配到有限数量的桶里。每个桶再单独进行子排序，最后按顺序将多个桶中的数据进行合并，排序完成。当待排序的数组内的数值是均匀分配的时候，桶排序的时间复杂度为O(n)。

算法描述

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。

 public static void bucketSort(int[] arr){
     //最大最小值
     int max = arr[0];
     int min = arr[0];
     int length = arr.length;
     for(int i=1; i<length; i++) {
         if(arr[i] > max) {
             max = arr[i];
         } else if(arr[i] < min) {
             min = arr[i];
         }
     }
     //最大值和最小值的差
     int diff = max - min;
     //桶列表
     ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
     for(int i = 0; i < length; i++){
         bucketList.add(new ArrayList<>());
     }
     //每个桶的存数区间
     float section = (float) diff / (float) (length - 1);
     //数据入桶
     for(int i = 0; i < length; i++){
         //当前数除以区间得出存放桶的位置 减1后得出桶的下标
         int num = (int) (arr[i] / section) - 1;
         if(num < 0){
             num = 0;
         }
         bucketList.get(num).add(arr[i]);
     }
     //桶内排序
     for(int i = 0; i < bucketList.size(); i++){
         //jdk的排序速度当然信得过
         Collections.sort(bucketList.get(i));
     }
     //写入原数组
     int index = 0;
     for(ArrayList<Integer> arrayList : bucketList){
         for(int value : arrayList){
             arr[index] = value;
             index++;
         }
     }
 }

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

动图演示

# 基数排序(Radix Sort)的原理

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法描述

取得数组中的最大数，并取得位数；
array为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序(利用计数排序适用于小范围数的特点)。

public class RadixSort {
	public static int[] sort(int[] array,int maxDigit){
		int[] result = new int[array.length];
		//它的每一位的范围，0-9
		int[] count = new int[10];
		for(int i=0;i<maxDigit;i++){
			int division = (int)Math.pow(10,i);
			for(int n=0;n<array.length;n++){
				//求每一位的数值，进行求余
				int num = array[n]/division%10;
				//将这个每一位的数值作为count的下标，再计算其出现多少次
				count[num]++;
			}	
			//进行累加，从下标值为1开始进行累加
			for(int m=1;m<count.length;m++){
				count[m] = count[m] + count[m-1];
			}	
			//将原来的数组进行倒叙，通过累加后的count数组，
			//获取count数组每个下标所对应的值就是下标的最后一个下标出现在result的位置减一，
			//然后进行递减，这样做是稳定的，最后得到的数组的按顺序排列的
			for(int j=array.length-1;j>=0;j--){
				int num = array[j]/division%10;
				result[--count[num]] = array[j];
			}		
			//将array的数组里面的值复制为了result
			System.arraycopy(result, 0, array, 0, array.length);
			//填充count数组中的每个元素都是0,清空值
			Arrays.fill(count,0);
		}	
		return result;
	}
	//获取最高的位数
	public static int getMaxDigit(int[] array){
		int num=0;
		//获取数组中最大的值
		int maxValue = Arrays.stream(array).max().getAsInt();
		//获取它的位数
		while(maxValue!=0){
			maxValue/=10;
			num++;
		}
		return num;
	}
	public static void main(String[] args) {
		int[] array = {312,236,187,330,222,457,113};
		int[] result = sort(array,getMaxDigit(array));
		System.out.println(Arrays.toString(result));
	}
}

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

动图演示

# 排序算法怎么选择

数据量规模较小，考虑直接插入或直接选择。当元素分布有序时直接插入将大大减少比较和移动记录的次数，如果不要求稳定性，可以使用直接选择，效率略高于直接插入。

数据量规模中等，选择希尔排序。

数据量规模较大，考虑堆排序(元素分布接近正序或逆序)、快速排序(元素分布随机)和归并排序(稳定性)。

一般不使用冒泡。

← Java虚拟机 MySql数据库 →