直接插入排序

算法思想

从当前位置开始，从后往前找比当前数字小的数字，找到后插入到这个小的数字后面；

在找的过程中，如果发现一个比当前数字大的数字，则两个数字同时往后挪。

算法思想举例

数组：9 8 7 6 5

首先从第二位数字“8”开始，从“8”往前找比“8”小的数字，因为只有“9”，“9”大于“8”，则“9”挪到“8”位置，“9”前面没数字了，则把“8”放在第一位。

如果数组为：7 8 9 5 6

则数字“8”前面只有“7”，比“8”小，则把“8”插在“7”后面。

如果数组为：1 2 3 4 6 7 8 5

当前数字为“5”，从“5”往前找，“8”大于“5”，“8”放在“5”的位置，“7”大于“5”，“7”放在“8”的位置，“6”大于“5”，“6”放在“7”的位置，“4”小于“5”，“5”放在“4”后面的位置。

代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

void InsertSort(int* arr, int len)
{
	for (int i = 1; i < len; ++i)
	{
		int tmp = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] > tmp)
		{
			j--;
		}
		int k = i;
		for (; k > j + 1; --k)
		{
			arr[k] = arr[k - 1];
		}
		arr[k] = tmp;
	}
}

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

int main()
{
	int str[] = { 8,5,3,6,7,9 };
	int n = sizeof(str) / sizeof(str[0]);
	InsertSort(str, n);
	Show(str, n);

	int arr[] = { 5,3,9,7,11,11,1 };
	int m = sizeof(arr) / sizeof(arr[0]);
	InsertSort(arr, m);
	Show(arr, m);
	return 0;
}

效率分析

时间复杂度：O(n^2)（完全有序为O(n)）

空间复杂度：O(1)

稳定性：稳定（没有跳跃式的交换）