数据结构从入门到精通——直接插入排序

鲜于言悠

发布于 2024-03-24 12:57:15

2090

发布于 2024-03-24 12:57:15

直接插入排序

前言

直接插入排序是一种简单的排序算法，其工作原理是逐个将待排序元素插入到已排序序列中的适当位置，直到全部元素排序完毕。算法从第二个元素开始，将其与前面的元素进行比较，如果当前元素小于前一个元素，则将其插入到前一个元素之前，否则继续向前比较。重复此过程，直到当前元素找到合适的插入位置。每次插入一个元素后，已排序序列的长度增加1，直到整个序列排序完成。直接插入排序的时间复杂度为O(n^2)，在数据量较小时效率较高，但在大规模数据排序中性能不佳。

一、直接插入排序的基本思想：

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

具体步骤为：从第一个元素开始，认为该元素已经被排序；取出下一个元素，在已排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复以上步骤。

二、直接插入排序的实例

直接插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

假设我们有一个整数列表 [5, 3, 8, 4, 2] 需要进行排序。

首先，我们认为列表的第一个元素 5 已经是一个有序序列。

然后，我们取第二个元素 3，与已排序序列 [5] 进行比较。因为 3 小于 5，所以我们将 3 插入到 5 的前面，得到新的已排序序列 [3, 5]。

接下来，我们取第三个元素 8，与已排序序列 [3, 5] 进行比较。8 大于 3 和 5，所以我们将 8 插入到序列的末尾，得到新的已排序序列 [3, 5, 8]。

然后，我们取第四个元素 4，与已排序序列 [3, 5, 8] 进行比较。4 应该插入到 3 和 5 之间，所以我们将 4 插入到适当的位置，得到新的已排序序列 [3, 4, 5, 8]。

最后，我们取第五个元素 2，与已排序序列 [3, 4, 5, 8] 进行比较。2 是最小的元素，所以我们将 2 插入到序列的最前面，得到最终的已排序序列 [2, 3, 4, 5, 8]。

通过这个过程，我们可以看到直接插入排序是如何逐步构建有序序列的。虽然直接插入排序在大数据集上可能不是最有效的排序算法，但它的实现简单，对于小规模数据或部分有序的数据，直接插入排序是一个很好的选择。

实际中我们玩扑克牌时，就用了插入排序的思想

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

直接插入排序的特性总结：

元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O(N^2)
空间复杂度：O(1)，它是一种稳定的排序算法
稳定性：稳定

直接插入排序的特性总结，在于其简单直观、稳定且空间复杂度低，但同时其时间复杂度较高，特别是在处理大数据集时效率不高。

直接插入排序是一种简单的排序算法，它的基本思想是将一个待排序的元素按其大小插入到已排序的序列中的适当位置，从而得到一个新的、个数增加1的有序序列。这一过程从第一个元素开始，每次将一个元素插入到已排序序列的合适位置，直到所有元素都插入完毕。

直接插入排序的稳定性是其一大特点。稳定性指的是在排序过程中，相等的元素在排序前后的相对位置不变。由于直接插入排序在插入元素时，遇到相等元素会选择将新元素放在已有元素的后面，因此它能够保证稳定性。

此外，直接插入排序的空间复杂度较低，因为它只需要一个额外的存储空间来暂存待插入的元素，不需要像其他排序算法那样开辟额外的数组空间。

然而，直接插入排序的时间复杂度较高，尤其是当处理大数据集时。在最坏的情况下，即待排序序列完全逆序时，直接插入排序的时间复杂度为O(n^2)，其中n为待排序元素的个数。这意味着随着数据量的增加，排序所需的时间将呈平方级增长，导致效率低下。

综上所述，直接插入排序具有稳定性好、空间复杂度低的特点，但时间复杂度较高，适用于小规模数据的排序。在实际应用中，可以根据数据的特点和排序需求来选择合适的排序算法。

三、直接插入排序的动图展示

直接插入排序

直接插入排序是一种简单的排序算法。其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。动图展示这一过程：初始时，已排序序列只包含一个元素，每次从未排序序列中取出一个元素，与已排序序列中的元素比较并插入到正确位置，直到所有元素都插入到已排序序列中，排序完成。此过程通过动画形式展示，能直观理解直接插入排序的工作原理。

四、直接插入排序的具体代码

test.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void InsertSort(int* a,int n)
{
	for (int i = 0; i < n - 1; i++)//因为本函数记录的是下一个位置，所以是n - 1 
	{
		int end = i;
		int tmp = a[end + 1];//记录下一个位置
		while (end >= 0)//从当前位置逐个向前判断
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];//直接拷贝
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;//覆盖
	}
}


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void TestOP()
{
	srand((unsigned int)time(0));
	const int N = 10000;
	int* a = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		a[i] = rand();
	}
	int begin1 = clock();
	InsertSort(a, N);
	int end1 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	free(a);
}
void TestInsertSort()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	PrintArray(a, sizeof(a) / sizeof(int));

	InsertSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
	TestInsertSort();
	
	TestOP();

	return 0;
}

该段代码实现了插入排序算法。函数InsertSort接受一个整数数组a和数组长度n作为参数。算法通过逐个处理数组中的元素，将其插入到已排序部分的正确位置，从而实现整个数组的排序。在每次迭代中，算法选择当前位置之后的一个元素，并向前搜索已排序部分，直到找到适当的位置插入该元素。算法通过覆盖元素的位置来实现插入，并在循环结束时将当前元素放置到正确的位置。这个过程对数组中的每个元素都重复进行，直到整个数组都被排序。