八大排序算法-希尔排序

谁借莪１个温暖的怀抱￠ 2022-06-07 08:13 120阅读 0赞

希尔的定义：希尔排序是插入算法的一种，也叫缩小增量排序。是直接插入排序算法的一种改良版。

希尔算法是把数据序列按下标的一定增量分组，对每组使用直接插入排序算法进行排序；然后依次缩减增量再进行排序，待整个序列中的元素基本（注：没有全部完成排序）有序时，再对全体元素进行一次直接插入排序。

基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所以距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后取第二个增量d2<d1重复上述的分组和排序，直至所取的

增量 ![3c6d55fbb2fb4316e40ee40423a4462309f7d3bf.jpg][]

=1(

![32fa828ba61ea8d3f96aea7a940a304e251f5807.jpg][]

![80cb39dbb6fd5266feaea26aa818972bd50736c2.jpg][]

…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

时间复杂度为：最大O(n^2)，最小O(n\*log2n)。

实例：

int arr[] = { 35, 28, 58, 10, 61, 58, 97, 17 };
    int k = sizeof(arr) / sizeof(arr[0]);
    
    //根据当前增量进行插入排序
    void shellInsert(int array[], int n, int dk)
    {
    	int i, j, temp;
    	for (i = dk; i<n; i++)//分别向每组的有序区域插入
    	{
    		temp = array[i];
    		for (j = i - dk; (j >= i%dk) && array[j]>temp; j -= dk)//比较与记录后移同时进行
    			array[j + dk] = array[j];
    		if (j != i - dk)
    			array[j + dk] = temp;//插入
    	}
    }
    
    //希尔排序
    void shellSort(int array[], int n, int t)
    {
    	int i;
    	while(t >= 1)
    	{
    		shellInsert(array, n, t);
    		t = t / 2;
    	}
    
    	for (int f = 0; f < n; f++)
    	{
    		std::cout << array[f] << "  ";
    	}
    }

[3c6d55fbb2fb4316e40ee40423a4462309f7d3bf.jpg]: https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D16/sign=5b37a5ba18d5ad6eaef960ec81cb742d/3c6d55fbb2fb4316e40ee40423a4462309f7d3bf.jpg
[32fa828ba61ea8d3f96aea7a940a304e251f5807.jpg]: https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D16/sign=dd8c7c646359252da7171902359bf9f4/32fa828ba61ea8d3f96aea7a940a304e251f5807.jpg
[80cb39dbb6fd5266feaea26aa818972bd50736c2.jpg]: https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D28/sign=5261265e02e9390152028a367aec2ebf/80cb39dbb6fd5266feaea26aa818972bd50736c2.jpg