插入排序和希爾(Shell)排序

【插入排序】

數組前k-1個元素已經有序，如何確定第k個元素的插入位置，使得這k個元素有序。

方法1：從左到右掃描掃描這個有序子數組，直到遇到第一個大於等於A[k]的元素，然後把A[k]插在這個元素的前面。

方法2：從右到左掃描這個有序子數組，直到遇到第一個小於等於A[k]的元素，然後把A[k]插在這個元素的後面。

【希爾排序】

先將數組分組，分別對每組進行插入排序，依次減少分組數進行插入排序，最後對分組數為1，即對整個數組進行插入排序。

【代碼】

#include 
#include 

void InsertionSort(int a[], int n)
{
	int i, j;
	int tmp;
	for(i = 1; i < n; i++)//方法2的插入方式
	{
		tmp = a[i];
		j = i - 1;
		while ( j >= 0 && a[j] > tmp)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = tmp;
	}
}

void ShellSort(int a[], int n)
{
	int step;
	int i, j, k;
	int tmp;
	for(step = n / 2; step > 0; step /= 2)  //不同步長的分組
		for(k = 0; k < step; k ++)  //總共分成step組
			for(i = k + step; i < n; i+=step) //對每組進行插入排序
			{
				tmp = a[i];
				j = i - step;
				while(j >= 0 && a[j] > tmp)
				{
					a[j + step] = a[j];
					j = j - step;
				}
				a[j + step] =tmp;
			}
}

int main(void)
{
	int a[7] = {5, 7, 3, 0, 4, 9, 8 };
	int n = sizeof(a)/sizeof(int);
	InsertionSort(a, n);
    ShellSort(a, n);
	for(int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
	return 0;
}