插入排序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),性能比冒泡排序和简单选择排序要好一些。