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

插入排序算法（C++版）

news 2025/8/5 1:38:29

1、什么是插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，它的基本思想是将一个待排序的数组分为已排序和未排序两个部分，然后逐步将未排序的元素插入到已排序的部分，直到整个数组有序。

2、插入排序的基本步骤：

初始化：将数组的第一个元素视为已排序部分，其余的元素视为未排序部分。
逐步插入：从未排序部分取出一个元素，插入到已排序部分的适当位置，使得已排序部分仍然有序。
重复：重复步骤2，直到未排序部分为空，整个数组变得有序。

3、插入排序的适用范围和特点：

适用范围：

插入排序适用于小规模的数据集或部分有序的数据集。
当数据规模较小时，插入排序的效率较高，而且对于基本有序的数据集，插入排序的性能表现也不错。

特点：

简单直观：插入排序是一种直观且易于理解的排序算法，适用于教学和小规模数据集的排序。
稳定性：插入排序是一种稳定的排序算法，相同元素的相对顺序在排序前后不会改变。
原地排序：插入排序是一种原地排序算法，它不需要额外的内存空间来存储临时数据。
适应性：对于基本有序的数据集，插入排序的性能较好。算法会在已有的有序部分快速找到适当位置插入新元素。
时间复杂度：最坏情况下的时间复杂度为O(n^{2)，最好情况下（已经有序）的时间复杂度为O(n)，平均时间复杂度为O(n}2)。

虽然插入排序在大规模数据集上的性能不如一些高级排序算法（例如快速排序、归并排序），但在某些特定场景下，插入排序可以是一个合适的选择，尤其是对于小规模或基本有序的数据。

4、插入排序算法示例

#include <iostream>
#include <vector>void insertionSort(std::vector<int> &arr) {int n = arr.size();for (int 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;}// 将 key 插入到合适的位置arr[j + 1] = key;}
}void printArray(const std::vector<int> &arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}int main() {std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};std::cout << "Unsorted array: ";printArray(arr);insertionSort(arr);std::cout << "Sorted array: ";printArray(arr);return 0;
}