排序学习思路:先实现单趟逻辑,在实现整体逻辑;先解决普遍情况,再解决特殊情况。

什么是插入排序

回忆下自己玩扑克牌的时候是怎么把手上的牌理顺的吧!其实那就是插入排序,从左边往右边,把一张张抽出来在左边插入到它适合的位置。

插入排序的特点是:完成插入动作的牌之间的是有序的,如下面动图中,开始插入7时,它前面插入过的3,5,9是有序的;开始插入2时,它前面插入过的3,5,9,7之间是有序的。

插入排序图解

排序前

排序过程

排序后

代码实现

#include <stdio.h>

void InsertSort(InSoDataType* a, int n)
{
	//n个元素的数组,下标范围[0, n-1]
	for (int p = 0; p < n; ++p)
	{
		//[0, end]有序,把a[end + 1]插入到前面序列
		int end = p;
		InSoDataType tmp = a[end];
		while (end > 0)
		{
			if (tmp < a[end - 1])
			{
				a[end] = a[end - 1];
				--end;
			}
			else break;
		}
		a[end] = tmp;
	}
}

void PrintfArr(int* a, int n)
{
	for (int i = 0; i < n; ++i)
		printf(" %d ", a[i]);
	printf("\n");
}

int main()
{
	int arr[] = { 3, 5, 9, 7, 2, 1 };
	int arrsize = sizeof(arr) / sizeof(arr[0]);
	InsertSort(arr, arrsize);
	PrintfArr(arr, arrsize);

	return 0;
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部