插入排序

根据王道书上的代码，结合自己的理解，写的插入排序的代码，分为直接插入排序和希尔排序两个。

直接插入排序

直接插入排序的思想是将每一个元素插入到已经有序的序列中，使其仍然保持有序。在实际代码处理的时候，胸第二个元素开始处理，将前面的序列看成有序，实现原地排序的效果。

直接插入排序的空间复杂度为O(1)，且为稳定的排序算法。

直接插入排序的最好时间复杂度为O(n)，最坏时间复杂度为O(n^{2)，平均时间复杂度为O(n}2)

# include <stdio.h>
# include <stdlib.h>
# include <time.h>
 
# define LENGTH 10
 
void CreateList(int * data, int len)
{
	int i = 0;
	srand(time(NULL));
	for (i=0; i<len; i++) {
		data[i] = rand() % 100;
	}
	return;
}
 
void PrintList(int * data, int len)
{
	int i = 0;
	for (i=0; i<len; i++) {
		printf("%d ", data[i]);
	}
	printf("\n");
	return;
}
 
// 直接插入排序
void InsertSort(int * data /* 待处理的数据 */, int len /* 数据的长度 */)
{
	int i = 0;
	for (i=1; i<len; i++) {							// 从第二个数据开始处理
		int j = i - 1;
		if (data[i] < data[i - 1]) {				// 如果前面的序列存在比当前数值大的数
			int temp = data[i];
			while (j >= 0 && data[j] > temp) {		// 一路往前把大的数向后移
				data[j + 1] = data[j];
				j--;
			}
			data[j + 1] = temp;
		}
		printf("%2d th sort: ", i);
		PrintList(data, len);
	}
	return;
}
 
int main(void)
{
	int * data = (int *)malloc(sizeof(int) * LENGTH);
	CreateList(data, LENGTH);
 
	printf("Before sort: ");
	PrintList(data, LENGTH);
	InsertSort(data, LENGTH);
	printf("After sort: ");
	PrintList(data, LENGTH);
	
	return 0;
}

希尔排序

希尔排序是直接插入排序的一种优化。其核心思想为：

• 将间隔为d的元素取出来看成一个新的子序列
• 对子序列进行直接插入排序，这样会使得原序列相对有序
• 不断缩小d的值，直到d等于1，此时希尔排序退化为直接插入排序

因为希尔排序每一次的排序都是建立在之前相对有序的基础上，所以能相对提高效率。

直接插入排序的空间复杂度为O(1)，且为不稳定的排序算法。

在增量序列函数选取合适的前提下，希尔排序的时间复杂度为O(n^{1.3)，最坏情况下的时间复杂度为O（n}2）。

# include <stdio.h>
# include <stdlib.h>
# include <time.h>
 
# define LENGTH 15
 
void CreateList(int * data, int len)
{
	int i = 0;
	srand(time(NULL));
	for (i=0; i<len; i++) {
		data[i] = rand() % 100;
	}
	return;
}
 
void PrintList(int * data, int len)
{
	int i = 0;
	for (i=0; i<len; i++) {
		printf("%d ", data[i]);
	}
	printf("\n");
	return;
}
 
// 希尔排序
void ShellSort(int * data, int len)
{
	int d = 0;
	int i = 0;
	for (d=len/2; d>=1; d/=2) {			// 设置步长，初始值为元素个数的一半，最后的值为1
		for (i=d; i<len; i++) {			// 在规定的步长内对元素进行直接插入排序
			if (data[i] < data[i - d]) {
				int temp = data[i];
				int j = i - d;
				while (j >= 0 && data[j] > temp) {
					data[j + d] = data[j];
					j = j - d;
				}
				data[j + d] = temp;
			}
		}
		printf("d = %d: ", d);
		PrintList(data, len);
	}
	
	return;
}
 
int main(void)
{
	int * data = (int *)malloc(sizeof(int) * LENGTH);
	CreateList(data, LENGTH);
 
	printf("Before sort: ");
	PrintList(data, LENGTH);
	ShellSort(data, LENGTH);
	printf("After sort: ");
	PrintList(data, LENGTH);
	
	return 0;
}