数据结构排序部分整理

重复执行n-1趟。

当待排序序列逆序时，时间复杂度最差：每趟比较并移动i（1~n-1）个元素，进行n-1趟，1+2+…+n-1=n(n-1)/2。

当待排序序列基本有序时，时间复杂度最小为O(n)：每趟只需要比较1次，共进行n-1趟，1+1+…+1=n-1。

插入排序是在原有数组的基础上进行的，排序所需要新增的空间与待排序序列的元素个数无关。

#include
int main() {
	int i,j, t, arr[10] = {21,45,76,68,54,89,94,14,37,5};
	for (i = 1; i < 10; i++) {
		t = arr[i];
		j = i - 1;
		while (j >= 0 && arr[j] > t) {
			arr[j + 1] = arr[j--];
		}
		arr[j + 1] =t;
	}

	for (i = 0; i < 10; i++) {
		printf("%d ", arr[i]);
	}

	return 0;
}