_{C++基础教程}
——
作业及参考答案全部汇总文档
^{_节11算法基础阶段作业}

最新版本V2.0
王道C++团队
COPYRIGHT ⓒ 2021-2024. 王道版权所有

基础题篇

_Gn!

下面都是一些基础的语法、概念编程练习题。

手动实现三个简单排序算法

_Gn!

请自己手动实现三个基础的排序算法：

xxxxxxxxxx
6
1
// 选择排序
2
void selection_sort(int arr[], int len);
3
// 冒泡排序
4
void bubble_sort(int arr[], int len);
5
// 插入排序
6
void insertion_sort(int arr[], int len);

然后给定一个int数组，实现将它从小到大进行排序。

参考代码：

选择排序代码实现：

xxxxxxxxxx
49
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3

4
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
5
#define SWAP(arr, i, j ) {      \
6
int tmp = arr[i];           \
7
arr[i] = arr[j];            \
8
arr[j] = tmp;               \
9
}
10

11
void print_arr(int arr[], int len) {
12
for (int i = 0; i < len; i++) {
13
  printf("%d ", arr[i]);
14
}
15
printf("\n");
16
}
17

18
// 选择排序
19
void selection_sort(int arr[], int len) {
20
/*
21
    * i表示未排序序列的开头元素
22
    * 最后一轮选择排序时, 未排序序列的开头元素是数组倒数第二个元素
23
    * i的每个取值都表示一轮选择排序
24
    * 也就是选择排序一共执行9趟
25
    */ 
26
    for (int i = 0; i < len - 1; i++) {
27
        // 不妨直接假设未排序序列的开头i位置元素就是最小值
28
        int min_index = i;
29
        // 遍历未排序数组序列,找出真正的最小值下标,此时应遍历最后一个元素
30
        for (int j = i + 1; j < len; j++) {
31
            if (arr[j] < arr[min_index]) {
32
                min_index = j;  // 记录较小值的下标
33
            }
34
        }   // for循环结束时，未排序序列的最小值下标就是min_index
35

36
        // 交换min_index和下标i的元素
37
        SWAP(arr, min_index, i);
38
        // 选择排序一趟打印一次数组
39
        print_arr(arr, len);
40
    }
41
}
42

43
int main(void) {
44
  // 测试选择排序
45
    int arr[] = { 1,10,2,5,3,4,5,6,3,2 };
46
    int len = ARR_LEN(arr);
47
    selection_sort(arr, len);
48
    return 0;
49
}

冒泡排序代码实现：

xxxxxxxxxx
53
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#include <stdbool.h>
4

5
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
6

7
#define SWAP(arr, i, j ) {      \
8
    int tmp = arr[i];           \
9
    arr[i] = arr[j];            \
10
    arr[j] = tmp;               \
11
}
12

13
void print_arr(int arr[], int len) {
14
    for (int i = 0; i < len; i++) {
15
        printf("%d ", arr[i]);
16
    }
17
    printf("\n");
18
}
19

20
void bubble_sort(int arr[], int len) {
21
    // 外层for的i表示第几轮冒泡排序,最多需要进行len-1轮
22
    for (int i = 1; i < len; i++) {
23
        // 标记在这一次冒泡排序中有没有交换,false表示没有交换
24
        bool swapped = false;
25
        /*
26
        * j表示两两比较元素中的第一个元素的下标
27
        * 第一轮j的最大取值是数组倒数第二个元素,并且逐步减小
28
        * 所以j的条件是小于 (len - i)
29
        */ 
30
        for (int j = 0; j < len - i; j++) {
31
            if (arr[j] > arr[j + 1]) {
32
                SWAP(arr, j, j + 1);
33
                // 发生了交换改变标记
34
                swapped = true;
35
            }
36
        }
37
        // 在一轮冒泡排序中没有任何交换,则排序已经完成,终止循环
38
        if (!swapped) {
39
            break;
40
        }
41
    // 打印一轮冒泡排序后数组的元素排列
42
        print_arr(arr, len);
43
    }
44
}
45

46
int main(void) {
47
  // 测试冒泡排序
48
    int arr[] = { 16, 1, 45, 23, 99, 2, 18, 67, 42, 10 };
49
    int len = ARR_LEN(arr);
50
    bubble_sort(arr, len);
51

52
    return 0;
53
}

插入排序代码实现：

xxxxxxxxxx
35
1
// 插入排序 优化: 用向后移动腾出插入位置,然后插入实现插入排序
2
void insertion_sort(int arr[], int len) {
3
    // 现在第一个元素就是第一张手牌,从第二个元素开始就是每一次要摸的牌
4
    // 外层for循环代表每一轮摸到的新手牌, 也就是每一轮插入排序
5
    for (int i = 1; i < len; i++) {
6
        // 先记录一下新手牌的值, 便于后续的插入操作
7
        int tmp = arr[i];
8
        int j = i - 1;
9
        for (;j >= 0; j--) {
10
            if (arr[j] > tmp) { // 注意:不能加=,加了就不是稳定排序算法了
11
                arr[j + 1] = arr[j];    // 将旧手牌中大于新手牌的所有牌都向后移
12
            }
13
            else
14
            {
15
                break;  // 只要发现一张旧手牌更小或相等, 就说明已经找到新手牌的插入位置了
16
            }
17
        }
18
        /*
19
            现在还有一件事情没做:新手牌要插入,需要确定插入位置
20
            分析: for循环什么时候结束?
21
            两种情况:
22
            1.j=-1时,循环结束,说明新手牌是最小的,所以插入到0这个位置,也就是j+1
23
            2.arr[j] <= tmp 也就是旧手牌更小或相等,此时新手牌放在j+1的位置
24
        */
25
        arr[j + 1] = tmp;
26
        print_arr(arr, len);    // 每一轮摸牌后查看排序后的数组
27
    }
28
}
29

30
int main(void) {
31
    int arr[] = { 1, 21, 45, 231, 99, 2, 18, 7, 4, 9 };
32
    int len = ARR_SIZE(arr);
33
    insertion_sort(arr, len);
34
    return 0;
35
}

以上。

手动实现希尔排序算法

_Gn!

请手动实现希尔排序算法:

xxxxxxxxxx
1
1
void shell_sort(int arr[], int n);

参考代码如下：

参考代码：

希尔排序的实现代码如下：

1
#include <stdio.h>
2

3
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
4

5
void print_arr(int arr[], int len) {
6
    for (int i = 0; i < len; i++) {
7
        printf("%d ", arr[i]);
8
    }
9
    printf("\n");
10
}
11

12
// 希尔排序: 缩小增量排序, 其实就是多人摸牌, 逐渐减少摸牌人数
13
// 希尔排序中, 增量序列的设计非常重要,这里采取简单的gap序列: 长度减半..一直减半,直到为1
14
// gap为1时就是一个在数组元素基本有序情况下的,插入排序
15
void shell_sort(int arr[], int len) {
16
    // 第一个元素是第一个人的初始手牌,一直到第gap个元素都是初始手牌
17
    int gap = len >> 1;
18
    while (gap > 0) {
19
        // 外层for的i仍然代表新摸到的手牌的下标,i从gap开始,直到摸完整个数组元素
20
        for (int i = gap; i < len; i++) {
21
            // 先记录一下新手牌的值, 便于后续的插入操作
22
            int tmp = arr[i];
23
            int j = i - gap;    // 代表每一个人旧手牌的最后一张牌
24
            for (; j >= 0; j -= gap) {
25
                // 内层for代表 每个人每摸到一张新手牌,都会和原本的旧手牌比较,但由于gap存在,所以需要减去gap
26
                if (arr[j] > tmp) { // 注意:不能加=,加了就不稳定了
27
                    arr[j + gap] = arr[j];  // 将旧手牌中大于新手牌的所有牌都向后移
28
                }
29
                else
30
                {
31
                    break;  // 只要发现一张旧手牌更小或相等, 就说明已经找到新手牌的插入位置了
32
                }
33
            }
34
            arr[j + gap] = tmp;
35
            print_arr(arr, len);    // 每一轮摸牌后查看排序后的数组
36
        }
37
        gap >>= 1; // 每一轮希尔排序,增量都减半
38
    }
39
}
40

41
int main(void) {
42
    int arr[] = { 16, 1, 45, 23, 99, 2, 18, 67, 42, 10 };
43
    int arr_len = ARR_LEN(arr);
44
    shell_sort(arr, arr_len);
45
    return 0;
46
}

以上。

手动实现归并排序算法

_Gn!

请手动实现归并排序算法：

xxxxxxxxxx
1
1
void merge_sort(int arr[], int len)

如果学有余力，不妨尝试一下多种临时数组的方式：

1.局部变量数组

2.全局变量数组

3.堆数组

提交答案只需要使用其中一种即可。

参考代码如下：

参考代码：

归并排序实现代码如下：

xxxxxxxxxx
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#include <stdlib.h>
4
#define ARR_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
5

6
// 打印数组的函数
7
void print_arr(int arr[], int left, int right) {
8
    for (int i = left; i <= right; i++) {
9
        printf("%d ", arr[i]);
10
    }
11
    printf("\n");
12
}
13

14
/*
15
   * 合并的思路:
16
* 1.把左右子数组中元素按照顺序合并到临时数组中,过程类似"穿针引线"
17
   * 2.将排好序的临时数组元素按照下标赋值给原数组
18
   * 注：临时数组和原数组共有一套下标
19
   * 传入函数逻辑上的左右子数组是有序的,相当于合并两个有序的左右子数组
20
   */
21
static void merge(int arr[], int left, int mid, int right, int* tmp) {
22
    /*
23
    * tmp_idx: 用于存放合并结果的临时数组的开始下标
24
    * left_idx: 左子数组的开始下标
25
    * right_idx: 右子数组的开始下标
26
    */
27
    int tmp_idx = left, left_idx = left, right_idx = mid + 1;
28

29
    // 只要左右子数组同时还有元素
30
    while (left_idx <= mid && right_idx <= right) {
31
        // 捉对比较左右子数组的元素,按照从小到大放入临时数组
32
        // <=判断不会改变相同元素的相对位置,是稳定算法。反之则不是稳定算法
33
        if (arr[left_idx] <= arr[right_idx]) {
34
            tmp[tmp_idx++] = arr[left_idx++];
35
        }
36
        else {
37
            tmp[tmp_idx++] = arr[right_idx++];
38
        }
39
    }   
40
    // while结束时，左右子数组必然有一个没有元素了,此时另一个数组必然还有元素
41
    // 也就是说只会有一个数组是空的
42
    // 但我们无法确定是哪个数组没有元素了
43
    // 所以我们都判断一下将左右子数组还剩余的元素取出来
44
    while (left_idx <= mid) {
45
        // 说明左数组还有元素
46
        tmp[tmp_idx++] = arr[left_idx++];
47
    }
48
    while (right_idx <= right) {
49
        // 说明右数组还有元素
50
        tmp[tmp_idx++] = arr[right_idx++];
51
    }
52

53
    // 将临时数组中已排序好的元素复制到原始数组中
54
    for (int i = left; i <= right; i++) {
55
        arr[i] = tmp[i];
56
    }
57
    // 打印此一轮归并排序的元素
58
    print_arr(arr, left, right);
59
}
60

61
/*
62
* 辅助函数,实现对[left, right]范围内的数组递归分解合并
63
* left表示递归分解的区间起点,right表示递归分解区间的终点,是一个闭区间
64
   * 递归分解的思路是:
65
   * 对[left, right]区间元素的排序,可以分解成:
66
* [left, mid]区间,和[mid + 1, right]区间的排序合并
67
   * 递归的出口是:
68
   * 如果区间仅有一个元素或没有元素,递归结束
69
   */
70
static void divide_merge(int arr[], int left, int right, int* tmp) {
71
    // 递归的出口
72
    if (left >= right) {
73
        return;
74
    }
75

76
    // 递归体
77
    // 计算中间索引
78
    int mid = left + (right - left >> 1);
79
    // 分解,规定左数组是[left, mid]
80
    // 右数组是[mid + 1, right]
81
    divide_merge(arr, left, mid, tmp);
82
    divide_merge(arr, mid + 1, right, tmp);
83

84
    /*
85
    * 归并，归并排序的核心操作
86
    * 需要一个临时数组完成此操作
87
    * 这个临时数组至少要和原先的数组一般大
88
    * 有两种方案：
89
    * 1.用全局变量数组或局部变量,该方式简洁易实现,无需考虑内存回收
90
    *   但缺点是
91
    *   a.必须编译时期确定数组长度,无法运行时期动态分配
92
    *   b.栈区和数据段都无法创建长数组,在大数据集下容易产生溢出错误
93
    * 为了解决这两个缺点,我们可以在堆上动态分配数组
94
    *   但同样也有缺点:
95
    *   a.内存管理风险
96
    *   b.动态分配数组会带来额外性能开销
97
    */
98
    merge(arr, left, mid, right, tmp);
99

100
}
101

102
void merge_sort(int arr[], int len) {
103
    // 临时数组
104
    int* tmp = calloc(len, sizeof(int));
105
    if (tmp == NULL){
106
        printf("calloc failed in merge_sort.\n");
107
        return;
108
    }
109

110
    // 将整个数组进行递归分解合并,即完成归并排序
111
    divide_merge(arr, 0, len - 1, tmp);
112

113
    // 不要忘记free释放资源
114
    free(tmp);
115
}
116

117
// 测试归并排序
118
int main() {
119
    int arr[] = { 8, 3, 2, 6, 9, 7, 1, 0, 4, 5 };
120
    int arr_size = ARR_SIZE(arr);
121

122
    merge_sort(arr, arr_size);
123
    return 0;
124
}

以上。

手动实现快速排序算法

_Gn!

请手动实现快速排序算法，包括单向分区以及双向分区：

xxxxxxxxxx
4
1
// 单向分区快速排序算法
2
void quick_sort_one_way(int arr[], int len);
3
// 双向分区快速排序算法
4
void quick_sort_two_way(int arr[], int len);

参考代码如下：

参考代码：

单向分区快排算法的实现代码如下：

x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#include <time.h>
4
#include <stdlib.h>
5

6
#define ARR_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
7
#define SWAP(arr, i, j) {   \
8
    int tmp = arr[i];       \
9
    arr[i] = arr[j];        \
10
    arr[j] = tmp;           \
11
}
12

13
// 打印数组的函数
14
void print_arr(int arr[], int left, int right) {
15
    for (int i = left; i <= right; i++) {
16
        printf("%d ", arr[i]);
17
    }
18
    printf("\n");
19
}
20

21
// 分区核心操作实现,返回一轮快排选择的pivot的下标
22
int partition(int arr[], int left, int right) {
23
    // 1.随机选择一个基准值,然后把它先放到数组末尾
24
    int pivot_idx = left + rand() % (right - left + 1); // 得到一个[left, right]范围内的随机索引
25
    int pivot = arr[pivot_idx];
26
    SWAP(arr, pivot_idx, right);
27

28
    // 2.设置一个partition_idx索引,指示小于pivot的元素应该插入的位置
29
    // 同时该索引最终表示分区的界限索引,所以命名为partition_idx
30
    int partition_idx = left;
31

32
    // 3.遍历整个数组,当元素小于pivot时,将它和partition_idx位置元素交换,partition_idx加1
33
    // 希望遍历结束时，i指向数组末尾的pivot，所以i < right
34
    for (int i = left; i < right; i++) {
35
        if (arr[i] < pivot) {
36
            SWAP(arr, i, partition_idx);
37
            partition_idx++;
38
        }
39
    }
40
    // 4.遍历结束后,将pivot元素(最后一个元素)交换到partition_idx位置
41
    SWAP(arr, right, partition_idx);
42

43
    printf("此一轮分区操作,选择的pivot是: %d\n分区结束后的数组是: ", pivot);
44
    print_arr(arr, left, right);
45

46
    // 5.返回基准值的位置索引
47
    return partition_idx;
48
}
49

50
/*
51
* 辅助函数
52
* 用于对对[left, right]区间中的元素进行递归分区操作
53
*/
54
void partition_recursion(int arr[], int left, int right) {
55
    // 递归出口
56
    if (left >= right) {
57
        return;
58
    }
59
    // 递归体
60
    int idx = partition(arr, left, right);  // 分区操作,找到pivot元素的下标位置
61
    partition_recursion(arr, left, idx - 1);
62
    partition_recursion(arr, idx + 1, right);
63
}
64

65
void quick_sort_one_way(int arr[], int len) {
66
    // 初始化随机数生成器,time(NULL)获取当前时间戳
67
    // 用于生成随机索引
68
    srand(time(NULL));
69
    // 调用辅助函数进行递归分解
70
    partition_recursion(arr, 0, len - 1);
71
}
72

73
int main(void) {
74
    // 测试单向分区快速排序
75
    int arr[] = { 8,3,2,6,9,5 };
76
    int len = ARR_SIZE(arr);
77
    quick_sort_one_way(arr, len);
78

79
    return 0;
80
}

双向分区快排算法的实现代码如下：

x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#define ARR_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
4

5
// 打印数组的函数
6
void print_arr(int arr[], int left, int right) {
7
    for (int i = left; i <= right; i++) {
8
        printf("%d ", arr[i]);
9
    }
10
    printf("\n");
11
}
12

13
// 双向分区操作函数用于快速排序
14
int partition(int arr[], int left, int right) {
15
    // 选择左端元素作为基准值
16
    int pivot = arr[left];
17

18
    // 初始化指针：low 指向数组起始，high 指向数组末尾
19
    int low = left;
20
    int high = right;
21

22
    // 当 low 和 high 未重合时，执行分区操作
23
    while (low < high) {
24
        // 从右向左找到第一个小于基准值的元素
25
        while (low < high && arr[high] >= pivot) {
26
            high--;
27
        }
28
        // 找到后，将其放到 low 的位置
29
        arr[low] = arr[high]; // 这里不需要判断 low < high，因为外层循环已保证
30

31
        // 从左向右找到第一个大于等于基准值的元素
32
        while (low < high && arr[low] < pivot) {
33
            low++;
34
        }
35
        // 找到后，将其放到 high 的位置
36
        arr[high] = arr[low]; // 同样，这里不需要再次判断 low < high
37
    }
38

39
    // 当 low 和 high 重合，确定了基准元素的最终位置，将基准值放回数组中
40
    arr[low] = pivot;
41

42
    // 打印本轮分区后的数组状态，仅为了演示和调试
43
    printf("此轮分区操作，选择的基准是: %d\n分区结束后的数组是: ", pivot);
44
    print_arr(arr, left, right); // 假设 print_arr 正确实现
45

46
    // 返回基准值的最终位置
47
    return low;
48
}
49

50
// 对[left, right]区间进行递归分区操作
51
void partition_recursion(int arr[], int left, int right) {
52
    // 递归出口
53
    if (left >= right) {
54
        return;
55
    }
56
    // 递归体
57
    int idx = partition(arr, left, right);  // 分区操作,找到pivot下标位置
58
    partition_recursion(arr, left, idx - 1);
59
    partition_recursion(arr, idx + 1, right);
60
}
61

62
void quick_sort_two_way(int arr[], int len) {
63
    partition_recursion(arr, 0, len - 1);
64
}
65

66
int main(void) {
67
    int arr[] = { 8,3,2,6,9,5 };
68
    int len = ARR_SIZE(arr);
69
    // 测试双向分区-快速排序
70
    quick_sort_two_way(arr, len);
71
    return 0;
72
}

以上。

手动实现堆排序算法

_Gn!

请手动实现堆排序算法:

xxxxxxxxxx
1
1
void heap_sort(int arr[], int len);

参考代码如下：

参考代码：

堆排序算法实现代码如下：

xxxxxxxxxx
106
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3

4
#define ARR_SIZE(a) (sizeof(a)/sizeof(a[0]))
5
#define SWAP(arr, i, j) {   \
6
    int tmp = arr[i];       \
7
    arr[i] = arr[j];        \
8
    arr[j] = tmp;           \
9
}
10

11
void print_arr(int arr[], int n) {
12
    for (int i = 0; i < n; i++) {
13
        printf("%d ", arr[i]);
14
    }
15
    printf("\n");
16
}
17

18
// idx是可能违反大顶堆规则的父结点的下标
19
// 在一开始idx结点的左右子树必然都是大顶堆
20
static void heapify(int arr[], int heap_len, int idx) {
21
    while (1) {
22
        // 找出idx结点的左右子树,比较,确定最大结点,如果最大结点不是idx那就进行交换操作
23
        int max_idx = idx;  // 假设父节点就是最大结点
24
        int lchild_idx = (idx << 1) + 1;    // 左子树的索引
25
        int rchild_idx = (idx << 1) + 2;    // 右子树的索引
26

27
        // 如果左子树存在并且大于最大值
28
        if (lchild_idx < heap_len && arr[lchild_idx] > arr[max_idx]) {
29
            max_idx = lchild_idx;
30
        }
31

32
        // 如果右子树存在并且大于最大值
33
        if (rchild_idx < heap_len && arr[rchild_idx] > arr[max_idx]) {
34
            max_idx = rchild_idx;
35
        }
36

37
        // 代码运行到这里,就找到了父节点和左右子树结点的最大值
38
        if (max_idx != idx) {
39
            // 父节点不是最大值，交换元素
40
            SWAP(arr, idx, max_idx);
41
            // max_idx此时发生了元素交换,此结点可能会违反大顶堆的规则
42
            // 更新idx，继续循环这一过程，直到不再出现元素交换。堆化才全部完成
43
            idx = max_idx;
44
        }
45
        else {
46
            // 父节点就是最大结点，此时堆化过程全部结束
47
            break;
48
        }
49
    }
50
}
51

52
void build_heap(int arr[], int len) {
53
    /*
54
    * 从数组最后一个非叶子结点开始，对每个非叶子结点做堆化处理
55
    * (最后一个非叶子结点向前遍历到数组首元素，过程中的结点都是非叶子结点)
56
    * 也就是自下而上处理所有的非叶子结点, 使得所有非叶子结点都符合大顶堆的规则
57
    * 这样整个数组就会构建成为一个大顶堆
58
    *
59
    * 那么最后一个非叶子结点的元素下标是多少呢?
60
    * 假设最后一个非叶子结点,它的索引是i
61
    * 那么它至少有一颗左子树,左子树的索引是2i + 1
62
    * 数组索引的取值范围是[0, len - 1]
63
    * 2i + 1 <= len - 1
64
    * i <= (len - 2) / 2
65
    * 所以数组中最后一个非叶子结点的下标就是(len - 2) / 2
66
    */
67
    int last_idx = len - 2 >> 1;
68
    for (int i = last_idx; i >= 0; i--) {
69
        heapify(arr, len, i);
70
    }
71
    print_arr(arr, len);
72
}
73

74
void heap_sort(int arr[], int len) {
75
    // 1.将原数组构建成一个大顶堆
76
    build_heap(arr, len);
77

78
    // 2.反复移除堆顶元素, 并重建大顶堆
79
    int heap_len = len; // 堆的逻辑大小,一开始将整个数组当成一个大顶堆
80
    // 只要堆的逻辑大小大于1, 就需要重复堆排序的过程
81
    while (heap_len > 1) {
82
        // 交换堆逻辑上的首尾元素
83
        SWAP(arr, 0, heap_len - 1);
84
        heap_len--;     // 堆逻辑大小减1
85
        // 重构大顶堆
86
        /*
87
        * 此函数的三个参数：
88
        * 1.arr是作为大顶堆的数组
89
        * 2.heap_len决定数组中哪部分元素作为大顶堆处理
90
        * 3.0是堆逻辑上的根结点,由于每次堆顶元素都会交换改变
91
        *   所以在堆排序的过程中，只有此元素的存在可能会违反大顶堆的规则
92
        *   也就是说该索引是堆化过程中可能需要处理的结点的索引
93
        */
94
        heapify(arr, heap_len, 0);
95
        print_arr(arr, len);
96
    }   // while结束时,heap_len = 1,堆排序结束
97
}
98

99
int main(void) {
100
    int arr[] = { 4, 10, 3, 5, 1 };
101
    int len = ARR_SIZE(arr);
102
    print_arr(arr, len);
103

104
    heap_sort(arr, len);
105
    return 0;
106
}

以上。

手动实现简单二分查找算法

_Gn!

请手动实现简单二分查找算法，要求使用递归和循环迭代两种方式实现：

xxxxxxxxxx
1
1
int binary_search(int arr[], int len, int target);

所谓简单二分查找，指的是利用二分查找算法，查找目标元素，只要找到目标元素即返回目标元素的下标。

参考代码如下：

参考代码：

递归实现简单二分查找：

x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3

4
#define ARR_LEN(arr) ( sizeof(arr) / sizeof(arr[0]) )
5

6
// 递归实现简单二分查找
7
int bs_recursion(int arr[], int left, int right, int target) {
8
    // 递归的出口
9
    // 如果区间已不存在, 则二分查找结束, 没找到目标元素
10
    if (left > right) {
11
        return -1;
12
    }
13

14
    // 递归体
15
    // 如果区间存在，则递归分解进行二分查找
16
    int mid = left + (right - left >> 1);   // 计算中间索引
17
    int diff = target - arr[mid];
18
    if (diff > 0) {
19
        // 递归查找右区间
20
        return bs_recursion(arr, mid + 1, right, target);
21
    }
22
    if (diff < 0) {
23
        // 递归查找左区间
24
        return bs_recursion(arr, left, mid - 1, target);
25
    }
26
    // diff等于0，中间元素就是目标元素
27
    return mid;
28
}
29

30
int binary_search(int arr[], int len, int target) {
31
    // 利用辅助函数完成递归二分查找数组的过程
32
    // 此函数调用表示对arr数组[0, len-1]区间的元素进行二分查找
33
    return bs_recursion(arr, 0, len - 1, target);
34
}
35

36
int main(void) {
37
    int arr[] = { 0,3,5,7,7,9,10, 20,100 };
38
    int len = ARR_LEN(arr);
39
    int target = 7;
40

41
    int idx = binary_search(arr, len, target);
42

43
    printf("查找目标元素%d, 它在数组中的索引是%d\n", target, idx);
44

45
    return 0;
46
}

循环迭代实现二分查找：

x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3

4
// 定义一个宏,用于计算数组的长度
5
#define ARR_LEN(arr) ((int)sizeof(arr) / sizeof(arr[0]))
6

7

8
// 循环实现简单二分查找
9
int binary_search(int arr[], int len, int target) {
10
    // 定义二分查找过程中数组的左右界限
11
    int left = 0, right = len - 1;
12

13
    while (left <= right) { // 只要区间还有一个元素,就进行二分查找
14
        int mid = left + (right - left >> 1);   // 计算中间索引
15
        int diff = target - arr[mid];
16

17
        if (diff > 0) {
18
            // 查找右半区间
19
            left = mid + 1;
20
        }
21
        else if (diff < 0) {
22
            // 查找左半区间
23
            right = mid - 1;
24
        }
25
        else {
26
            // 已找到目标元素
27
            return mid;
28
        }
29
    }
30

31
    // while循环即left > right，说明数组中没有目标元素
32
    return -1;
33
}
34

35
int main(void) {
36
    int arr[] = { 0,3,5,7,7,9,10, 20,100 };
37
    int len = ARR_LEN(arr);
38
    int target = 100;
39

40
    int idx = binary_search(arr, len, target);
41
    printf("查找目标元素%d, 它在数组中的索引是%d\n", target, idx);
42

43
    return 0;
44
}

以上。

手动实现二分查找的变种

_Gn!

基于循环迭代的实现方式，利用二分查找的算法思想，实现：

1. 查找数组中最后一个与目标值相等的元素

2. 查找数组中最后一个小于等于目标值的元素

参考代码如下：

参考代码实现如下：

查找数组中最后一个与目标值相等的元素，实现参考代码如下：

x
1
// 查找最后一个等于目标值的元素
2
int binary_search_last(int arr[], int len, int target) {
3
    int left = 0, right = len - 1;
4

5
    while (left <= right) {
6
        int mid = left + (right - left >> 1);
7

8
        if (arr[mid] < target) {
9
            left = mid + 1;
10
        }
11
        else if (arr[mid] > target) {
12
            right = mid - 1;
13
        }
14
        else {
15
            if (mid == right || arr[mid + 1] > target) {
16
                // 如果mid是数组的最后一个元素，或者mid的下一个元素大于目标值
17
                // 那么mid就是target最后一次在数组中出现的下标
18
                return mid;
19
            }
20
            // 只要不能断定mid是最后一次出现的索引，就继续向右半区间进行二分查找
21
            left = mid + 1;
22
        }
23
    }
24
    // 没找到目标元素
25
    return -1;
26
}

查找最后一个小于等于目标值的元素，实现参考代码如下：

x
1
// 查找最后一个小于等于目标值的元素
2
int binary_search(int arr[], int len, int target) {
3
    int left = 0, right = len - 1;
4

5
    while (left <= right) {
6
        int mid = left + (right - left >> 1);
7

8
        if (arr[mid] > target) {
9
            // 中间值大于目标值, 于是去左区间中查找
10
            right = mid - 1;
11
        }else{
12
            // 中间值小于等于目标值的，于是mid就是一个备选返回值
13
            // 但是要先判断mid是不是最后一个小于等于目标值的元素
14
            if (mid == right || arr[mid + 1] > target) {
15
                // mid是数组最后一个元素或者mid就是最后一个小于等于目标值的元素
16
                return mid;
17
            }
18
            // mid不是最后一个, 于是去右区间中查找
19
            left = mid + 1;
20
        }
21
    }
22

23
    // 没找到目标元素
24
    return -1;
25
}

以上。

利用二分查找思想改进插入排序

_Gn!

在数据较多的情况下，使用插入排序会导致"旧手牌"序列比较长，此时若仍然相邻元素两两比较后移是比较耗时的，可以考虑使用"二分查找算法思想"进行改进。

请你实现这个改进。

参考代码如下：

参考代码实现如下：

利用二分查找，找到最后一个小于等于"新手牌"值的元素，这样就可以直接将它后面的所有元素后移一位，然后再它后面直接插入"新手牌"。

参考实现代码如下：

x
1
#include <stdio.h>
2

3
#define ARR_LEN(arr) ((int)sizeof(arr) / sizeof(arr[0]))
4

5
// 使用二分查找在有序数组[left, right]区间内中找到最后一个小于等于目标值的元素的位置
6
int binary_search(int arr[], int left, int right, int key) {
7
    while (left <= right) {
8
        // 计算中间位置
9
        int mid = left + (right - left >> 1);
10
        // 比较中间位置的元素和目标值
11
        int cmp = arr[mid] - key;
12
        // 如果中间值和目标值相等或中间值更小，那mid就是一个可能的结果
13
        if (cmp <= 0) {
14
            // 判断mid是不是最后一个
15
            if (mid == right || arr[mid + 1] > key) {   
16
                // 如果它已经是区间的最后一个元素
17
                // 或者它不是最后一个元素但mid后面的一个元素已经比目标值大了
18
                // 都可以断定mid是最后一个小于等于目标值的元素
19
                return mid;
20
            }
21
            // 如果不是最后一个，那就继续去右边区间查找
22
            left = mid + 1;
23
        } else {
24
            // 如果中间值比目标值大，那就去左边区间二分查找
25
            right = mid - 1;
26
        }
27
    } // left > right 
28

29
    return -1;
30
}
31

32
void binary_insertion_sort(int arr[], int n) {
33
    for(int i = 1; i < n; i++) {
34
        int value = arr[i];
35
        // 使用二分查找找到应插入的位置
36
        // idx(不包括)后面的所有元素都有后移一位，idx + 1是value要插入的位置
37
        int idx = binary_search(arr, 0, i-1, value);    
38
        int j = i - 1;  // j在这里赋值为有序数组的最后一个元素
39
        while (j > idx) {       // 有序数组中的元素只要下标大于idx就后移 也就是不包括idx，但idx后面的所有元素都要后移
40
            arr[j+1] = arr[j];
41
            j--;
42
        } // j == idx;
43
        arr[j + 1] = value;
44
    }
45
}
46

47
int main(void) {
48
    int arr[] = {9, 5, 2, 7, 1, 3, 4, 0, 8, 6};
49
    int len = ARR_LEN(arr);
50
    binary_insertion_sort(arr, len);
51

52
    for(int i = 0; i < len; i++) {
53
        printf("%d ", arr[i]);
54
    }
55
    printf("\n");
56

57
    return 0;
58
}

以上。

The End