【基于C的排序算法】插入排序之直接插入排序

前言

本文基于C语言来分享一波笔者对于排序算法的插入排序中的直接插入排序的学习心得与经验，由于水平有限，纰漏难免，欢迎指正交流。

直接插入排序

​ 直接插入排序是一种简单的插入排序法，其基本思想是 ：

​ 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为
止，得到一个新的有序序列 。
​ 实际中我们玩扑克牌时，就用了插入排序的思想

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

升序排列的示例：

下面以升序排列为例讲解过程：

​ 原序列中可以分成两个序列，前面的是已排序的有序序列，用一个下标end标志该序列的尾，初始状态下end是0；后面的是还未排序的序列，用一个tmp变量暂存未排序序列首个元素，实际上是通过tmp = arr[end + 1] 实现的，也就是end指向的下一个元素。为什么要用变量暂存end的下一个元素呢？因为有可能涉及到元素后移，比如说，如果arr[end]要比tmp的值大，根据升序，应该把arr[end]的值后移对吧，那要是直接后移就会覆盖掉arr[end + 1]，所以在移动前要先把元素暂存到tmp中。在每一次比较后end要递减一下，向前移动。要是tmp比arr[end]要大该怎么操作呢？这时候就说明找到要插入的位置了，把tmp的值插入到arr[end + 1]即可。

​ 可以看出，直接插入排序不可能只有一轮，像前面讲的过程就是一轮的过程，结果就是把未排序序列的首元素插入到了已排序序列中并保持原来的顺序，正如把刚摸到的一张牌按顺序插入到你的手牌中。实际上，一开始序列是全部未排序的，我们可以把第一个元素作为已排序元素，也就是说已排序序列一开始只有一个元素，end值就为0，后面的元素就全部都是未排序序列的了。

​ 也就是说要将整个原序列排好序的话要让已排序序列拓展至整个原序列，也就是end要不断增加到size - 1（size是数组元素个数），end值为size - 1时结束，所以还要外套一个循环。

void InsertSort(int* arr, int sz)
{
	assert(arr);

	for (int i = 0; i < sz - 1; ++i)//i的取值就是end的取值，end最多取到sz-2算有效，当它取到sz-1时就该结束循环了
	{
		//单轮排序
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)//为什么要>=0呢？可不可以>0？
		{
			//要排升序		
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				--end;
			}
			else
			{				
				break;
			}		
		}
		arr[end + 1] = tmp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

​ end可以为0，因为有可能tmp的值比arr[0]还小，那就得让原来的arr[0]后移，把tmp放到arr[0]的位置。

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

1. 元素集合越接近有序，直接插入排序算法的时间效率越高，最好情况下（有序）时间复杂度为O(n)
2. 时间复杂度：O(n²)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

感谢观看，你的支持就是对我最大的鼓励~