C语言插入排序(附带源码和解析)
插入排序是一种简单直观的排序算法,它的工作原理类似于我们打扑克牌时整理手中的牌。在这个过程中,我们会将每一张新拿到的牌插入到已经排好序的牌中的适当位置。插入排序就是采用了这种思想,通过构建有序序列,对未排序数据进行一个个插入操作,从而达到排序的目的。
插入排序的基本原理
插入排序的核心思想是将一个新元素插入到已经排好序的有序表中,从而得到一个新的、元素数量加一的有序表。具体来说,插入排序的过程如下:
- 从第一个元素开始,该元素可以认为已经被排序;
- 取出下一个元素,在已经排序的元素序列中从后向前扫描;
- 如果该元素(已排序)大于新元素,将该元素移到下一位置;
- 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置;
- 将新元素插入到该位置后;
- 重复步骤 2~5。
让我们通过一个具体的例子来理解这个过程。假设我们有一个数组 [5, 2, 4, 6, 1, 3],我们要对它进行升序排序。
// 初始状态 [5, 2, 4, 6, 1, 3] // 第一步,5 已经排序 [5 | 2, 4, 6, 1, 3] // 第二步,将 2 插入到已排序序列中 [2, 5 | 4, 6, 1, 3] // 第三步,将 4 插入到已排序序列中 [2, 4, 5 | 6, 1, 3] // 第四步,6 已经在正确的位置 [2, 4, 5, 6 | 1, 3] // 第五步,将 1 插入到已排序序列中 [1, 2, 4, 5, 6 | 3] // 最后一步,将 3 插入到已排序序列中 [1, 2, 3, 4, 5, 6]
在这个过程中,竖线左边的元素始终保持有序,而我们每次都将右边的一个元素插入到左边合适的位置。
C语言实现插入排序
下面是插入排序的C语言实现:
#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 = j - 1; } 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[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: \n"); printArray(arr, n); insertionSort(arr, n); printf("排序后的数组: \n"); printArray(arr, n); return 0; }
运行结果:
原始数组: 64 34 25 12 22 11 90 排序后的数组: 11 12 22 25 34 64 90
这段代码中,insertionSort 函数实现了插入排序的核心逻辑。它使用两个循环:外层循环遍历未排序部分的每个元素,内层循环将当前元素插入到已排序部分的正确位置。
插入排序的性能以及优缺点
插入排序的时间复杂度取决于输入数组的初始顺序:
- 最好情况:当数组已经是升序排列时,算法只需要进行 n-1 次比较和 0 次交换。时间复杂度为 O(n)。
- 最坏情况:当数组是降序排列时,每个元素都需要和已排序的所有元素比较,并移动到数组的首位。时间复杂度为 O(n^2)。
- 平均情况:在随机顺序的数组中,插入排序的平均时间复杂度也是 O(n^2)。
插入排序有以下优点:
- 简单直观,易于实现;
- 对于小规模数据或基本有序的数据效率较高;
- 是稳定排序算法,不会改变相同元素的相对位置;
- 可以用作其他复杂排序算法的子过程。
但插入排序也有一些缺点:
- 对于大规模乱序数组效率低下;
- 平均时间复杂度较高,不适合对大数据量进行排序。
结语
插入排序是一种简单但在某些情况下非常有效的排序算法,尽管它的平均时间复杂度为 O(n^2),但对于小规模数据或基本有序的数据,它可能会比一些更复杂的排序算法表现得更好。
你可能还想关注其它 9 种排序算法:
- C语言冒泡排序(附带源码和解析)
- C语言快速排序(附带源码和解析)
- C语言选择排序(附带源码和解析)
- C语言希尔排序(附带源码和解析)
- C语言归并排序(附带源码和解析)
- C语言堆排序(附带源码和解析)
- C语言计数排序(附带源码和解析)
- C语言桶排序(附带源码和解析)
- C语言基数排序(附带源码和解析)
声明:《算法系列教程》为本站“54笨鸟”官方原创,由国家机构和地方版权局所签发的权威证书所保护。