由于考试耽搁了几天，不好意思~~~

前面的介绍的三种排序算法，都属于简单排序，大家能够看下详细算法，时间复杂度基本都在0(n^2)，这样呢，非常多计算机界、数学界的牛人就非常不爽了，他们在家里想啊想，吃饭的时候在想，窝粑粑的时候也在想，到底能不能把时间复杂度搞低点呢。最终，皇天不负有心人啊，王母娘娘显灵了，最终被DL. SHELL这哥们给想出来了。他所创造的希尔（shell）排序是世界上第一个打破0(n^2)的时间复杂度的算法。牛逼不？

好了，言归正传。

希尔排序：

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本号。希尔排序是非稳定排序算法。



希尔排序是基于插入排序的下面两点性质而提出改进方法的：

(1) 插入排序在对差点儿已经排好序的数据操作时， 效率高， 即能够达到线性排序的效率

(2) 但插入排序一般来说是低效的， 由于插入排序每次仅仅能将数据移动一位

源码：

#include "stdafx.h"

#include <stdlib.h>

void Shell_Sort()

{

	int arr[10];

	for ( int i=0; i<10; i++)  //初始化数据

	{

		arr[i] = rand()%123;  //随机生成数据

	}

	printf("Before sort:\n");  //打印排序前的数据

	for (int i = 0; i < 10; i++)

	{

		printf("%d ",arr[i]);

	}

	//開始排序

	int k = 0;

	int gap = 10;

	int temp = 0 ; //记录要插入的数据

	do

	{

		gap = (gap / 3) + 1; //假定间隔为3，（3能够为其它数字）

		for (int i = gap; i < 10; i+=gap) //从第二个一直比到最后一个元素,每次跳gap个间距

		{

			k = i;

			temp = arr[k];

			for (int j = i-gap; (j>=0)&&(arr[j] > temp); j-=gap)//从要插入的元素的上一个元素開始,一直往前，每次跳																			//gap个元素直到要插入的元素遇到不比它大的																			//元素为止

			{

				arr[j+gap] = arr[j];

				k = j; //k的位置就是要插入的位置

			}

			arr[k]  = temp; //将要插入的元素插到k的位置

		}

	}while(gap > 1);

	printf("\nAfter sort:\n"); //打印排序后的数据

	for (int i = 0; i < 10; i++)

	{

		printf("%d ",arr[i]);

	}

}

int _tmain(int argc, _TCHAR* argv[])

{

	Shell_Sort();

	printf("\n");

	system("pause");

	return 0;

}

执行结果：

Before sort:

41 17 61 55 104 103 39 84 25 110

After sort:

17 25 39 41 55 61 84 103 104 110

请按随意键继续. . .

如有错误，望不吝指出。