当前位置：首页 > news >正文

插入排序解析

news 2025/7/2 6:12:43

可以将插入排序类比为整理扑克牌的过程：

左手持已排序的牌（初始为空）右手从桌上未排序的牌堆中逐张取牌将取到的牌插入左手正确位置最终左手持完全有序的牌

前言

一、算法工作原理

插入排序是一种基于比较的简单排序算法，其核心思想是逐步构建有序序列。算法将待排序数组视为两个部分：已排序部分（初始时仅包含第一个元素）和未排序部分。通过不断从未排序部分取出元素，在已排序部分中找到适当位置插入，最终完成整个数组的排序。

1.2 算法基本特性

特性	描述
时间复杂度(最优)	O(n) - 当输入数组已经有序时
时间复杂度(最差)	O(n²) - 当输入数组完全逆序时
时间复杂度(平均)	O(n²)
空间复杂度	O(1) - 原地排序，不需要额外存储空间
稳定性	稳定 - 相等元素的相对位置不会改变

二、算法详细实现

1. 标准插入排序（从后向前比较插入）

#include <stdio.h>void Sort(int arr[], int n) {for(int i=1;i<n;++i){int k=arr[i];int j=i-1;while(j>=0&&arr[j]>k){arr[j+1]=arr[j];j--;}arr[j+1]=k;// 插入到正确位置}
}
int main() {int arr[] = {12, 9, 7, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);Sort(arr, n);for (int i = 0; i < n; i++) printf("%d ", arr[i]);  // 输出：5，6，7，9，12return 0;
}

初始状态：已排序部分：[12]未排序部分：[11, 13, 5, 6]

第一轮迭代（i=1）：key=11，j=0比较：12 > 11 → 后移12 → [12,12,13,5,6]j=-1退出循环插入：arr[0]=11 → [11,12,13,5,6]

第二轮迭代（i=2）：key=13，j=1比较：12 < 13 → 不移动直接插入 → [11,12,13,5,6]

第三轮迭代（i=3）：key=5，j=2比较：13 > 5 → 后移13 → [11,12,13,13,6]比较：12 > 5 → 后移12 → [11,12,12,13,6]比较：11 > 5 → 后移11 → [11,11,12,13,6]j=-1退出循环插入：arr[0]=5 → [5,11,12,13,6]

第四轮迭代（i=4）：key=6，j=3比较：13 > 6 → 后移13 → [5,11,12,13,13]比较：12 > 6 → 后移12 → [5,11,12,12,13]比较：11 > 6 → 后移11 → [5,11,11,12,13]比较：5 < 6 → 停止插入：arr[1]=6 → [5,6,11,12,13]

下面的代码就不过多解释了可以自己看看

2. 交换法插入排序

特点：代码更短，但交换操作比移动更耗时（适用于小数据量）。

void SortSwap(int arr[], int n) 
{for (int i = 1; i < n; i++) {int j = i;// 边比较边交换，类似冒泡while (j > 0 && arr[j] < arr[j - 1]){int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;j--;}}
}

这个和冒泡排序没差很多只不过是一直保持i前面的有序

3. 二分查找优化插入排序

int Search(int arr[], int key, int low, int high) {while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] < key) low = mid + 1;else high = mid - 1;}return low;  // 返回插入位置
}void SortBinary(int arr[], int n){for (int i = 1; i < n; i++){int key = arr[i];int pos = Search(arr, key, 0, i - 1); // 一直往后移动为key提供位置for (int j = i; j > pos; j--){arr[j] = arr[j - 1];}arr[pos] = key;  // 插入}
}

这个就是直接寻找位置然后进行间接插入直到访问到最后一个

4. 递归实现插入排序

void Sort(int arr[], int n, int i) {if (i == n) return;int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;Sort(arr, n, i + 1);
}

这样的递归更好一点比从中间递归要优化许多