排序之插入排序

一 算法思想

 

以排升序为例：

第一个数据看作是已经排序好了的数据，从下标为1的第二个数据开始排序，将该数据作为end。需要将end+1的数据插入到之前的数据里面去，以形成有序的数据。那么先开辟一个tmp的空间，把这一个数据先存储起来，以防止后续的数据整体后移以及插入的时候数据的消失。

将该tmp空间中存储的数据分别与之前的数据一一进行比较，如果tmp比之前的数据要小，那么就要将该位置的数据往后移动一个位置，tmp再与前面的数据进行比较。直至tmp>该位置的数据，那么就将数据插入该位置的下一个位置。（之前已经通过移动预留出了一个数据的位置）。

上述的操作是一次数据插入的操作，需要对所有的数据进行操作，因此在外面再套一层循环控制。

二 代码展示

#define _CRT_SECURE_NO_WARNINGS 1 
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

void insertsort(int* pa, int size)
{
	assert(pa);

	int i = 0;
	for (i = 1; i <size-1; i++) 
	{
		int end = i;
		int tmp = pa[end + 1];
		while (end >= 0)
		{
			if (tmp < pa[end])
			{
				pa[end + 1] = pa[end];
				end--;
			}

			else
			{
				break;
			}

		}

		pa[end+1] = tmp;
	}
}

int main()
{
	int a[] = { 11,25,6,87,98,69,30,23,10,2 };
	int size = sizeof(a) / sizeof(a[0]);
	insertsort(a, size);
	int i = 0;
	for (i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}