C语言--八大排序之直接插入排序算法

排序：把无序的数据变得有序，默认升序。（笔试面试排名第一的内容）

1.直接(简单)插入排序（例如：扑克牌发牌时，每发一张，将牌有序插入）

从当前位置开始, 从后往前找比当前数字小的, 找到后插入到这个小的数字后面;
在找的过程中, 如果发现一个比当前数字大, 同时将这个数字往后挪;
 特点:1.越有序越快,完全有序的时间复杂度为：O(n),（非常重要,这个是希尔排序的基础），

         2.如果碰见一个和插入元素相等的元素，那么把插入元素放在相等元素的后面，即就是想等元素的先后顺序并没有改变，所以插入排序是一个稳定的排序。

 代码实现如下：

#include <stdio.h>

void InsertSort(int* arr, int len)//O(n^2),最好的情况,O(1),
{
	int tmp;//存放当前处理的数字
	int j;
	for (int i = 1; i < len; i++)//从第二个数字开始
	{//1 2 3 4 5
		tmp = arr[i];
		for (j = i - 1; j >= 0; j--)//从后往前找第一个比tmp小的数字
		{
			if (arr[j] > tmp)//arr[j]需要后移
				arr[j + 1] = arr[j];
			else
				break;
		}
		arr[j + 1] = tmp;
	}
}

//打印函数
void show(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d  ", arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[] = { 4,6,2,8,9,0,1,7,3,5 };
	InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
    show(arr, sizeof(arr) / sizeof(arr[0]));
	return 0;
}

运行结果：