排序算法——直接插入排序+希尔排序

直接插入排序

基本思想：将一个记录插入到已经排好的有序序列中，得到一个增1的新数列。

时间复杂度为：O（n^2）.

代码实现：

void fun(int a[], int N)
{
	int i, j temp;
	for (i = 1; i < N; i++)
	{
		temp = a[i];
		for (j = i; j > 0 && a[j - 1] > temp; j--)
		{
			a[j] = a[j - 1];
		}
		a[j] = temp;
	}
}
           

希尔排序

基本思想： 先将整个待排序的元素序列分割成若干个子序列（由相隔某个“增量”的元素组成）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（增量为1）。

时间复杂度： O(N^3/2)

代码实现：

void fun(int *a, int N)
{
	int i , j, x;
	int temp;
	for(x = N/2; x > 0; x = x/2)
	{
		for(i = x; i < N; i++)
		{
			temp = a[i];
			for(j = i; j >=x; j = j - x)
			{
				if(a[j- x] > temp)
					a[j] = a[j - x];
				else
					break;
		    }
		    a[j] = temp;
	   }
	}
}