【排序算法】一、排序概念和直接插入排序（C/C++）

本文介绍: 直接插入排序

在这里插入图片描述

例如，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序

具体步骤如下：

例如，对数组[4, 2, 5, 1, 6, 3]进行排序，使用直接插入排序，如下：（升序）
在这里插入图片描述
动图演示：（数据不和上面相同）

C语言代码如下：（升序）

// 直接插入排序
void InsertSort(int* arr, int n) // arr:需要排序的数组; n:数组的大小
{
	for (int i = 0; i < n-1; ++i) // 达到n-1时，数组已经有序，无需再遍历最后一次，避免多余的循环
	{
		// [0, end]有序，把end+1位置的值插入，保持有序
		int end = i; // 记录有序序列的最后一个下标
		int tmp = arr[end + 1]; // 保存等待插入的值

		while (end >= 0) 
		{
			if (arr[end] > tmp) // arr[end]比要插入的数大，向后移动
			{
				arr[end + 1] = arr[end]; // 向后移，进行覆盖，tmp已经保存被覆盖的值
				--end; // 迭代
			}
			else // arr[end]比要插入的数小，已有序，跳出循环
			{
				break;
			}
		}
		arr[end + 1] = tmp; // 进行插入
	}
}

C++代码：（升序）

// 直接插入排序
void InsertSort(vector<int>& arr)
{
	int n = arr.size();
	for (int i = 0; i < n - 1; ++i) // 达到n-1时，数组已经有序，无需再遍历最后一次，避免多余的循环
	{
		// [0, end]有序，把end+1位置的值插入，保持有序
		int end = i; // 记录有序序列的最后一个下标
		int tmp = arr[end + 1]; // 保存等待插入的值

		while (end >= 0)
		{
			if (arr[end] > tmp) // arr[end]比要插入的数大，向后移动
			{
				arr[end + 1] = arr[end]; // 向后移，进行覆盖，tmp已经保存被覆盖的值
				--end; // 迭代
			}
			else // arr[end]比要插入的数小，已有序，跳出循环
			{
				break;
			}
		}
		arr[end + 1] = tmp; // 进行插入
	}
}

「 作者 」 枫叶先生
「 更新 」 2024.1.9
「 声明 」 余之才疏学浅，故所撰文疏漏难免，
          或有谬误或不准确之处，敬请读者批评指正。

显示所有内容

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

排序插入排序算法

目录

一、排序概念的介绍

二、直接插入排序

2.1 原理

2.2 代码实现（C/C++）

2.3 特性总结

发表回复取消回复

目录