插入排序详解(c语言)

一. 插入排序

1.1 插入排序的图解及原理

插入排序的步骤：
.对于无序序列，其首项加入新的有序序列
.遍历无序序列的元素，将其插入到有序序列的合适位置

上图是对插入排序的一个图解，接下来我们新建一个数组

int a[5]={2,5,8,3,6}
1

假设要实现升序，我们可以发现前三个数组里的元素是有序的，那么只需要从第四个元素（即下标为3的元素）开始进行排序，那么前四个元素的排序分为以下几个步骤：
1.定义变量存储当前位置的值
注：假设[0,end]为有序数组，在这里end就是2，a[end+1]就是第四个元素

int tmp=a[end+1];
1

2.判断当前位置与上一个位置的大小关系，如果上一个位置比当前位置的值要大，就进行挪动覆盖，但是注意上一个位置的数暂时没变，因为要进行下一次比较，

		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
1
2
3
4
5
6
7
8
9
10
11
12
13

在这里
第一次比较：

第二次比较：

第三次比较：

3.第2步其实只是一趟的代码，解析完后我们也发现其实我们没排第五个元素
那么在最外面我们就要套一个循环来控制end这个变量，因为我们是假设[0,end]是有序的，但是这个数组一开始是未知的，所以我们遍历整个数组来控制end

for (int i = 0; i < n - 1; i++)
{
	int end=i;
	...
	...
}
1
2
3
4
5
6

1.2插入排序的代码

void InsertSort(int *a,int size)
{
   	for (int i = 0; i < n - 1; i++)
	{
		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;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.3插入排序的时间复杂度与稳定性

首先提前告诉大家插入排序的时间复杂度是O(n^2),有人可能觉得这和冒泡排序一个样，毕竟循环里面套循环，但是可以很负责任大家，他们只是一个量级，插入排序比冒泡排序厉害的不是一星半点
我们随机生成100000个数进行性能的测试：

我们可以清晰的看到，插入排序比冒泡排序快将近10倍，因此同一个量级也分个高低
插入排序时间复杂度的计算：

• 显而易见的是，逆序的时候进行排序是最坏的情况
  这时候我们第一次需要1次排序，第二次2次，以此类推
  共进行1+2+3+…+(n-1)=(n^2-n)/2
  然后根据时间复杂度的计算规则得出插入排序最坏情况的时间复杂度为O(n^2)
• 升序则是最好的情况
  但是我们还是要遍历一遍数组，因为我们一开始也不知道他是升序的，
  因此插入排序最好情况的时间复杂度为O(n)
• 由以上可以知道插入排序的平均时间复杂度是O(N^2).

插入排序的稳定性：
插入排序是插入到比它大的数前面，所以插入排序是稳定的
注：具体等写完八大排序算法再总结

愿你的代码生涯如同登山，一步一个脚印，攀登到编程的高峰。