8.插入排序

  插入排序算法是一种简单的排序算法，也成为直接插入排序算法。它是一种稳定的排序算法，对局部有序的数据具有较高的效率。

  插入排序算法是一个对少量元素进行排序的有效算法。比如，打牌是我们使用插入排序方法最多的日常生活例子。我们在摸牌时，一般会重复一下步骤。起初，我们手里没有牌，摸出第一张，随意放在左手上，以后每一次摸排，都会按照花色从小到大排列，直到所有的牌摸完。插入排序算法采用的类似思路，每一次从无序序列中拿出一个数据，将它放到已排序的序序列的正确位置，如此重复，直到所有的无序序列中的数据都找到了正确位置。

插入排序

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void insertSort(int arr[], int len)
{
	for (int i = 1; i < len;i++)
	{
		if (arr[i-1] > arr[i])
		{
			int temp = arr[i];
			int j = i - 1;
			for (; j >= 0 && temp < arr[j]; j--)
			{
				//数据后移
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = temp;
		}
	}
}

void printArray(int arr[] ,int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d\n",arr[i]);
	}
}

void test01()
{
	int arr[] = { 4, 1, 2, 3, 5, 7, 6 };
	//插入排序
	int len = sizeof(arr) / sizeof(int);
	insertSort(arr, len);

	//打印数组
	printArray(arr, len);
}

int main()
{
	test01();

	system("pause");
	return EXIT_SUCCESS;
}

参考资料来源：

黑马程序员