排序方法（三）插入排序

使用语言：c语言，编译器visual studio 2017
一.基本思想
假设从小到大排序。从第二个数开始往后遍历，将每个数插入到前面的有序序列中，最后形成一整个有序序列。将第二个数与第一个数比较，小的放前面，可以视为第一次插入；将第三个数插入到第一第二个数形成的有序序列中，这是第二次插入；…将最后一个数插入完毕，则排序完毕。例子：将下列数排序：
56，48，10，7，0，23，10，99，90，40

二.代码实现

#include<stdio.h>
int main() {
	int array[100];
	int i = 0;
	int j = 0;
	int num = 0;
	printf("请输入待排序的数字个数：\n");
	scanf_s("%d", &num);
	printf("请输入%d个数字：\n", num);
	for (i; i<num; i++) scanf_s("%d", &array[i]);
	if (num == 1) return 0;
	if (array[0] >= array[1]) {
		int temp = array[0];
		array[0] = array[1];
		array[1] = temp;
	}
	printf("第1次插入的结果：%d %d\n", array[0], array[1]);
	if (num == 2) return 0;
	else {
		for (i = 2; i < num; i++) {
			int temp = array[i];
			for (j = i - 1; temp < array[j]; j--) {
				array[j + 1] = array[j];
				if (j == -1) break;
			}
			array[j + 1] = temp;
			printf("第%d次插入的结果：", i);
			for (int k = 0; k <= i; k++) {
				printf("%d ", array[k]);
				if (k == i) printf("\n");
			}
		}
	}
	return 0;
}

三.时间复杂度分析
（1）最好情况：序列原本就是有序的。则比较次数为n-1，时间复杂度为O(N)。
（2）最差情况：序列是逆序的。则比较次数和移动次数均为：1+2+3+4+……+n-1=(n-1)n/2，时间
复杂度为O(N^2)。
（3）平均情况：序列出现各种排列的概率相同，则比较次数和移动次数约为n^2/4，故此时时间复杂
度为O(N^2)。