[数据结构与算法]排序1:直接插入排序

??很久没有写博客了,最近打算完整的写一个专题关于数据结构中排序算法的内容??

? ? ? ? ? 这一期我们来剖析一下直接插入排序的底层逻辑和代码实现。

目录

插入排序的基本思想

单趟的实现

加入循环让整个排序跑起来

插入排序的基本思想

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。 这一点就类似于我们打扑克的时候把一张牌插入到其他牌的前面。

单趟的实现

?一口气吃不成一个大胖子，想要实现整个排序，我们应该来先实现单轮排序。

逻辑大致可分为以下：

? ? ? ? 1、从后往前遍历。

? ? ? ? 2、比较后一个与前一个的大小。

? ? ? ? 3、a：如果后面的数要小于前面的数，那么小的数插入到前面，然后被插入位置的后面的数字整体往后移动一格。

其单轮的代码如下：

int end = i;
		int temp = a[end + 1];
		//比前一个小,插进去,然后整体往后移动一个
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;

? ? ?从后往前遍历我们由end来实现，end递减，实现了从后往前。然后比较下标为end和下标为end+1位置的大小，再考虑是否插入移动。

加入循环让整个排序跑起来

我们知道，n个数字实际上只需要排n-1轮就行了，因为如果排完了n-1个数字，剩下的一个肯定也归位了。另外，如果循环次数设置为n次，那么最后一次如果与后面的比较，就会发生越界。

综上，我们代码实现如下：

void InsertSort(int* a, int n)
{
	//范围逐渐阔大
	for (int i = 0; i < n - 1; ++i)
	{
		int end = i;
		int temp = a[end + 1];
		//比前一个小,插进去,然后整体往后移动一个
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;

	}
}

接下来,我们放一个乱序的数组进行测试:

void TestInsertSort()
{
	int a[] = { 34,56,25,65,86,99,72,66 };
	InsertSort(a, sizeof(a) / sizeof(int));
	Print(a, sizeof(a) / sizeof(int));
}

最终排成了由小到大的数:

总结：