查找

查找操作是指在给定的数据集合中，根据特定的条件找到一个特定的数据项。这个数据项可能是一个值、一个键或一个属性。查找操作的时间复杂度是衡量查找效率的重要指标，它表示了查找操作所需的时间与数据项数量的关系。常用的查找算法

  • 线性查找：这是最基本的查找算法，它按照顺序逐个比较数据项，直到找到目标数据项或遍历完整个数据集合。线性查找的时间复杂度为O(n)，其中n为数据集合的大小。
  • 二分查找：二分查找是一种高效的查找算法，适用于已排序的数据集合。它将数据集合分成两半，然后根据目标值与中间值的比较结果，排除一半的数据，继续在另一半数据中进行查找。二分查找的时间复杂度为O(log n)。
  • 哈希查找：哈希查找利用哈希表数据结构进行查找。它将数据项的键通过哈希函数转换为对应的地址，然后在该地址处存储该数据项的值。哈希查找的时间复杂度一般为O(1)，但在哈希冲突严重的情况下，时间复杂度可能会退化到O(n)。
  • B树查找：B树是一种平衡的多路搜索树，它能够保持数据的有序性，并支持快速的插入、删除和查找操作。B树查找的时间复杂度为O(log n)。
  • 散列查找：散列查找是一种利用哈希函数将键映射到桶中的数据结构进行查找的方法。它能够快速地定位到目标数据项的桶，然后在桶中继续进行线性查找。散列查找的时间复杂度一般为O(1)。

顺序查找

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

1
2
3
4
5
6
7
8
9
10
int Sequential_Search(int *a,int n,int key)    //a为数组，n为要查找数组长度，key为待查找关键词
{
    int i;
    for(i = 1;i <= n;i++)    //遍历数组内的每一条记录,元素记录是从1开始
    {
        if(a[i] == key)    //如果查找到，则返回记录所在位置
            return i;
    }
    return 0;    //如果未查找到，则返回0
}

二分查找*

二分查找的实现方式有很多种，大多数都是通过修改维护两端的指针构造的。

二分查找的思路简单，我们需要找的数据都是在数组中，只要将这个数组分为两个部分，然后在左边找不到就到右边找，然后再把剩下的数组分为两部分，以此类推。

二分查找采用双指针的形式，来对我们数组序列进行遍历。二分查找只使用于排好序的数组，不适用于其他。掌握二分查找的关键是，要明白数组是怎么分成两部分，两部分的边界是什么组成的。如果按照顺序查找的话就是按照对应序列一个一个找，直到找到目标为止，没有找到就返回-1

1
2
3
4
5
6
7
int a[N];
int ans;
for(int i = 1;i<N;i++){
    if(a[i] == ans) return true;
  else break;
}
if(a[N]!=ans) return false;

这可以用蓝红划分数组来解释，假设我们数组开始全是灰色(没有被遍历)，设计一个蓝色指针指向数组的最左边，从左往右扫到蓝红边界，直到扫到目标值。

然后也同样，也可以在最右边设计一个红色指针，从右往左扫直到扫到蓝红边界，直到扫到我们的目标值。

这样的算法是十分低效的，原因是因为指针移动速度缓慢，每次只能在数组中搜索到一个值的信息。在上面的基础上，我们用蓝红表示二分数组中两个不同的区域：

如果我们在数组中间发现一个指针为蓝色，那么很显然这个指针之前的颜色全为蓝色：

同样的我们在右侧发现了一个红色区域块，就可以推断出其右侧区域都是红色

通过这样不断操作，直到找到我们的蓝红边界：

我们为什么要找蓝红边界，因为二分有几个常见的问题需要我们解决，在下面代码中ans是红蓝边界，对这个值我们有如下问题：

  • 找到第一个>=ans的元素
  • 找到最后一个<ans的元素
  • 找到第一个>ans的元素
  • 找到最后一个<=ans的元素

经过蓝红区块的分类，我们可以把问题转化为每一次找ans时，与ans比较的m（目标值）是属于蓝色区块的还是红色区块的。例如

  • 找到第一个>=ans的元素：m在红色位置(红蓝边界的右侧)
  • 找到最后一个<ans的元素：m在蓝色位置(红蓝边界的左侧)
  • 找到第一个>ans的元素：m在红色位置(同上)
  • 找到最后一个<=ans的元素：m在蓝色位置

理论还是理论，接下来根据这个思路我们建立几个代码模型来验证这种思路是否可行！

注意未遍历的位置都是灰色！！！！我们的目的是将这个数组染色，让它只有红蓝两种颜色，这个对于理解红蓝分区二分很重要！！！

1
2
3
4
5
6
7
8
9
10
11
//1.定义双指针维护区域
l = -1,r = N; // 这里的数组是0-n-1的
while(l+1!=r) //l+1 = r的时候说明红蓝区域相融了
{
    m = (l+r)/2;
    // 2.如果m节点是蓝色节点
    if(isBlue(m)) l = m; // m节点是蓝色节点，其左侧都是蓝色
    else r = m; // m是红色节点，其右侧都是红色
}

return l or r // 最终找到的位置处，需要区分

开始l指针指向蓝色区域，r指针指向红色区域，循环直到达到边界，保持l,r颜色不发生改变，遍历结束l,r就达到了蓝红边界处。二分查找的时间复杂度是o(log n)，也就是一直在折半。为什么l区域初始化为-1，这是因为我们需要在数组中分蓝和红区域，如果将l初始化为1，恰好数组中全是红色区域，这样就矛盾了。同理，r也不可以取r-1这个位置，也会导致矛盾。

那么就可以根据不同的问题来构造这个isBlue(如果你喜欢也可以判断red)函数,这是一个布尔函数主要用途是判断在红蓝边界的左右侧，从而辅助实现我们的二分查找。这里实现的二分查找有两个需要完成重点

  1. 指定红蓝边界(已经完成)
  2. 返回目标位置

这里的返回目标位置，关键在于直接把 m 的值当作目标值进行比较：如果大于目标值，则 m 在红色区域；如果小于目标值，则 m 在蓝色区域。下面就开始构造模版(下面代码可运行)

  • 找到第一个>=ans的元素：m在红色区域(ans的右边)，最终返回的是r
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
#include <iostream>
#include <vector>
// 判断蓝色区域，反之就是红色区域
bool isBlue(const std::vector<int>& array, int m, int ans) {
	return array[m] < ans; 
}
// 目的是填色找到《红蓝边界》
int binarySearch(const std::vector<int>& array, int ans) {
    int l = -1, r = array.size(); 

    while (l + 1 != r) {
        int m = (l + r) / 2;
        
        if (isBlue(array, m, ans)) {
            l = m;  // m左边都是蓝色
        } else {
            r = m;  // m右边都是红色
        }
    }

    return r;// 第一个大于或等于ans的元素，是红色
}

int main() {
    std::vector<int> array = {2,3,4,5,5,5,5,5,6}; // Sorted array
    int ans = 5; // The target value

    int index = binarySearch(array, ans);
    if (index != -1) {
        std::cout << "找到了值第一个>= " << ans << " 位置是: " << index 
                  << " (值是: " << array[index] << ")" << std::endl;
    } else {
        std::cout << "找不到或者是输入有误" << ans << std::endl;
    }

    return 0;
}
  • 找到最后一个<ans的元素：m在蓝色位置(比对的左边)，最终返回l
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
#include <iostream>
#include <vector>
// 判断蓝色区域，反之就是红色区域
bool isBlue(const std::vector<int>& array, int m, int ans) {
	return array[m] < ans; 
}
// 目的是填色找到《红蓝边界》
int binarySearch(const std::vector<int>& array, int ans) {
    int l = -1, r = array.size(); 

    while (l + 1 != r) {
        int m = (l + r) / 2;
        
        if (isBlue(array, m, ans)) {
            l = m;  // m左边都是蓝色
        } else {
            r = m;  // m右边都是红色
        }
    }

    return l; //最后一个<ans的元素，是蓝色
}

int main() {
    std::vector<int> array = {2,3,4,5,5,5,5,5,6}; // Sorted array
    int ans = 5; // The target value

    int index = binarySearch(array, ans);
    if (index != -1) {
        std::cout << "找到了值最后一个< " << ans << " 位置是: " << index 
                  << " (值是: " << array[index] << ")" << std::endl;
    } else {
        std::cout << "找不到或者是输入有误" << ans << std::endl;
    }

    return 0;
}
  • 找到第一个>ans的元素：m在红色区域，最终返回的是r
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
#include <iostream>
#include <vector>
// 判断蓝色区域，反之就是红色区域
bool isBlue(const std::vector<int>& array, int m, int ans) {
	return array[m] <= ans; 
}
// 目的是填色找到《红蓝边界》
int binarySearch(const std::vector<int>& array, int ans) {
    int l = -1, r = array.size(); 

    while (l + 1 != r) {
        int m = (l + r) / 2;
        
        if (isBlue(array, m, ans)) {
            l = m;  // m左边都是蓝色
        } else {
            r = m;  // m右边都是红色
        }
    }

    return r; 
}

int main() {
    std::vector<int> array = {2,3,4,5,5,5,5,5,6}; // Sorted array
    int ans = 5; // The target value

    int index = binarySearch(array, ans);
    if (index != -1) {
        std::cout << "找到了第一个> " << ans << " 位置是: " << index 
                  << " (值是: " << array[index] << ")" << std::endl;
    } else {
        std::cout << "找不到或者是输入有误" << ans << std::endl;
    }

    return 0;
}
  • 找到最后一个<=ans的元素：m在蓝色位置，返回的是l
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
#include <iostream>
#include <vector>
// 判断蓝色区域，反之就是红色区域
bool isBlue(const std::vector<int>& array, int m, int ans) {
	return array[m] <= ans; 
}
// 目的是填色找到《红蓝边界》
int binarySearch(const std::vector<int>& array, int ans) {
    int l = -1, r = array.size(); 

    while (l + 1 != r) {
        int m = (l + r) / 2;
        
        if (isBlue(array, m, ans)) {
            l = m;  // m左边都是蓝色
        } else {
            r = m;  // m右边都是红色
        }
    }

    return l; 
}

int main() {
    std::vector<int> array = {2,3,4,5,5,5,5,5,6}; // Sorted array
    int ans = 5; // The target value

    int index = binarySearch(array, ans);
    if (index != -1) {
        std::cout << "找到了最后一个<= " << ans << " 位置是: " << index 
                  << " (值是: " << array[index] << ")" << std::endl;
    } else {
        std::cout << "找不到或者是输入有误" << ans << std::endl;
    }

    return 0;
}

这里的初始数组需要定义在0-n-1，也就是从索引0开始，一共n-1-0+1= n个数据

我们需要检查 m（二分值）是否始终落在数组的有效范围内。初始时，l（左边界）和 r（右边界）的最小值分别为 0 和 1。此时，m 的最小值为 (0 + 1) / 2 = 0，即索引为 0 的元素。根据循环退出条件，当 l + 1 == r 时，循环退出。因此，l 的最大值为 N-2，r 的最大值为 N-1。

相应的，m 的最大值为 (N-2 + N-1) / 2 = (2N-3) / 2，近似为 N/2。确保 m 始终在数组范围内是通过这些边界值控制的。

更新指针的时候，都是指向蓝红边界的位置，如果我们改变为l = m+1会导致区域发生错误，我们就用更新为m和r的模版就行，不会搞乱自己。

死循环问题：全部问题都会归类为第一种退出循环的方式

分块查找

分块查找是结合了二分查找和顺序查找的一种改进方法，分块查找会讲原始的数组分为几块，并用一个辅助数组存储其每个块的核心信息。通常这个核心信息包括两种

  • 最大关键字
  • 起始地址

对于每一个分块，都会用其起始地址来区分。例如地址区间1-6说明是在第一个分块，地址区间7-12说明是在第二个分块，这个分块的长度需要我们自己定义。对于最大关键字，其作用是用于比对目标数据在哪一个分块，这里通常使用二分法。根据比对最大关键字的位置信息，我们能够确定一个具体的范围。在用二分法查询到具体的数据分块时，对于这个数据分块使用顺序查找在O(1)的时间内就可解决问题。分块查找不要求整体数据是有序的，但是要求索引有序方便定位数据是在哪一个块中。

假设要查找关键字 38 的具体位置。首先将 38依次和索引表中各最大关键字进行比较，因为22 < 38 < 48，所以可以确定 38如果存在，肯定在第二个子表中。

由于索引表中显示第二子表的起始位置在查找表的第 7 的位置上，所以从该位置开始进行顺序查找，一直查找到该子表最后一个关键字（一般将查找表进行等分，具体子表个数根据实际情况而定）。结果在第10的位置上确定该关键字即为所找。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <stdlib.h>

// 1.辅助结构体用于分块，这里是将整个数组分为三块
struct index 
{ 
    // 定义块的结构
    int key;
    int start;
} newIndex[3];  // 定义结构体数组

int search(int key, int a[]);

int cmp(const void *a, const void *b)
{
    // 按照 key 进行排序
    return (*(struct index*)a).key > (*(struct index*)b).key ? 1 : -1;
}

int main()
{
    int i, j = -1, k, key;
    int a[] = {33, 42, 44, 38, 24, 48, 22, 12, 13, 8, 9, 20, 60, 58, 74, 49, 86, 53};
    
    // 确认模块的起始值和最大值
    for (i = 0; i < 3; i++) 
    {
        newIndex[i].start = j + 1; // 确定每个块范围的起始值
        j += 6;
        newIndex[i].key = a[newIndex[i].start]; // 初始化最大值
        for (int k = newIndex[i].start; k <= j; k++) 
        {
            if (newIndex[i].key < a[k]) 
            {
                newIndex[i].key = a[k];
            }
        }
    }

    // 2.对结构体按照 key 值进行排序，这里用的是快排
    qsort(newIndex, 3, sizeof(newIndex[0]), cmp);

    // 输入要查询的数，并调用函数进行查找
    printf("请输入您想要查找的数：\n");
    scanf("%d", &key);
    k = search(key, a);

    // 输出查找的结果
    if (k >= 0) 
    {
        printf("查找成功！您要找的数在数组中的位置是：%d\n", k + 1);
    }
    else
    {
        printf("查找失败！您要找的数不在数组中。\n");
    }

    return 0;
}

int search(int key, int a[])
{
    int i = 0;

    // 3.二分查找确定在哪个块中
    while (i < 3 && key > newIndex[i].key) 
    {
        i++;
    }

    if (i >= 3) 
    {
        // 大于分得的块数，则返回-1
        return -1;
    }

    // 4.在找到的块中进行顺序查找
    int start = newIndex[i].start;
    int end = (i == 2) ? 17 : newIndex[i].start + 5;  // 确定块的结束位置

    while (start <= end && a[start] != key) 
    {
        start++;
    }

    if (start > end) 
    {
        return -1;
    }

    return start;
}

分块查找在现实生活中也很常用。

例如，一个学校有很多个班级，每个班级有几十个学生。给定一个学生的学号，要求查找这个学生的相关资料。显然，每个班级的学生档案是分开存放的，没有任何两个班级的学生的学号是交叉重叠的，那么最好的查找方法实现确定这个学生所在的班级，然后再在这个学生所在班级的学生档案中查找这个学生的资料。上述查找学生资料的过程，实际上就是一个典型的分块查找。

树型查找在图论中有做说明，这里不再重复

排序*

排序（Sorting）是计算机科学中最基础和常用的算法之一，它是将一组数据按照某种规则重新排列的过程。排序算法通常用于解决大规模数据的分类、归纳和分析问题。排序算法涉及到许多细节，包括算法的复杂度、稳定性、内存占用等方面。因此，要理解排序算法，需要从多个角度进行分析。

一、时间复杂度

排序算法的时间复杂度是判断其效率的重要指标，它通常用大O记法（Big O notation）来表示。常见的排序算法有冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序等等。每种排序算法都有不同的时间复杂度，其中最优的时间复杂度为O(nlogn)。归并排序、快速排序、堆排序均实现了O(nlogn)的复杂度，而其他排序算法的时间复杂度则相对较高。

二、稳定性

在排序算法中，稳定性是指排序前和排序后具有相同值的元素之间的顺序是否保持不变。例如，在学生成绩表中，如果有多个学生的分数相同，那么排序后他们之间的排名是否保持不变。稳定性对于实际应用非常重要，比如在对英文文本排序时，要求相同的字符串顺序不变，以保持原有的语义。插入排序、冒泡排序、归并排序、基数排序等算法是稳定的，而选择排序、快速排序、希尔排序、堆排序等算法则是不稳定的。

其中稳定性是描述排序过程中数据变动的情况，举个例子排序一个结构体

1
2
3
4
struct RA{
    int key;
    int value;
}
1
(4, A), (2, B), (3, C), (2, D), (4, E)

目标：按 value 的字母顺序 排序。如果使用稳定排序，排序结果可能是：

1
(2, B), (2, D), (3, C), (4, A), (4, E)

value 为 B 和 D 的元素，它们的 key 分别是 2 和 2，(2, B) 在原始数组中比 (2, D) 靠前，排序后相对位置未变，说明是稳定的排序。如果使用不稳定排序，结果可能是:

1
(2, D), (2, B), (3, C), (4, A), (4, E)

value 为 B 和 D 的元素的相对位置发生了变化，因此这是不稳定的排序。

三、内存占用

排序算法的效率不仅取决于时间复杂度，还受到内存占用的影响。某些排序算法需要额外的内存空间来完成排序操作，而其他算法则可以在原有的内存空间中就地完成排序。此外，一些排序算法在最坏情况下的内存占用量可能非常大，甚至超出可接受范围。插入排序、归并排序、基数排序等算法通常需要额外的内存空间，而选择排序、冒泡排序、快速排序、堆排序则不需要额外的内存空间。

四、内部排序和外部排序的区分

其中内部排序和外部排序的区分，是在于数据是否完全存储于内存中。最显著的区分就是他们的运算速度和运算范围。内部排序的特点就是运算速度快，但是限于内存的大小，只能运算小数量级的排序。符合内部排序的有：冒泡排序，插入排序，选择排序，快速排序，归并排序，堆排序，希尔排序。

外部排序一般会在名字上备注，且通常会使用IO流来控制数据的导入与导出(磁盘-内存)。以下介绍的基本排序函数，都不属于外部排序。

任何排序的核心思想就是将序列分为两个部分，第一部分是有序序列，其中存储的都是有序的数；另部分就是无序的数据，是尚未遍历到是未知顺序的数据。通常排序过程中，都会涉及到获取数据 - 移动数据；其中的时间复杂度基本上取决于这两者。预测排序算法的时间复杂度通常会使用概率等工具构造其复杂度函数。

交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。其中冒泡排序是稳定的，而快速排序通常是不稳定的。

冒泡排序

冒泡排序（Bubble Sort）基本思想：类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来(当然也可以反着来)，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。直观表达，每一趟遍历，将一个最大的数移到序列末尾。也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，将他们之间小的，或者大的值交换过来。遍历数列的工作是重复地进行，直到没有再需要交换的，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。总结有三个步骤

  1. 比较相邻的元素，如果前一个比后一个大，交换之。
  2. 第一趟排序第i个和第i+1个比较与交换，随后第i+1个和第i+2个一对比较交换，这样直到倒数第n-1个和最后n个，将最大的数移动到最后一位。
  3. 第二趟将第二大的数移动至倒数第二位
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
50
51
52
53
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 10
// 1.交换操作
Swap(int *p1, int * p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void Print(int *a)
{
    for (int i=0;i<N;i++)
    {
        printf("%d ",a[i]);
    }
}
// 2. 冒泡排序
void BubbleSort(int* a, int n)
{
    // 外部循环，维护排序区块和未排序区块
    for (int j=0;j<n;++j)
    {
        int size = 0;
        // 在未排序区块中，比较和交换直到最大值排列在排序完成的区块中
        for (int i=1;i<N-j;++i)
        {
            // 比较和交换
            if (a[i-1]>a[i])
            {
                Swap(&a[i-1],&a[i]);
                size =1;
            }
        }
        // 3.标记是否执行排序，未执行则提前跳出
        if (size==0)
        {
            break;
        }
    }
}
int main()
{
    int a[N] = {0};
    for (int i=0;i<N;++i)
    {
        a[i] = rand();
    }
    BubbleSort(a,N);
    Print(a);
    
    return 0;
}

教科书上实现的冒泡排序，比较工整

1
2
3
4
5
6
7
8
9
10
11
12
13
void BubbleSort(ElemType A[],int n){
    for(int i = 0;i<n-1;i++){
        bool flag = false;
        // 这里改为正序也可以
        for(int j=n-1;j>i;j--){
            if(A[j-1]>A[j]) {
                swap(A[j-1],j[j]); //逆序交换
            	flag = true;
            }
		}
         if(flag==false) return;
    }   
}

冒泡排序是一种稳定的排序手法，其时间复杂度是O(n^2)，平均时间复杂度是O(n^2)。冒泡排序产生的有序子序列一定是全局有序的。全局有序通常指的是一个数据集合中所有元素都按照某种排序规则排列好。

快速排序

快速排序(Quicksort)是Hoare于1962年提出的一种二叉树结构的交换排序方法，有时候也叫做划分交换排序，是一个高效的算法，其基本思想为：任取待排序 元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有 元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。这是一个分治算法，而且它就在原地交换数据排序。

分治法的意思是将一个大问题转化为几个小问题，通过解决完成全部小问题然后返回值构成大问题的解而成。由于每个小问题的解决方法都是一致的，所以选择使用递归来实现这些操作。具体实现快速排序是这样的，用基准值将序列分为两部分，左部分小于基准值，右部分大于基准值。然后在这两个部分都执行下述操作。

  • 首先选举出一个基准值，对基准值的操作具体要看你的要求，这里假设要从小到大
  • 将小于当前基准值的数据放在数据左侧
  • 将大于当前基准值的数据放在数据右侧

由于快速排序每次递归将序列分为两个子序列，递归的深度决定了其空间复杂度。在理想情况下，递归深度为 log(n)，因此快速排序的空间复杂度为 O(log(n))。但在最坏情况下，递归深度为 n，此时的空间复杂度会增加到 O(n)。

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
50
51
52
53
54
55
56
57
58
59
60
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//打印
void Print(int *a,int n)
{
    for (int i=0;i<n;++i)
    {
        printf("%d ",a[i]);
    }
}
//挖坑法
void QuickSort(int* a,int left,int right)//升序
{
    if (left < right)
    {
        int begin = left;
        int end = right;
        int pivot = begin;//记录坑位的下标
        int key = a[begin];//坑值
        while (begin < end)
        {
            //右边找小，放到左边
            while (begin < end && a[end] >= key)//与坑值比较
            {
                --end;
            }
            //小的放在左边的坑里，自己形成了新的坑位
            a[pivot] = a[end];
            pivot = end;
            //左边找大，放在右边
            while (begin < end && a[begin] <= key)//与坑值比较
            {
                ++begin;
            }
            //大的放在右边的坑里，自己形成了新的坑位
            a[pivot] = a[begin];
            pivot = begin;
        }
        //最后将坑值给到坑位
        a[pivot] = key;
        //[left,right]
        //[left,pivot-1]  [pivot+1,right]
        //左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归
        QuickSort(a, left, pivot - 1);
        QuickSort(a, pivot + 1, right);
    }
    else
    {
        return;
    }
}
int main()
{
    int a[10] = {0,9,5,6,3,2,1,7,8,4};
    //挖坑法
    QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);
    //打印
    Print(a,sizeof(a) / sizeof(a[0]));
    return 0;
}

快排的缺点

根据上面的代码，我们来分析一下快排的缺点：

如何解决快排对有序数据排序效率很差的方法？：三数取中法

所谓三数取中，不是取最大值，最小值，以及他们的中间值，而是取左边（begin）、右边（end）和中间（begin+end）/2。在有序的情况下中间的值刚好就是二分，将取出的值作为坑位，就不会出现最差的这种情况。我们依旧使用区间的开头作为坑值，但是要使用三数取中的逻辑。

1
2
3
4
5
6
7
8
9
10
int begin = left;
int end = right;
//使用三数取中选“坑值”，用mid存储其下标
int mid = GetMidIndex(a, begin, end);
//将区间首值当作坑位
//坑值与首值交换，避免算法混乱
//一般我们会将区间首值作为坑值
Swap(&a[begin], &a[mid]);//传地址调用
//存储坑值
int key = a[begin];
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
int GetMidIndex(int *a,int left,int right)
{
    //二分
    int mid = (right - left) / 2;
    if (a[left]<a[mid])
    {
        if (a[left]<a[right])
        {
            if (a[mid]<a[right])
            {
                return mid;
            }
            else  //a[mid]>=a[right]
            {
                return right;
            }
        }
        else   //a[left]>=a[right]
        {
            return left;
        }
    }
    else  //a[left]>=a[mid]
    {
        if (a[mid]<a[right])
        {
            if (a[left]<a[right])
            {
                return left;
            }
            else  //a[left]>=a[right]
            {
                return right;
            }
        }
        else  //a[mid]>=a[right]
        {
            return mid;
        }
    }
}

经过三数取中的处理，就不会出现快排的最坏情况，但也几乎不会成为最好的情况，有利有弊，我们在面试的过程中只需要写基础版的快排即可，以防时间不够。

小区间优化：

关于如果处理数据多，相应的递归次数多，会不会影响操作快排的性能？

当我们在使用快排对大量数据进行排序时，我们可以采用小区间优化，减少递归次数，达到优化程序得到目的。

  • 对当待处理数据大于10的子序列进行快排递归。
  • 对当待处理数据低于10的子序列进行直接插入排序进行排序，避免递归次数过多。
  • 这个10不是固定的，可以根据处理的数据量调整。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//区间[left,right]
//左区间[left,pivot-1]  右区间[pivot+1,right]
//左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归
// 小区间优化
if (pivot - 1 - left > 10)//对当待处理数据大于于10的子序列进行快排递归排序
{
    //快排
    QuickSort(a,left,pivot-1);
}
else
{
    //采用直接插入排序，对当待处理数据低于10的子序列进行排序，避免递归
    InsertSort(a+left,pivot-1-left+1);//为什么最后要加1,例如：区间[0,9]实际上有10个数
}
if (right - (pivot + 1) > 10)
{
    QuickSort(a,pivot+1,right);
}
else
{
    InsertSort(a + pivot+1, right-(pivot+1)+1);
}
左右指针法*

根据上图的示例我们应该能够理解左右指针法是什么样的逻辑，跟挖坑法是一样的思想，单趟排序完毕实现左边比坑位小，右边比坑位大。但是即使左右指针法跟挖坑法的思想是一样的，但是他们单趟的运算结果是不一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		//选坑位
		int mid = GetMidIndex(a, begin, end);//三数取中
		Swap(&a[begin], &a[mid]);
		int key = begin;
		while (begin < end)
		{
			while (begin < end && a[end] <= a[key])
				--end;
			while (begin < end && a[begin] >= a[key])
				++begin;
			Swap(&a[begin], &a[end]);
		}
		Swap(&a[begin], &a[key]);
		//分治递归
		QuickSort(a, left, begin - 1);
		QuickSort(a, begin + 1, right);
	}
}
前后指针法
  1. 采用perv记录区间第一个元素的下标，采用cur记录区间第二个元素的下标。
  2. cur找小，每次遇到比key(坑值)小的值就停下来，++prev。
  3. 交换prev和cur位置的值
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
//左右指针法
void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		//选坑位
		int mid = GetMidIndex(a, left,right);//三数取中
		Swap(&a[left], &a[mid]);
		int key = left;
		//初始化指向
		int prev = left, cur = left + 1;
		while (cur<=right)
		{
			if (a[cur] <= a[key])//&&++prev!=cur
			{
				++prev;
				//避免无效操作
				if(cur!=prev)
				Swap(&a[prev],&a[cur]);
			}
			++cur;
		}
		Swap(&a[key], &a[prev]);
		//分治递归
		QuickSort(a, left, prev - 1);
		QuickSort(a, prev + 1, right);
	}
}

插入排序

前面说过，任何排序的核心思想就是将序列分为两个部分，第一部分是有序序列，其中存储的都是有序的数；另部分就是无序的数据，是尚未遍历到是未知顺序的数据。

插入排序的核心思想与斗地主抓牌类似，假设发牌员将无序的牌堆在牌桌上，为了区分，我们认为手中的牌是有序的。每次从无序的牌堆接收到一个新的牌，将之插入到有序的序列当中，也就是抓牌整理排序。直接插入排序的时间复杂度是O(n^2)，因为有两层循环。第一层从无序的位置找到一张牌，第二层将这个牌插入到有序的位置。

码牌的时候将无序的牌插入到手中的牌，每次插完有序+1，无序-1。直到无序部分没有牌为止。如果在无序牌堆中，所有的牌是正序的时候，其时间复杂度会降低到O(n)，也就是仅仅插入而不用进行比较。（但是正序序列为什么需要排序呢？）

插入排序的步骤可以简单概括为以下几个阶段：

  1. 初始状态：将数组的第一个元素视为已排序部分，其余部分为未排序部分。
  2. 逐个插入：从未排序部分选择一个元素，将其插入到已排序部分的正确位置。为了插入，将已排序部分中大于待插入元素的元素向右移动一个位置。
  3. 重复：重复上述插入步骤，直到所有元素都被插入到已排序部分。
  4. 完成：当算法完成时，整个数组就被排序了。

具体代码如下，声明一个单指针i来遍历我们的数组，然后使用一个j内循环指针，对排序完成的区域进行一次遍历移动，然后将对应的i指针的数据插入到对应的位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void sort(int array[],int length){
    for(int i = 1;i < length;i++){
        //1.从无序牌堆中找到的牌
        int key = array[i];
        //2.变量指向的是有序牌堆
        int j = i-1;
	   //3.从有序牌堆中找到适合key的位置插入,插入位置设置为j(已经排序完成)的前面
        while(j>=0 && array[j]>key){
            // 移动位置为插入腾出空间
            array[j+1] = array[j];
            j--;
        }
        //插入正确位置 - 完工
        array[j+1] = key;
    }
}

折半插入排序

折半插入排序是对直接插入排序的一种优化。在直接插入排序中，待排序元素需要从后向前逐个与已排序序列的元素比较，以确定插入位置。这对基本有序的数列效率较高，但在乱序情况下，比较次数较多。

折半插入排序通过二分查找来确定插入位置，从而减少了查找过程中的比较次数。相比普通插入排序，折半插入排序将比较和移动操作分离，使用二分查找降低了查找部分的时间复杂度至O(log n)，但元素的移动次数仍然保持在O(n)，因此总的时间复杂度仍为O(n^2)。折半插入排序是一种稳定排序算法，因为相等元素的相对顺序不会改变。

算法步骤

设数组为a[0…n]。

  1. 将原序列分成有序区和无序区。a[0…i-1]为有序区，a[i…n]为无序区。（i从1开始）
  2. 从无序区中取出第一个元素，即a[i]，使用二分查找算法在有序区中查找要插入的位置索引j。
  3. 将a[j]到a[i-1]的元素后移，并将a[i]赋值给a[j]。
  4. 重复步骤2~3，直到无序区元素为0。
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
void InsertSort(ElemType A[], int n)
{
    int i, j, low, high, mid;
    
    // 1.i 从 2 开始，因为 A[1] 已经是自然有序的
    for (i = 2; i <= n; i++) 
    {
        A[0] = A[i]; // 将 A[0] 作为哨兵变量，保存当前无序数据
        low = 1;
        high = i - 1;
        
        // 二分查找插入位置
        while (low <= high) 
        {
            mid = (low + high) / 2;
            if (A[mid] > A[0]) 
                high = mid - 1; // 插入点在左侧
            else 
                low = mid + 1;  // 插入点在右侧
        }

        // 2.移动元素，为插入留出空间。主要耗时间的部分
        for (j = i - 1; j >= low; --j) 
        {
            A[j + 1] = A[j];
        }
        
        A[low] = A[0]; // 在 low 位置插入元素
    }
}

不难看出，折半插入排序仅仅是减少了比较元素的次数，约为O(nlogn)，而且该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n；而元素的移动次数没有改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍然为O(n²)，但它的效果还是比直接插入排序要好。

  • 最好时间复杂度O(n)
  • 平均时间复杂度O(n²)
  • 最坏时间复杂度O(n²)

希尔排序操作*

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2）的第一批算法之一。

前面提到，当一个数组的大部分元素是从大到小排序的时候，如果要用插入排序来实现从小到大排序，就需要做很多次swap(移动数据)，就像上面的[6, 5, 4, 3, 2, 1]这个例子一样。这种情况下，希尔排序会先把数组处理成大部分元素都是从小到大排序，然后再用插入排序来最后处理，这样就能大量减少swap，提升排序效率。 我们用一个例子来看希尔排序工作的过程：

[61, 109, 149, 111, 34, 2, 24, 119, 122, 27]首先，数组一共有10个元素（size = 10）。

第一轮、先用size/2做为间隔（gap），我们可以理解成是把原数组，按照间隔来分成了小数组，并对小数组进行插入排序。这里gap = 5，小数组为[61, 2]、[109, 24]、[149, 119]、[111, 122]、[34, 27]。

对小数组进行插入排序：[2, 61]、[24, 109]、[119, 149]、[111, 122]、[27, 34]。我们并不改变原数组，所以排序后的原数组为[2, 24, 119, 111, 27, 61, 109, 149, 122, 34]。可以看到，经过一轮排序，原数组数值较大的一些元素到了数组的后面，这样能大大减少后面插入排序的swap次数。

第二轮、gap = gap/2 = 2。继续将原数组(这个是关键)分为两个小数组，并对小数组进行插入排序。[2, 119, 27, 109, 122]、[24, 111, 61, 149, 34]

两个小数组排序后为：[2, 27, 109, 119, 122]、[24, 34, 61, 111, 149]。因为不改变原数组，所以原数组这时为[2, 24, 27, 34, 109, 61, 119, 111, 122, 149]

第三轮，gap = gap/2 = 1。这是最后一轮，其实就是将第二轮排序后的数组，进行插入排序。

理解希尔排序的重点是gap的划分是对原数组!!!!进行划分的，对于每次的gap的分组进行直接插入排序，然后再缩小gap的大小直到gap为1

当数组长度为n的时候，我们要做lg(n)轮排序。lg(n)轮排序，就是一个for loop，这个好理解。那么for loop里面，每一轮排序代码是什么样的？

第一轮：gap = 5，大的数组分成了5个小数组（[61, 2]、[109, 24]、[149, 119]、[111, 122]、[34, 27]）。从index 5到9，要做5次插入（insertion）。

第二轮：gap = 2，大的数组分成了2个小数组（[2, 119, 27, 109, 122]、[24, 111, 61, 149, 34]）。从index 2到9， 要做8次插入（insertion）。

我们知道说，对一个数组进行插入排序的时候，每一次插入，都要跟前面有序的元素进行对比，但一旦比有序元素更大，就停止对比，完成插入。

  • 序号为2的元素先是跟0比较，序号2的值比序号0的值大，不需要swap，完成插入；
  • 序号为4的先跟序号2先比较，因为比2小，所以要swap，再跟序号0比较；
  • 序号为6的先跟序号4比较，swap，再跟序号2比较，停止并完成插入；
  • 序号为8的先跟序号6比较，因为比6大，直接停止比较。

以此类推，实现代码如下

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
# include <stdio.h>

void shellsort(int arr[], int n) {
    int gap, i, j, temp;
	// 1.gap隔离整个数组，并逐步降低gap值
    for(gap = n/2; gap > 0; gap /= 2)
        // 对每一个分组进行插入操作，这一步不会改变整个数组！！
        for(i = gap; i < n; i++)
            for(j = i - gap; j >= 0 && arr[j] > arr[j+gap]; j -= gap) {
                temp = arr[j];
                arr[j] = arr[j+gap];
                arr[j+gap] = temp;
            }
}

int main() {
    int arr[] = {61, 109, 149, 111, 34, 2, 24, 119, 122, 27}; 
    int size = sizeof arr / sizeof arr[0];
    shellsort(arr, size); 

    for(int i = 0; i < size; i++) {
        printf("i: %d\n", arr[i]); 
    }
    return 0; 
}

选择排序

它的基本思想是: 首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序是一种简单直观的排序算法，无论什么数据进去都是O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。同时选择排序是不稳定的排序方法。

那如何选出最小的一个元素呢。很容易想到：先随便选一个元素假设它为最小的元素（默认为无序区间第一个元素），然后让这个元素与无序区间中的每一个元素进行比较，如果遇到比自己小的元素，那更新最小值下标，直到把无序区间遍历完，那最后的最小值就是这个无序区间的最小值。

下面以数列{20,40,30,10,60,50}为例，演示它的选择排序过程(如下图)。

第1趟： i=0。找出a[1...5]中的最小值a[3]=10，然后将a[0]和a[3]互换。 数列变化: 20,40,30,10,60,50 -- > 10,40,30,20,60,50

第2趟：i=1。找出a[2...5]中的最小值a[3]=20，然后将a[1]和a[3]互换。 数列变化: 10,40,30,20,60,50 -- > 10,20,30,40,60,50

第3趟：i=2。找出a[3...5]中的最小值，由于该最小值大于a[2]，该趟不做任何处理。

第4趟：i=3。找出a[4...5]中的最小值，由于该最小值大于a[3]，该趟不做任何处理。

第5趟：i=4。交换a[4]和a[5]的数据。 数列变化: 10,20,30,40,60,50 -- > 10,20,30,40,50,60

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 实现代码
void SelectSort(ElemType A[],int n){
    for(int i = 0;i<n-1;i++)
    {
        // 1.最小值位置 - 相对于未排序部分来说
        int min = i;
        for(int j = i+1;j<n;j++)
        {
            if(A[j]<A[min]) min = j; // 记录最小值位置
        }
        // 2.与最小值位置交换 - 作为已排序位置
        if(min!=i) swap(A[i],A[min]); 
    }
}

选择排序的交换操作介于0和 (n - 1)次之间。选择排序的比较操作为n(n - 1)/2次。选择排序的赋值操作介于0和 3(n - 1) 次之间，1次交换对应三次赋值。

比较次数O(n^2)，比较次数与关键字的初始状态无关，总的比较次数N = (n-1) + (n-2) + ... +1 = n*(n-1)/2。

交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。选择排序每交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多(n-1)次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

  • 最好时间复杂度：最好情况是输入序列已经升序排列，需要比较n*(n-1)/2次，但不需要交换元素，即交换次数为：0；所以最好时间复杂度为О(n²)。
  • 最坏时间复杂度：最坏情况是输入序列是逆序的，则每一趟都需要交换。即需要比较n*(n-1)/2次，元素交换次数为：n-1次。所以最坏时间复杂度还是*О(n²)。

原地操作几乎是选择排序的唯一优点，当空间复杂度要求较高时，可以考虑选择排序；选择排序实际适用的场合非常罕见。

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

第一步、构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

  • 假设给定无序序列结构如下
  • 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
  • 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
  • 这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，我们就将一个无需序列构造成了一个大根堆。

第二步、将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

  • 将堆顶元素9和末尾元素4进行交换
  • 重新调整结构，使其继续满足堆定义
  • 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

再简单总结下堆排序的基本思路：

  1. 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
  2. 将堆顶元素与末尾元素交换，将最大元素沉到数组末端;
  3. 重新调整结构，也就是堆化。使新的树满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤直到整个序列有序。

顺序排序

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
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <algorithm>

// 构造大根堆
void adjustHeap(std::vector<int>& arr, int parent, int length) {
    int temp = arr[parent];  // 保存当前父节点的值
    int child = 2 * parent + 1;  // 左孩子节点索引

    while (child < length) {
        // 如果右孩子存在，且大于左孩子，选择右孩子
        if (child + 1 < length && arr[child] < arr[child + 1]) {
            child++;
        }

        // 如果子节点大于父节点，将子节点的值赋给父节点
        if (arr[child] > temp) {
            arr[parent] = arr[child];
            parent = child;
            child = 2 * parent + 1;  // 更新子节点，继续向下调整
        } else {
            break;  // 子树已经是大顶堆，退出循环
        }
    }
    arr[parent] = temp;  // 将原父节点的值放在最终位置
}

// 堆排序函数
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 1. 构建初始大顶堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, n);  // 从最后一个非叶子节点开始调整
    }

    // 2. 交换堆顶元素与末尾元素，调整堆
    for (int j = n - 1; j > 0; j--) {
        std::swap(arr[0], arr[j]);  // 将堆顶元素移到末尾，新树少一个节点
        adjustHeap(arr, 0, j);  // 调整剩余元素，重新堆化
    }
}

int main() {
    std::vector<int> arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    heapSort(arr);
    
    // 输出排序后的数组
    std::cout << "Sorted array: ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

逆序排序

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
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <algorithm>

// 调整小根堆
void adjustHeap(std::vector<int>& arr, int parent, int length) {
    int temp = arr[parent];  // 保存当前父节点的值
    int child = 2 * parent + 1;  // 左孩子节点索引

    while (child < length) {
        // 如果右孩子存在，且小于左孩子，选择右孩子
        if (child + 1 < length && arr[child] > arr[child + 1]) {
            child++;
        }

        // 如果子节点小于父节点，将子节点的值赋给父节点
        if (arr[child] < temp) {
            arr[parent] = arr[child];
            parent = child;
            child = 2 * parent + 1;  // 更新子节点，继续向下调整
        } else {
            break;  // 子树已经是小根堆，退出循环
        }
    }
    arr[parent] = temp;  // 将原父节点的值放在最终位置
}

// 堆排序函数（逆序）
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 1. 构建初始小根堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, n);  // 从最后一个非叶子节点开始调整
    }

    // 2. 交换堆顶元素与末尾元素，调整堆
    for (int j = n - 1; j > 0; j--) {
        std::swap(arr[0], arr[j]);  // 将堆顶元素移到末尾
        adjustHeap(arr, 0, j);  // 调整剩余元素，重新构建小根堆
    }
}

int main() {
    std::vector<int> arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    heapSort(arr);
    
    // 输出逆序排序后的数组
    std::cout << "Sorted array (descending): ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

归并排序

归并排序（MERGE-SORT）是一种基于归并思想的排序算法，采用经典的分治策略。分治法将问题分解为多个小问题，递归求解后，再在合并阶段将各个子问题的解整合起来，从而完成整个排序。

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

精髓就是把归和并拆成两个部分，就容易理解

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
using namespace std;

// 函数声明：归并排序和合并两个有序子数组
void mergeSort(vector<int>& arr, int left, int right, vector<int>& temp);
void merge(vector<int>& arr, int left, int mid, int right, vector<int>& temp);

int main() {
    // 初始化待排序数组
    vector<int> arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    
    // 临时数组用于存放合并过程中的结果
    vector<int> temp(arr.size());

    // 对数组进行归并排序
    mergeSort(arr, 0, arr.size() - 1, temp);

    // 输出排序后的数组
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

// 1.归并排序函数
// 参数：arr - 待排序数组，left - 左边界，right - 右边界，temp - 临时数组
void mergeSort(vector<int>& arr, int left, int right, vector<int>& temp) {
    if (left < right) {
        // 防止(left + right)溢出，计算中间位置
        int mid = left + (right - left) / 2;

        // 递归对左右两部分进行归并排序
        mergeSort(arr, left, mid, temp);
        mergeSort(arr, mid + 1, right, temp);

        // 合并已排序的左右部分
        merge(arr, left, mid, right, temp);
    }
}

// 2.合并两个有序子数组
// 参数：arr - 待合并数组，left - 左边界，mid - 中间位置，right - 右边界，temp - 临时数组
void merge(vector<int>& arr, int left, int mid, int right, vector<int>& temp) {
    int i = left;      // 左半部分起始索引
    int j = mid + 1;   // 右半部分起始索引
    int t = 0;         // 临时数组索引

    // 合并两个子数组到临时数组
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t++] = arr[i++];  // 左侧元素较小，存入temp
        } else {
            temp[t++] = arr[j++];  // 右侧元素较小，存入temp
        }
    }

    // 复制剩余的左半部分元素 - 如果有的话
    while (i <= mid) {
        temp[t++] = arr[i++];
    }

    // 复制剩余的右半部分元素 - 如果有的话
    while (j <= right) {
        temp[t++] = arr[j++];
    }

    // 将临时数组的元素拷贝回原数组
    t = 0;
    while (left <= right) {
        arr[left++] = temp[t++];
    }
}

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

桶排序

下列算法都是“非比较排序算法”，它们的时间复杂度可以达到线性阶。

「桶排序 bucket sort」是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并

算法流程

考虑一个长度为 n 的数组，元素是范围 [0,1) 的浮点数。桶排序的流程如下图所示。

  1. 初始化 k 个桶，将 n 个元素分配到 k 个桶中。
  2. 对每个桶分别执行排序.
  3. 按照桶的从小到大的顺序，合并结果。

桶排序适用于处理体量很大的数据。例如，输入数据包含 100 万个元素，由于空间限制，系统内存无法一次性加载所有数据。此时，可以将数据分成 1000 个桶，然后分别对每个桶进行排序，最后将结果合并。

  • 时间复杂度 O(n+k) ：假设元素在各个桶内平均分布，那么每个桶内的元素数量为 n/k 。假设排序单个桶使用O(n/k * log⁡n/k) 时间，则排序所有桶使用O(nlog⁡n/k)时间。当桶数量 k 比较大时，时间复杂度则趋向于 O(n)。合并结果时需要遍历所有桶和元素，花费O(n+k)时间。
  • 自适应排序：在最坏情况下，所有数据被分配到一个桶中，且排序该桶使用O(n^2)时间。
  • 空间复杂度 O(n+k)、非原地排序：需要借助 k 个桶和总共 n 个元素的额外空间。
  • 桶排序是否稳定取决于排序桶内元素的算法是否稳定。

如何实现平均分配

桶排序的时间复杂度理论上可以达到O(n) ，关键在于将元素均匀分配到各个桶中，因为实际数据往往不是均匀分布的。例如，我们想要将淘宝上的所有商品按价格范围平均分配到 10 个桶中，但商品价格分布不均，低于 100 元的非常多，高于 1000 元的非常少。若将价格区间平均划分为 10 份，各个桶中的商品数量差距会非常大。

为实现平均分配，我们可以先设定一个大致的分界线，将数据粗略地分到 3 个桶中。分配完毕后，再将商品较多的桶继续划分为 3 个桶，直至所有桶中的元素数量大致相等。

如下图所示，这种方法本质上是创建一个递归树，目标是让叶节点的值尽可能平均。当然，不一定要每轮将数据划分为 3 个桶，具体划分方式可根据数据特点灵活选择。

如果我们提前知道商品价格的概率分布，则可以根据数据概率分布设置每个桶的价格分界线。值得注意的是，数据分布并不一定需要特意统计，也可以根据数据特点采用某种概率模型进行近似。如下图所示，我们假设商品价格服从正态分布，这样就可以合理地设定价格区间，从而将商品平均分配到各个桶中。

计数排序

「计数排序 counting sort」通过统计元素数量来实现排序，通常应用于整数数组。先来看一个简单的例子。给定一个长度为 n 的数组 nums ，其中的元素都是非负整数，计数排序的整体流程如下图所示。

  1. 遍历数组，找出数组中的最大数字，记为 m ，然后创建一个长度为 m+1 的辅助数组 counter 。
  2. 借助 counter 统计 nums 中各数字的出现次数，其中 counter[num] 对应数字 num 的出现次数。统计方法很简单，只需遍历 nums（设当前数字为 num），每轮将 counter[num] 增加 1 即可。
  3. 由于 counter 的各个索引天然有序，因此相当于所有数字已经被排序好了。接下来，我们遍历 counter ，根据各数字的出现次数，将它们按从小到大的顺序填入 nums 即可。

从桶排序的角度看，我们可以将计数排序中的计数数组 counter 的每个索引视为一个桶，将统计数量的过程看作是将各个元素分配到对应的桶中。本质上，计数排序是桶排序在整型数据下的一个特例。

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
50
51
#include <iostream>
#include <vector>
using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;

    // 找到数组中的最大值和最小值
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    
    // 创建计数数组，大小为最大值与最小值之间的差值 + 1
    vector<int> count(maxVal - minVal + 1, 0);
    
    // 统计每个元素的出现次数
    for (int num : arr) {
        count[num - minVal]++;
    }

    // 填回原数组
    int index = 0;
    for (int i = 0; i < count.size(); i++) {
        while (count[i] > 0) {
            arr[index++] = i + minVal;
            count[i]--;
        }
    }
}

int main() {
    vector<int> arr = {9, 4, 1, 7, 9, 1, 2, 0, 5, 8, 1, 4, 2};
    
    // 输出排序前的数组
    cout << "Before Sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    
    // 进行计数排序
    countingSort(arr);

    // 输出排序后的数组
    cout << "After Sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

如果输入数据是对象，上述步骤 3. 就失效了。假设输入数据是商品对象，我们想要按照商品价格（类的成员变量）对商品进行排序，而上述算法只能给出价格的排序结果。

前缀和可以帮助我们准确确定每个元素在排序后的正确位置，并且在处理相同元素时保证它们的相对顺序不会改变，这就是稳定性的由来。

那么如何才能得到原数据的排序结果呢？我们首先计算 counter 的前缀和。顾名思义，索引 i 处的前缀和 prefix[i] 等于数组前 i 个元素之和：

前缀和具有明确的意义，prefix[num] - 1 代表元素 num 在结果数组 res 中最后一次出现的索引。这个信息非常关键，因为它告诉我们各个元素应该出现在结果数组的哪个位置。接下来，我们倒序遍历原数组 nums 的每个元素 num ，在每轮迭代中执行以下两步。

  1. 将 num 填入数组 res 的索引 prefix[num] - 1 处。
  2. 令前缀和 prefix[num] 减小 1 ，从而得到下次放置 num 的索引。

遍历完成后，数组 res 中就是排序好的结果，最后使用 res 覆盖原数组 nums 即可。下图展示了完整的计数排序流程。

稳定的计数排序

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
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;

    // 找到数组中的最大值和最小值
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    
    // 创建计数数组，大小为最大值与最小值之间的差值 + 1
    vector<int> count(maxVal - minVal + 1, 0);

    // 统计每个元素的出现次数
    for (int num : arr) {
        count[num - minVal]++;
    }

    // 计算前缀和，确定每个元素在最终排序中开始的位置
    for (int i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }

    // 创建一个临时数组存储排序结果
    vector<int> sortedArr(arr.size());

    // 从后往前遍历原数组，保证计数排序的稳定性
    for (int i = arr.size() - 1; i >= 0; i--) {
        int value = arr[i];
        int position = count[value - minVal] - 1;  // 根据前缀和确定位置
        sortedArr[position] = value;
        count[value - minVal]--;  // 更新计数数组
    }

    // 将排序后的结果拷贝回原数组
    arr = sortedArr;
}

int main() {
    vector<int> arr = {9, 4, 1, 7, 9, 1, 2, 0, 5, 8, 1, 4, 2};
    
    // 输出排序前的数组
    cout << "Before Sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    
    // 进行计数排序
    countingSort(arr);

    // 输出排序后的数组
    cout << "After Sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}
  • 时间复杂度 O(n+m)：涉及遍历 nums 和遍历 counter ，都使用线性时间。一般情况下 n≫m ，时间复杂度趋于 O(n)。
  • 空间复杂度 O(n+m)、非原地排序：借助了长度分别为 n 和 m 的数组 res 和 counter 。
  • 稳定排序：由于向 res 中填充元素的顺序是从右向左的，因此倒序遍历 nums 可以避免改变相等元素之间的相对位置，从而实现稳定排序。实际上，正序遍历 nums 也可以得到正确的排序结果，但结果是非稳定的。

计数排序只适用于非负整数。若想要将其用于其他类型的数据，需要确保这些数据可以被转换为非负整数，并且在转换过程中不能改变各个元素之间的相对大小关系。例如，对于包含负数的整数数组，可以先给所有数字加上一个常数，将全部数字转化为正数，排序完成后再转换回去即可。

计数排序适用于数据量大但数据范围较小的情况。比如，在上述示例中 m 不能太大，否则会占用过多空间。而当 n≪m 时，计数排序使用 O(m) 时间，可能比O(nlog⁡n)的排序算法还要慢。

基数排序

「基数排序 radix sort」的核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。

以学号数据为例，假设数字的最低位是第 1 位，最高位是第 8 位，基数排序的流程如下图所示。

  1. 初始化位数 k=1 。
  2. 对学号的第 k 位执行“计数排序”。完成后，数据会根据第 k 位从小到大排序。
  3. 将 k 增加 1 ，然后返回步骤 2. 继续迭代，直到所有位都排序完成后结束。

下面来剖析代码实现。对于一个 d 进制的数字 x ，要获取其第 k 位 x_k ，可以使用以下计算公式：

其中 ⌊a⌋ 表示对浮点数 a 向下取整，而 mod  d 表示对 d 取余。对于学号数据，d=10 且 k∈[1,8]。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 获取数字d位上的数值（从右往左数，d从1开始）
int getDigit(int num, int d) {
    return (num / static_cast<int>(pow(10, d - 1))) % 10;
}

// 计数排序，用于对数字的d位进行排序
void countingSortByDigit(vector<int>& arr, int d) {
    int n = arr.size();
    vector<int> output(n);  // 用于存放排序后的数组
    vector<int> count(10, 0);  // 基数为10，因为我们在处理0-9的数字

    // 统计每个数字d位上出现的次数
    for (int num : arr) {
        int digit = getDigit(num, d);
        count[digit]++;
    }

    // 计算前缀和，确保排序的稳定性
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 反向遍历数组，根据计数数组将元素按d位进行排序
    for (int i = n - 1; i >= 0; i--) {
        int digit = getDigit(arr[i], d);
        output[--count[digit]] = arr[i];
    }

    // 将排序后的结果拷贝回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 基数排序
void radixSort(vector<int>& arr) {
    if (arr.empty()) return;

    // 找到数组中的最大值
    int maxVal = *max_element(arr.begin(), arr.end());

    // 找到最大值的位数
    int maxDigits = 0;
    while (maxVal > 0) {
        maxDigits++;
        maxVal /= 10;
    }

    // 按每一位从低到高进行计数排序
    for (int d = 1; d <= maxDigits; d++) {
        countingSortByDigit(arr, d);
    }
}

int main() {
    // 测试数组
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};

    // 输出排序前的数组
    cout << "Before Sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // 进行基数排序
    radixSort(arr);

    // 输出排序后的数组
    cout << "After Sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

相较于计数排序，基数排序适用于数值范围较大的情况，但前提是数据必须可以表示为固定位数的格式，且位数不能过大。例如，浮点数不适合使用基数排序，因为其位数k过大，可能导致时间复杂度O(nk)>>O(n^2)

  • 时间复杂度 O(nk)：设数据量为 n、数据为 d 进制、最大位数为 k ，则对某一位执行计数排序使用 O(n+d) 时间，排序所有 k 位使用 O((n+d)k) 时间。通常情况下，d 和 k 都相对较小，时间复杂度趋向 O(n) 。
  • 空间复杂度 O(n+d)、非原地排序：与计数排序相同，基数排序需要借助长度为 n 和 d 的数组 res 和 counter 。
  • 稳定排序：与计数排序相同。

散列表

「哈希表 hash table」，又称「散列表」，其通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表输入一个键 key ，则可以在 O(1) 时间内获取对应的值 value 。

如下图所示，给定 n个学生，每个学生都有“姓名”和“学号”两项数据。假如我们希望实现“输入一个学号，返回对应的姓名”的查询功能，则可以采用下图所示的哈希表来实现。

除哈希表外，数组和链表也可以实现查询功能，它们的效率对比如下表所示。

  • 添加元素：仅需将元素添加至数组（链表）的尾部即可，使用 O(1) 时间。
  • 查询元素：由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用 O(n)O(n)O(n) 时间。
  • 删除元素：需要先查询到元素，再从数组（链表）中删除，使用 O(n)O(n)O(n) 时间。

表 - 元素查询效率对比

数组 链表 哈希表
查找元素 O(n) O(n) O(1)
添加元素 O(1) O(1) O(1)
删除元素 O(n) O(n) O(1)

观察发现，在哈希表中进行增删查改的时间复杂度都是 O(1) ，非常高效。

哈希表的常见操作包括：初始化、查询操作、添加键值对和删除键值对等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 初始化哈希表 */
unordered_map<int, string> map;

/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map[12836] = "小哈";
map[15937] = "小啰";
map[16750] = "小算";
map[13276] = "小法";
map[10583] = "小鸭";

/* 查询操作 */
// 向哈希表输入键 key ，得到值 value
string name = map[15937];

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.erase(10583);

哈希表有三种常用遍历方式：遍历键值对、遍历键和遍历值。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 遍历哈希表 */
// 遍历键值对 key->value
for (auto kv: map) {
    cout << kv.first << " -> " << kv.second << endl;
}
// 单独遍历键 key
for (auto kv: map) {
    cout << kv.first << endl;
}
// 单独遍历值 value
for (auto kv: map) {
    cout << kv.second << endl;
}

哈希表简单实现

我们先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为「桶 bucket」，每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。

那么，如何基于 key 来定位对应的桶呢？这是通过「哈希函数 hash function」实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key ，输出空间是所有桶（数组索引）。换句话说，输入一个 key ，我们可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。

输入一个 key ，哈希函数的计算过程分为以下两步。

  1. 通过某种哈希算法 hash() 计算得到哈希值。
  2. 将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index 。
1
index = hash(key) % capacity

随后，我们就可以利用 index 在哈希表中访问对应的桶，从而获取 value 。

设数组长度 capacity = 100、哈希算法 hash(key) = key ，易得哈希函数为 key % 100 。下图以 key 学号和 value 姓名为例，展示了哈希函数的工作原理。

以下代码实现了一个简单哈希表。其中，我们将 key 和 value 封装成一个类 Pair ，以表示键值对

1
[file]{array_hash_map}-[class]{array_hash_map}-[func]{}

哈希冲突与扩容

本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况。

对于上述示例中的哈希函数，当输入的 key 后两位相同时，哈希函数的输出结果也相同。例如，查询学号为 12836 和 20336 的两个学生时，我们得到：

1
2
12836 % 100 = 36
20336 % 100 = 36

如下图所示，两个学号指向了同一个姓名，这显然是不对的。我们将这种多个输入对应同一输出的情况称为「哈希冲突 hash collision」

容易想到，哈希表容量 nnn 越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，我们可以通过扩容哈希表来减少哈希冲突。

如下图所示，扩容前键值对 (136, A) 和 (236, D) 发生冲突，扩容后冲突消失。

类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时。并且由于哈希表容量 capacity 改变，我们需要通过哈希函数来重新计算所有键值对的存储位置，这进一步提高了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

「负载因子 load factor」是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常被作为哈希表扩容的触发条件。

通常情况下哈希函数的输入空间远大于输出空间，因此理论上哈希冲突是不可避免的。比如，输入空间为全体整数，输出空间为数组容量大小，则必然有多个整数映射至同一桶索引。

哈希冲突会导致查询结果错误，严重影响哈希表的可用性。为解决该问题，我们可以每当遇到哈希冲突时就进行哈希表扩容，直至冲突消失为止。此方法简单粗暴且有效，但效率太低，因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率，我们可以采用以下策略。

  1. 改良哈希表数据结构，使得哈希表可以在存在哈希冲突时正常工作。
  2. 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。

哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。

链式地址

在原始哈希表中，每个桶仅能存储一个键值对。「链式地址 separate chaining」将单个元素转换为链表，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中。下图展示了一个链式地址哈希表的例子。

基于链式地址实现的哈希表的操作方法发生了以下变化。

  • 查询元素：输入 key ，经过哈希函数得到桶索引，即可访问链表头节点，然后遍历链表并对比 key 以查找目标键值对。
  • 添加元素：先通过哈希函数访问链表头节点，然后将节点（即键值对）添加到链表中。
  • 删除元素：根据哈希函数的结果访问链表头部，接着遍历链表以查找目标节点，并将其删除。

链式地址存在以下局限性。

  • 占用空间增大，链表包含节点指针，它相比数组更加耗费内存空间。
  • 查询效率降低，因为需要线性遍历链表来查找对应元素。

以下代码给出了链式地址哈希表的简单实现，需要注意两点。

  • 使用列表（动态数组）代替链表，从而简化代码。在这种设定下，哈希表（数组）包含多个桶，每个桶都是一个列表。
  • 以下实现包含哈希表扩容方法。当负载因子超过 2/3 时，我们将哈希表扩容至 2 倍。
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <list>
#include <vector>
using namespace std;

class HashTable {
private:
    int bucketCount;  // 哈希表桶的数量
    int elementCount; // 当前元素数量
    vector<list<int>> table;

    // 哈希函数
    int hashFunction(int key) {
        return key % bucketCount;
    }

    // 扩容哈希表，当负载因子超过 2/3 时调用
    void rehash() {
        // 将哈希表大小扩展为原来的2倍
        int newBucketCount = bucketCount * 2;
        vector<list<int>> newTable(newBucketCount); // 新的哈希表

        // 重新哈希所有元素到新的表中
        for (int i = 0; i < bucketCount; i++) {
            for (int key : table[i]) {
                int newIndex = key % newBucketCount;
                newTable[newIndex].push_back(key);
            }
        }

        // 替换旧表
        table = move(newTable);
        bucketCount = newBucketCount;
    }

    // 检查是否需要扩容
    void checkLoadFactor() {
        float loadFactor = (float)elementCount / bucketCount;
        if (loadFactor > 2.0 / 3.0) {
            rehash();  // 扩容操作
        }
    }

public:
    // 构造函数
    HashTable(int size) {
        bucketCount = size;
        elementCount = 0;
        table.resize(bucketCount);
    }

    // 插入数据
    void insert(int key) {
        int index = hashFunction(key);
        table[index].push_back(key);
        elementCount++;  // 更新元素数量
        checkLoadFactor();  // 检查负载因子是否超过阈值
    }

    // 删除数据
    void remove(int key) {
        int index = hashFunction(key);
        table[index].remove(key);
        elementCount--;  // 更新元素数量
    }

    // 查找数据
    bool search(int key) {
        int index = hashFunction(key);
        for (int x : table[index]) {
            if (x == key) {
                return true;
            }
        }
        return false;
    }

    // 打印哈希表
    void display() {
        for (int i = 0; i < bucketCount; i++) {
            cout << "Bucket " << i << ":";
            for (int x : table[i]) {
                cout << " " << x;
            }
            cout << endl;
        }
    }
};

int main() {
    HashTable ht(7);  // 创建初始大小为 7 的哈希表

    // 插入数据
    ht.insert(15);
    ht.insert(11);
    ht.insert(27);
    ht.insert(8);
    ht.insert(12);
    ht.insert(20);
    ht.insert(21);  // 插入更多数据以触发扩容

    // 显示哈希表
    ht.display();

    // 查找数据
    cout << "Search 15: " << (ht.search(15) ? "Found" : "Not Found") << endl;
    cout << "Search 23: " << (ht.search(23) ? "Found" : "Not Found") << endl;

    // 删除数据
    ht.remove(15);
    ht.display();

    return 0;
}

值得注意的是，当链表很长时，查询效率O(n)很差。此时可以将链表转换为“AVL 树”或“红黑树”，从而将查询操作的时间复杂度优化至 O(log⁡n) 。

开放寻址

「开放寻址 open addressing」不引入额外的数据结构，而是通过多次探测来处理哈希冲突，探测方式主要包括线性探测、平方探测、多次哈希等。

下面将主要以线性探测为例，介绍开放寻址哈希表的工作机制与代码实现。

线性探测

线性探测采用固定步长的线性搜索来进行探测，其操作方法与普通哈希表有所不同。

  • 插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为 1 ），直至找到空桶，将元素插入其中。
  • 查找元素：若发现哈希冲突，则使用相同步长向后线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None 。

下图展示了开放寻址（线性探测）哈希表的键值对分布。根据此哈希函数，最后两位相同的 key 都会被映射到相同的桶。而通过线性探测，它们被依次存储在该桶以及之下的桶中。

然而，线性探测容易产生“聚集现象”。具体来说，数组中连续被占用的位置越长，这些连续位置发生哈希冲突的可能性越大，从而进一步促使该位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。

值得注意的是，我们不能在开放寻址哈希表中直接删除元素。这是因为删除元素会在数组内产生一个空桶 None ，而当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在。

为了解决该问题，我们可以采用「懒删除 lazy deletion」机制：它不直接从哈希表中移除元素，而是利用一个常量 TOMBSTONE 来标记这个桶。在该机制下，None\text{None}None 和 TOMBSTONE 都代表空桶，都可以放置键值对。但不同的是，线性探测到 TOMBSTONE 时应该继续遍历，因为其之下可能还存在键值对。

然而，懒删除可能会加速哈希表的性能退化。这是因为每次删除操作都会产生一个删除标记，随着 TOMBSTONE 的增加，搜索时间也会增加，因为线性探测可能需要跳过多个 TOMBSTONE 才能找到目标元素。

为此，考虑在线性探测中记录遇到的首个 TOMBSTONE 的索引，并将搜索到的目标元素与该 TOMBSTONE 交换位置。这样做的好处是当每次查询或添加元素时，元素会被移动至距离理想位置（探测起始点）更近的桶，从而优化查询效率。

以下代码实现了一个包含懒删除的开放寻址（线性探测）哈希表。为了更加充分地使用哈希表的空间，我们将哈希表看作是一个“环形数组”，当越过数组尾部时，回到头部继续遍历。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <vector>

using namespace std;

class HashTable {
private:
    struct HashNode {
        int key;
        bool isDeleted;  // 用于标记懒删除
        bool isOccupied; // 用于标记该位置是否被占用

        HashNode() : key(0), isDeleted(false), isOccupied(false) {}
    };

    vector<HashNode> table;
    int size;
    int capacity;

    // 哈希函数
    int hash(int key) const {
        return key % capacity;
    }

    // 线性探测函数
    int probe(int index) const {
        return (index + 1) % capacity; // 环形数组处理越界
    }

public:
    HashTable(int cap) : size(0), capacity(cap), table(cap) {}

    // 插入元素
    void insert(int key) {
        if (size >= capacity) {
            cout << "Hash table is full" << endl;
            return;
        }

        int index = hash(key);
        while (table[index].isOccupied && !table[index].isDeleted) {
            index = probe(index); // 找到下一个空闲位置
        }

        table[index].key = key;
        table[index].isOccupied = true;
        table[index].isDeleted = false; // 标记为未删除
        size++;
    }

    // 查找元素
    bool search(int key) const {
        int index = hash(key);
        int start = index; // 保存起始位置防止循环

        while (table[index].isOccupied) {
            if (table[index].key == key && !table[index].isDeleted) {
                return true;
            }
            index = probe(index);
            if (index == start) break; // 已经环绕回到起始位置
        }

        return false;
    }

    // 懒删除元素
    void remove(int key) {
        int index = hash(key);
        int start = index;

        while (table[index].isOccupied) {
            if (table[index].key == key && !table[index].isDeleted) {
                table[index].isDeleted = true; // 懒删除
                size--;
                return;
            }
            index = probe(index);
            if (index == start) break;
        }

        cout << "Key not found" << endl;
    }

    // 打印哈希表状态
    void print() const {
        for (int i = 0; i < capacity; i++) {
            if (table[i].isOccupied && !table[i].isDeleted) {
                cout << i << ": " << table[i].key << endl;
            } else {
                cout << i << ": " << "empty" << (table[i].isDeleted ? " (deleted)" : "") << endl;
            }
        }
    }
};

int main() {
    HashTable ht(7); // 容量为7

    ht.insert(10);
    ht.insert(20);
    ht.insert(15);
    ht.insert(7);
    ht.insert(33);

    ht.print();

    cout << "Search 15: " << (ht.search(15) ? "Found" : "Not Found") << endl;

    ht.remove(15);
    ht.print();

    cout << "Search 15 after removal: " << (ht.search(15) ? "Found" : "Not Found") << endl;

    return 0;
}

平方探测

平方探测与线性探测类似，都是开放寻址的常见策略之一。当发生冲突时，平方探测不是简单地跳过一个固定的步数，而是跳过“探测次数的平方”的步数，即 1,4,9,… 步。

平方探测主要具有以下优势。

  • 平方探测通过跳过平方的距离，试图缓解线性探测的聚集效应。
  • 平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀。

然而，平方探测也并不是完美的。

  • 仍然存在聚集现象，即某些位置比其他位置更容易被占用。
  • 由于平方的增长，平方探测可能不会探测整个哈希表，这意味着即使哈希表中有空桶，平方探测也可能无法访问到它。
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <vector>

using namespace std;

class HashTable {
private:
    struct HashNode {
        int key;
        bool isDeleted;  // 用于标记懒删除
        bool isOccupied; // 用于标记该位置是否被占用

        HashNode() : key(0), isDeleted(false), isOccupied(false) {}
    };

    vector<HashNode> table;
    int size;
    int capacity;

    // 哈希函数
    int hash(int key) const {
        return key % capacity;
    }

    // 平方探测函数
    int probe(int index, int i) const {
        return (index + i * i) % capacity; // 平方探测，环形数组处理越界
    }

public:
    HashTable(int cap) : size(0), capacity(cap), table(cap) {}

    // 插入元素
    void insert(int key) {
        if (size >= capacity) {
            cout << "Hash table is full" << endl;
            return;
        }

        int index = hash(key);
        int i = 0;
        // 使用平方探测寻找空位
        while (table[index].isOccupied && !table[index].isDeleted) {
            i++;
            index = probe(hash(key), i); // 平方探测
        }

        table[index].key = key;
        table[index].isOccupied = true;
        table[index].isDeleted = false; // 标记为未删除
        size++;
    }

    // 查找元素
    bool search(int key) const {
        int index = hash(key);
        int i = 0;
        int start = index; // 保存起始位置防止循环

        while (table[index].isOccupied) {
            if (table[index].key == key && !table[index].isDeleted) {
                return true;
            }
            i++;
            index = probe(hash(key), i); // 平方探测
            if (index == start) break; // 已经环绕回到起始位置
        }

        return false;
    }

    // 懒删除元素
    void remove(int key) {
        int index = hash(key);
        int i = 0;
        int start = index;

        while (table[index].isOccupied) {
            if (table[index].key == key && !table[index].isDeleted) {
                table[index].isDeleted = true; // 懒删除
                size--;
                return;
            }
            i++;
            index = probe(hash(key), i); // 平方探测
            if (index == start) break;
        }

        cout << "Key not found" << endl;
    }

    // 打印哈希表状态
    void print() const {
        for (int i = 0; i < capacity; i++) {
            if (table[i].isOccupied && !table[i].isDeleted) {
                cout << i << ": " << table[i].key << endl;
            } else {
                cout << i << ": " << "empty" << (table[i].isDeleted ? " (deleted)" : "") << endl;
            }
        }
    }
};

int main() {
    HashTable ht(7); // 容量为7

    ht.insert(10);
    ht.insert(20);
    ht.insert(15);
    ht.insert(7);
    ht.insert(33);

    ht.print();

    cout << "Search 15: " << (ht.search(15) ? "Found" : "Not Found") << endl;

    ht.remove(15);
    ht.print();

    cout << "Search 15 after removal: " << (ht.search(15) ? "Found" : "Not Found") << endl;

    return 0;
}

多次哈希

多次哈希使用多个哈希函数f1(x)、f2(x)、f3(x)、… 进行探测。

  • 插入元素：若哈希函数 f1(x) 出现冲突，则尝试 f2(x)，以此类推，直到找到空桶后插入元素。
  • 查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回；或当遇到空桶或已尝试所有哈希函数，说明哈希表中不存在该元素，则返回 None 。

与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会增加额外的计算量。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <vector>

using namespace std;

class HashTable {
private:
    struct HashNode {
        int key;
        bool isDeleted;  // 用于标记懒删除
        bool isOccupied; // 用于标记该位置是否被占用

        HashNode() : key(0), isDeleted(false), isOccupied(false) {}
    };

    vector<HashNode> table;
    int size;
    int capacity;

    // 第一个哈希函数
    int f1(int key) const {
        return key % capacity;
    }

    // 第二个哈希函数，避免返回 0 来防止停滞
    int f2(int key) const {
        return (key / capacity) % capacity + 1;
    }

    // 多次哈希的探测函数，使用 f1 和 f2
    int probe(int key, int attempt) const {
        return (f1(key) + attempt * f2(key)) % capacity;
    }

public:
    HashTable(int cap) : size(0), capacity(cap), table(cap) {}

    // 插入元素
    void insert(int key) {
        if (size >= capacity) {
            cout << "Hash table is full" << endl;
            return;
        }

        int attempt = 0;
        int index = f1(key);
        // 使用多次哈希寻找空位
        while (table[index].isOccupied && !table[index].isDeleted) {
            attempt++;
            index = probe(key, attempt); // 使用 f1 和 f2 进行探测
            if (attempt >= capacity) {  // 防止无限循环
                cout << "Hash table insertion failed: no empty bucket" << endl;
                return;
            }
        }

        table[index].key = key;
        table[index].isOccupied = true;
        table[index].isDeleted = false; // 标记为未删除
        size++;
    }

    // 查找元素
    bool search(int key) const {
        int attempt = 0;
        int index = f1(key);
        // 多次哈希查找
        while (table[index].isOccupied) {
            if (table[index].key == key && !table[index].isDeleted) {
                return true;
            }
            attempt++;
            index = probe(key, attempt);
            if (attempt >= capacity) {  // 防止无限循环
                break;
            }
        }

        return false;
    }

    // 懒删除元素
    void remove(int key) {
        int attempt = 0;
        int index = f1(key);
        // 多次哈希删除
        while (table[index].isOccupied) {
            if (table[index].key == key && !table[index].isDeleted) {
                table[index].isDeleted = true; // 懒删除
                size--;
                return;
            }
            attempt++;
            index = probe(key, attempt);
            if (attempt >= capacity) {  // 防止无限循环
                break;
            }
        }

        cout << "Key not found" << endl;
    }

    // 打印哈希表状态
    void print() const {
        for (int i = 0; i < capacity; i++) {
            if (table[i].isOccupied && !table[i].isDeleted) {
                cout << i << ": " << table[i].key << endl;
            } else {
                cout << i << ": " << "empty" << (table[i].isDeleted ? " (deleted)" : "") << endl;
            }
        }
    }
};

int main() {
    HashTable ht(7); // 容量为7

    ht.insert(10);
    ht.insert(20);
    ht.insert(15);
    ht.insert(7);
    ht.insert(33);

    ht.print();

    cout << "Search 15: " << (ht.search(15) ? "Found" : "Not Found") << endl;

    ht.remove(15);
    ht.print();

    cout << "Search 15 after removal: " << (ht.search(15) ? "Found" : "Not Found") << endl;

    return 0;
}

重点：

  • 输入 key ，哈希表能够在 O(1) 时间内查询到 value ，效率非常高。
  • 常见的哈希表操作包括查询、添加键值对、删除键值对和遍历哈希表等。
  • 哈希函数将 key 映射为数组索引，从而访问对应桶并获取 value 。
  • 两个不同的 key 可能在经过哈希函数后得到相同的数组索引，导致查询结果出错，这种现象被称为哈希冲突。
  • 哈希表容量越大，哈希冲突的概率就越低。因此可以通过扩容哈希表来缓解哈希冲突。与数组扩容类似，哈希表扩容操作的开销很大。
  • 负载因子定义为哈希表中元素数量除以桶数量，反映了哈希冲突的严重程度，常用作触发哈希表扩容的条件。
  • 链式地址通过将单个元素转化为链表，将所有冲突元素存储在同一个链表中。然而，链表过长会降低查询效率，可以进一步将链表转换为红黑树来提高效率。
  • 开放寻址通过多次探测来处理哈希冲突。线性探测使用固定步长，缺点是不能删除元素，且容易产生聚集。多次哈希使用多个哈希函数进行探测，相较线性探测更不易产生聚集，但多个哈希函数增加了计算量。
  • 不同编程语言采取了不同的哈希表实现。例如，Java 的 HashMap 使用链式地址，而 Python 的 Dict 采用开放寻址。
  • 在哈希表中，我们希望哈希算法具有确定性、高效率和均匀分布的特点。在密码学中，哈希算法还应该具备抗碰撞性和雪崩效应。
  • 哈希算法通常采用大质数作为模数，以最大化地保证哈希值的均匀分布，减少哈希冲突。
  • 常见的哈希算法包括 MD5、SHA-1、SHA-2 和 SHA3 等。MD5 常用于校验文件完整性，SHA-2 常用于安全应用与协议。
  • 编程语言通常会为数据类型提供内置哈希算法，用于计算哈希表中的桶索引。通常情况下，只有不可变对象是可哈希的。