C语言程序设计十大排序—插入排序

文章目录

1.概念✅
2.插入排序🎈
3.代码实现✅
- 3.1 直接写✨
- 3.2 函数✨
4.总结✅
5.十大排序

1.概念✅

排序是数据处理的基本操作之一，每次算法竞赛都很多题目用到排序。排序算法是计算机科学中基础且常用的算法，排序后的数据更易于处理和查找。在计算机发展的历程中，在排序算法的研究一直深受人们重视，出现了很多算法，在思路、效率、应用等方面各有特色。通过学习排序算法，读者可以理解不同算法的优势和局限性，并根据具体情况选择最合适的算法，以提高程序的性能和效率。学习排序算法还有助于培养逻辑思维和问题解决能力，在解决其他类型的问题时也能够应用到类似的思维方法。

2.插入排序🎈

插入排序（Insertion Sort）是一种“动态”算法，在一个有序数列上这个增加数据，当新增一个数x时，把它插到有序数列中的合适位置，使数列扔保持有序。初始的数列是空的，这个插入所有的n个数据后，这n个数据就排好了序。
如何把x插到合适的位置？简单的做法是从有序数列的最后一个开始，逐个与x比较，若这个数比x大，就继续往前找，直到找到比x小的数，把x插到它的后面。
具体操作{12, 11, 13, 5, 6}为例，如下图所示:
（1）从第一个数a[0]开始，它构成了长度为1的有序数列a[0]。

在这里插入图片描述

（2）新增a[1]，把它插到有序数列{a[0]}中。

若a[1]>a[0]，完成，
若a[1]<a[0]，把a[1]插到a[0]的前面。方法是先把a[0]移到数列的第2个位置，然后把a[1]放到数列的第1个位置，得到新的有序数列{a[0],a[1]}。
（3）新增a[2]，把它插到有序数列{a[0], a[1]}中。
在这里插入图片描述
概括插入排序的原理：将待排序的元素划分为“已排序”和“未排序”两个部分，每次从“未排序的”元素中选取一个插到“已排序”元素中的正确位置。插入排序的一个列子是打扑克时抓牌，每抓一张牌，就插入到手中排好序的牌中。

3.代码实现✅

3.1 直接写✨

#include "stdio.h"
int main() {int arr[] = {12, 11, 13, 5, 6}; // 原始数组int n = sizeof(arr) / sizeof(arr[0]); // 数组大小int i;// 插入排序实现for ( i = 1; i < n; i++) {int key = arr[i];  // 当前待插入的元素int j = i - 1;// 将大于key的元素移到右侧while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}// 插入当前元素到正确的位置arr[j + 1] = key;}// 打印排序后的数组printf("排序后的数组: \n");for (i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}

3.2 函数✨

#include <stdio.h>void insertionSort(int arr[], int n) {int i, key, j;// 从第二个元素开始，遍历整个数组for (i = 1; i < n; i++) {key = arr[i];  // 当前待插入的元素j = i - 1;// 将大于key的元素移到右侧while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}// 插入当前元素到正确的位置arr[j + 1] = key;}
}void printArray(int arr[], int n) {int i; for ( i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {12, 11, 13, 5, 6}; // 原始数组int n = sizeof(arr) / sizeof(arr[0]); // 数组大小insertionSort(arr, n); // 调用插入排序函数printf("排序后的数组: \n");printArray(arr, n); // 打印排序后的数组return 0;
}

4.总结✅

插入排序的计算复杂度取决于第5行的for循环和第8行的while循环，这是两重循环，各循环O(n)次，总计算复杂度O(n^2)。
插入排序是不是和冒泡排序一样“聪明”？也就是说，如果待排序的数列已经有序了，再运行插入排序算法，插入排序是否知道已经排好序？此时第8行的while的判断条件a[i]>key始终不成立，while内的不会执行，而实际上就是a[i]=key，没有任何变化。也就是说，再次插入都是插到末尾，不用插到中间。那么for、while这两重循环实际上变成了只有for一个循环，一共计算O(n)次即结束。所以插入排序和“冒泡”排序一样“聪明”。

Perspective-takling