一起学习交流~

排序-06-希尔排序

算法 laomuji 12个月前 (10-10) 486次浏览 已收录 1个评论

一、什么是希尔排序

首先上百度百科

下面说下我自己的理解

希尔排序 直接插入排序算法的一种更高效的改进版本,可以非常有效的减少数据交换次数 希尔排序是非稳定排序算法
实现起来比较容易,时间复杂度最好为nlog2n,最坏为O(n^2),时间复杂度范围:O(n^(1.3—2))
希尔排序在数据量为百万级时使用比较好,因为实现起来简单,速度也比较快,但是千万级别的数据还是用快排之类的

二、希尔排序原理

步长首先是数组的一半 然后每次/2 这里方便理解 每次-1,实际上应该每次/2
5,6,8,4,3,1,2,7,9,10
5 1 比较并交换 1 5
6 2 比较并交换 2 6
8 7 比较并交换 7 8
4 9 比较并交换 4 9
3 10 比较并交换 3 10
合并数据
1 2 7 4 3 5 6 8 9 10
步长-1
1 3 9 比较并交换 1 3 9
2 5 10 比较并交换 2 5 10
7 6 比较并交换 6 7
4 8 比较并交换 4 8
合并数据
1 2 6 4 3 5 7 8 9 10
步长-1
1 4 7 10 比较并交换 1 4 7 10
2 3 8 比较并交换 2 3 8
6 5 9 比较并交换 5 6 9
合并数据
1 2 5 4 3 6 7 8 9 10
步长-1
1 5 3 7 9 比较并交换 1 3 5 7 9

2 4 6 8 10 比较并交换 2 4 6 8 10
合并数据
1 2 3 4 5 6 7 8 9 10
步长-1
1 2 3 4 5 6 7 8 9 10 比较并交换 1 2 3 4 5 6 7 8 9 10

三、希尔排序代码

//希尔排序属于插入排序的变种
void shellSort(int nums[], int length)
{
	int gap = length / 2;//步长,间隔
	while (gap > 0)//如果步长不为0 就进行操作
	{
		for (int i = 0; i < gap; i++)//分组
		{
			//插入排序的变种
			//从第2个位置开始
			//每次交换确保前面的值都是比自己小的值
			//首先是位置2和1,先保存2的值,若1比保存的值大,把1的值复制到2,然后再把保存的值放到1,此时1<2
			//然后3和2和1,先保存3的值
			//若2比保存的值大,把2的值复制到3,然后保存的值再和1比较,若1比保存的值大,把1的值复制给2,然后再把保存的值放到1,此时1<2<3,经过了2次交换
			//若2比保存的值小,那么无需再往前比较,因为前面一定是1<2的,把保存的值复制到3(实际上没有变),此时1<2<3,经过了1次交换
			for (int j = i + gap; j < length; j += gap)
			{
				int temp = nums[j]; //保存当前位置的值
				int k = j - gap;//前一个值
				//如果前面有值 而且前一个值比最大值大
				while (k >= 0 && nums[k] > temp)
				{
					//把前面的值放到后面一个
					nums[j] = nums[k];
					//继续往前找
					k -= gap;
				}
				//当前面所有的值都比较过了或者没有找到比自己小的值了
				//就把
				nums[k + gap] = temp;
			}

		}
		//方便理解可以用-1 查看步骤 但是速度会慢很多
		gap /= 2;//最好还是/2
	}
}
喜欢 (0)
订阅评论
提醒
guest
1 评论
最旧
最新 最多投票
内联反馈
查看所有评论
姜世启
姜世启
11 月 前

‘or”=’