插入排序C语言板

直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表。顾名思义，从名称上也可以知道它是一种插入排序的方法。我们来直接插入排序方法的代码。

	void InsertSort(SqList *L) {
		int i,j;
		for (int i = 2; i <= L->length; i++) {
			if (L->r[i]r[i-1]) { // 需要把L->r[i] 插入有序子表
				L->r[0] = L->r[i];   // 设置哨兵
				for(j=i-1;L->r[j];L->r[j]>L->r[0];j--) {
					L->r[j+1] = L->r[j]; // 记录后移
				}
				L->r[j+1] = L->r[0]; // 插入到正确位置
			}
		}
	}

我们来分析一下这个算法，从空间上来看，它只需要一个记录的辅助空间，因此关键是看它的时间复杂度。最好的情况排序表本身就是有序的，只需要比较 L.r[i] 与 L.r[i-1] ,由于没有记录移动，时间复杂度为O(n)。最坏的情况是逆序的情况共（n + 2）（n - 1）/ 2 次。有随机和概率相同原则比较和移动次数约为 n^2 / 2 ,因此时间复杂度为O(n^2),性能比冒泡排序和简单选择排序要好一些。