1 常见算法

1.1 排序算法

1.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
/**
 * @brief 冒泡排序算法
 * @param arr 待排序数组
 * @param length 待排序数组长度
 */
void maopao(int arr[], int length)
{
    int temp;
    // i：表示比较轮数
    for(int i=0; i<length; i++)
    {
        // j：两两数字进行比较，大数向后移
        for(int j=0; j<length-i-1; j++)
        {
            if(arr[j] > arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

1.1.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
/**
 * @brief 分区函数 - 快速排序的核心
 */
int fenqu(int arr[], int left, int right)
{
    int temp = 0;
    // 选取最后一个元素作为基准
    int pivot = arr[right]; 
    // 定义快慢指针
    int slow = left;
    int fast = left;
    while(fast < right)
    {
        if(arr[fast] < pivot)
        {
            temp = arr[slow];
            arr[slow] = arr[fast];
            arr[fast] = temp;
            
            slow++;
        }
        fast++;
    }
    // 交换最后一个基准点
    temp = arr[slow];
    arr[slow] = arr[right];
    arr[right] = temp;
    
    return slow;
}
/**
 * @brief 快速排序算法
 * @note 快速排序的【标准模板】
 * @param arr 待排序数组
 * @param length 待排序数组长度
 */
void kuaisu(int arr[], int left, int right)
{
    if(left < right)
    {
        // 对arr[left]到arr[right]之间的元素进行分区
        int point = fenqu(arr, left, right);
        // 对分区点左侧的元素进行快速排序
        kuaisu(arr, left, point-1);
        // 对分区点右侧的元素进行快速排序
        kuaisu(arr, point+1, right);
    }
}

1.1.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
/**
 * @brief 构建大根堆
 * @param arr 原数组
 * @param length 源数组长度
 * @param index 当前调整的元素下标索引
 */
void dagendui(int arr[], int length, int index)
{
	int largest = index;       // 初始化最大值为当前待调整节点
    int left = 2 * index + 1;  // 当前待调整节点的左子节点
    int right = 2 * index + 2; // 当前待调整节点的右子节点
	
	// 如果左子节点大于根节点
	if (left < length && arr[left] > arr[largest])
        largest = left;
	// 如果右子节点大于当前最大值
    if (right < length && arr[right] > arr[largest])
        largest = right;
	
	// 如果最大值不是当前待调整节点
    if (largest != index) 
	{
		// 交换当前元素和最大值元素的位置
		int temp = arr[largest];
		arr[largest] = arr[index];
		arr[index] = temp;
        // 递归调整受影响的子树
        dagendui(arr, length, largest);
    }
}
/**
 * @brief 堆排序算法
 * @param arr 待排序数组
 * @param length 待排序数组长度
 */
void dui(int arr[], int length)
{
	// 1. 构建大根堆（从最后一个非叶子节点开始）
    for (int i = length / 2 - 1; i >= 0; i--)
		dagendui(arr, length, i);
	
	// 2. 进行堆排序
	for (int i = length - 1; i > 0; i--)
	{
		// 将大根堆当前根节点（最大值）移动到数组末尾
		int temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;
		
		// 重新构建大根堆
		dagendui(arr, i, 0);
	}
}

对我来说堆排序的难点主要是构建大根堆函数dagendui()中的逻辑：

上面的代码中核心思想是：

  1. 进入函数，首先假设待调整节点的索引i就是最大值对应的索引largest = i；
  2. 然后计算左右子节点的索引；
  3. 判断左子节点的索引是否小于数组长度，再判断左子节点对应的值是否大于最大值索引largest对应的值，如果大于，则更新最大值对应的索引largest = 2*i+1（这里不进行值的交换，只更新索引）；
  4. 判断右子节点的索引是否小于数组长度，再判断右子节点对应的值是否大于最大值索引largest对应的值，如果大于，则更新最大值对应的索引largest = 2*i+2（这里不进行值的交换，只更新索引）；
  5. 判断最大值对应的索引largest是否还等于i，若不等于，说明左右子节点有比待调整节点对应的值还大的，根据大根堆的原则，需要进行调整，这时候就之间交换largest索引和i索引对应的值即可；
  6. 最后不要忘了：递归调整受影响的子树（因为交换元素后，交换下来的元素有可能在以自己为根节点的子树上不是最大堆）。

1.1.4 归并排序

（一）归并排序算法源代码

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

/**
 * @brief 合并两个有序子数组
 * @param arr: 原数组
 * @param left: 左子数组起始索引
 * @param mid: 左子数组结束索引（右子数组起始索引为mid+1）
 * @param right: 右子数组结束索引
 */
void merge(int arr[], int left, int mid, int right) 
{
    // 1. 计算左右子数组的长度
    int len_left = mid - left + 1;  // 左子数组长度
    int len_right = right - mid;    // 右子数组长度

    // 2. 创建临时数组存储左右子数组（避免修改原数组时覆盖数据）
    int* left_arr = (int*)malloc(len_left * sizeof(int));
    int* right_arr = (int*)malloc(len_right * sizeof(int));

    // 3. 将原数组中的数据复制到临时数组
    for (int i = 0; i < len_left; i++) 
        left_arr[i] = arr[left + i];  // 左子数组范围：[left, mid]

    for (int j = 0; j < len_right; j++)
        right_arr[j] = arr[mid + 1 + j];  // 右子数组范围：[mid+1, right]

    // 4. 合并两个临时数组到原数组（核心步骤）
    int i = 0;      // 左子数组的当前索引
    int j = 0;      // 右子数组的当前索引
    int k = left;   // 原数组中合并后的起始索引

    // 比较两个子数组的元素，按从小到大顺序放入原数组
    while (i < len_left && j < len_right) 
    {
        if (left_arr[i] <= right_arr[j]) 
        {
            arr[k] = left_arr[i];
            i++;
        } 
        else 
        {
            arr[k] = right_arr[j];
            j++;
        }
        k++;
    }

    // 5. 处理剩余元素（若左子数组有剩余）
    while (i < len_left) 
    {
        arr[k] = left_arr[i];
        i++;
        k++;
    }

    // 6. 处理剩余元素（若右子数组有剩余）
    while (j < len_right)
    {
        arr[k] = right_arr[j];
        j++;
        k++;
    }

    // 释放临时数组内存
    free(left_arr);
    free(right_arr);
}

/**
 * @brief 归并排序主函数（递归）
 * @param arr: 待排序数组
 * @param left: 数组起始索引
 * @param right: 数组结束索引
 */
void merge_sort(int arr[], int left, int right) 
{
    // 递归终止条件：当子数组长度为1时（left == right），无需排序
    if (left < right) 
    {
        // 1. 计算中点（避免溢出：mid = (left + right) / 2 可能溢出，改用下面的写法）
        int mid = left + (right - left) / 2;

        // 2. 递归排序左子数组 [left, mid]
        merge_sort(arr, left, mid);

        // 3. 递归排序右子数组 [mid+1, right]
        merge_sort(arr, mid + 1, right);

        // 4. 合并两个已排序的子数组
        merge(arr, left, mid, right);
    }
}

// 辅助函数：打印数组
void print_array(int arr[], int size) 
{
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组：");
    print_array(arr, size);

    // 调用归并排序（初始范围：0到size-1）
    merge_sort(arr, 0, size - 1);

    printf("排序后的数组：");
    print_array(arr, size);

    return 0;
}

归并排序的两个重要函数：

  1. 合并两个有序数组函数void merge(int arr[], int left, int mid, int right)，这个函数的逻辑还比较简单；
  2. 归并排序主函数void merge_sort(int arr[], int left, int right)，这个函数的逻辑感觉确实有点难理解，实在不行就硬记吧，代码量不大
    • Step1：计算中点
    • Step2：递归排序左子数组
    • Step3：递归排序右子数组
    • Step4：合并排序后的左右子数组

（二）归并算法用于链表排序

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
typedef struct ListNode {
    int val;
    struct ListNode *next;
}ListNode;

// 合并两个有序链表
ListNode* MergeLink(ListNode* start, ListNode* mid)
{
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    ListNode* reslut = head;
    while(start && mid)
    {
        if(start->val < mid->val)
        {
            head->next = start;
            start = start->next;
        }
        else
        {
            head->next = mid;
            mid = mid->next;
        }
        head = head->next;
    }
    if(start)
        head->next = start;
    if(mid)
        head->next = mid;
    return reslut->next;
}

// 链表的归并排序
ListNode* sortList(ListNode* head)
{
    // 边界条件：链表为空或者只有一个节点
    if(head == NULL || head->next == NULL)
        return head;
    
    // 使用快慢指针的方法找到链表的中间节点
    ListNode* slow = head;
    ListNode* fast = head->next;
    while(fast && fast->next)
    {
        // 慢指针走一步
        slow = slow->next;
        // 快指针走两步
        fast = fast->next->next;
    }
    // 新定义一个节点为链表的头节点
    ListNode* start = head;
    // 找到链表的中间节点
    ListNode* mid = slow->next;
    // 把链表一分为二
    slow->next = NULL;

    // 递归排序链表的第一部分
    start = sortList(start);
    // 递归排序链表的第二部分
    mid = sortList(mid);
    
    // 合并两部分链表
    return MergeLink(start, mid);
}

参考链接：【LeetCode 148】排序链表 - 华南溜达虎 - 哔哩哔哩

1.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
#include <stdio.h>
#include <stdlib.h>
 
// 定义二叉树节点结构体
typedef struct TreeNode {
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int val)
{
    TreeNode* ptreenode = (TreeNode*)malloc(sizeof(TreeNode));
    ptreenode->value = val;
    ptreenode->left = NULL;
    ptreenode->right = NULL;
    
    return ptreenode;
}

// 前序遍历函数
void preOrderTraversal(TreeNode *cur)
{
    if(!cur)
        return;
    
    // 遍历根节点
    printf("%d ", cur->value);
    // 遍历左子树
    preOrderTraversal(cur->left);
    // 遍历右子树
    preOrderTraversal(cur->right);
}

// 中序遍历函数
void milOrderTraversal(TreeNode *cur)
{
    if(!cur)
        return;
    
    // 遍历左子树
    milOrderTraversal(cur->left);
    // 遍历根节点
    printf("%d ", cur->value);
    // 遍历右子树
    milOrderTraversal(cur->right);
}

// 后序遍历函数
void postOrderTraversal(TreeNode *cur)
{
    if(!cur)
        return;
    
    // 遍历左子树
    postOrderTraversal(cur->left);
    // 遍历右子树
    postOrderTraversal(cur->right);
    // 遍历根节点
    printf("%d ", cur->value);
}

int main() 
{
    // 构建一个简单的二叉树进行测试
    //        1
    //      /   \
    //     2     3
    //   /   \  /  \
    //  4    5 6    7
    //             / \
    //            8   9
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    
    root->right->right->left = createNode(8);
    root->right->right->right = createNode(9);
 
    printf("前序遍历顺序: ");
    preOrderTraversal(root);
    printf("\n中序遍历顺序: ");
    milOrderTraversal(root);
    printf("\n后序遍历顺序: ");
    postOrderTraversal(root);
    printf("\n");
 
    return 0;
}