一、插入算法>排序算法
基本思想
插入排序的基本思想是将未排序的元素逐个插入到已排序的序列中。初始时，假设序列的第一个元素已经被排序。然后从第二个元素开始，将其插入到已排序的序列中的适当位置，使得已排序的序列仍然有序。
步骤
- 初始化：假设数组的第一个元素已经排序好。
- 遍历数组：从第二个元素开始遍历数组。
- 比较并插入：对于每个未排序的元素，从当前位置开始向左比较，直到找到合适的位置插入该元素。
- 重复步骤2和3：重复这个过程，直到所有的元素都被插入到已排序的序列中。
示例
假设我们有一个数组 [5, 2, 4, 6, 1, 3]：
- 第一轮：
[5, 2, 4, 6, 1, 3]->[2, 5, 4, 6, 1, 3] - 第二轮：
[2, 5, 4, 6, 1, 3]->[2, 4, 5, 6, 1, 3] - 第三轮：
[2, 4, 5, 6, 1, 3]->[2, 4, 5, 6, 1, 3]（6已经是最大的，无需移动） - 第四轮：
[2, 4, 5, 6, 1, 3]->[1, 2, 4, 5, 6, 3] - 第五轮：
[1, 2, 4, 5, 6, 3]->[1, 2, 3, 4, 5, 6]
性能分析
- 最好情况：当输入数组已经是排序好的，时间复杂度为 O(n)。
- 最坏情况：当输入数组是逆序的，时间复杂度为 O(n^2)。
- 平均情况：时间复杂度为 O(n^2)。
- 空间复杂度：O(1)，因为它是原地排序。
二、代码
#include <stdlib.h>
#include <stdio.h>
#include <time.h>// 函数声明
int* create_and_generate_random_array(int size);
void print_array(int *array, int size);
void insertion_sort(int *array, int size);
int generate_random_size();int main() {int size = generate_random_size(); // 随机生成数组大小int *array = create_and_generate_random_array(size);if (array == NULL) {// 如果内存分配失败printf("Memory allocation failed\n");return 1;}// 打印原始数组（如果需要，可以取消注释）// printf("Original array:\n");// print_array(array, size);// 获取开始时间clock_t start_time = clock();// 对数组进行插入排序insertion_sort(array, size);// 获取结束时间clock_t end_time = clock();// 计算时间差并转换为毫秒double execution_time = ((double)(end_time - start_time) / CLOCKS_PER_SEC) * 1000;// 打印排序后的数组（如果需要，可以取消注释）// printf("Sorted array:\n");// print_array(array, size);printf("array_size = %d\n", size);// 打印执行时间printf("Execution time: %.2f ms\n", execution_time);// 释放分配的内存free(array);return 0;
}// 生成随机数组大小
int generate_random_size() {srand(time(NULL));return rand() % 9000 + 1000; // 生成1000到9999之间的随机数
}// 创建并生成随机数组
int* create_and_generate_random_array(int size) {int *array = (int *)malloc(sizeof(int) * size);if (array == NULL) {// 如果内存分配失败return NULL;}// 使用当前时间作为随机数种子srand(time(NULL));for (int i = 0; i < size; i++) {array[i] = rand() % 1000; // 生成0到999之间的随机数}return array;
}// 打印数组
void print_array(int *array, int size) {for (int i = 0; i < size; i++) {printf("%d ", array[i]);}printf("\n");
}// 插入排序
void insertion_sort(int *array, int size) {for (int i = 1; i < size; i++) {int key = array[i];int j = i - 1;// 将当前元素插入已排序的部分while (j >= 0 && array[j] > key) {array[j + 1] = array[j];j--;}array[j + 1] = key;}
}
