希尔排序-插入排序

个人主页点了解这里~

---

了解希尔排序我们首先需要知道他的前身插入排序

---

1.插入排序

过程:从下标为0开始遍历数组到数组倒数第二个元素

从第一个元素开始,记录他右边相邻位置的值

然后与左边的值依次比较大小,(排顺序)若记录的值比左边小,则交换位置(值)

若相等或大则不交换直接退出循环

注意:为什么只需要遍历到倒数第二个元素,因为我们需要进行比较的是遍历到的元素的下一位值,

所以如果一直遍历到最后,后面会出现越界问题

// 插入排序
void InsertSort(int* a, int n)//n元素个数
{
	for (int i = 0; i < n - 1; i++)//注意n-1
	{
		int end = i;
		int tmp = a[end + 1];//记录比较值
		while (end >= 0)//循环比较
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
			a[end + 1] = tmp;//最后移出的空位赋值给记录值tmp
		}
	}
}

时间复杂度属于O(n*n)

---

2.对于插入排序我们还有什么地方可以优化(希尔排序解决)

问题:我们可以发现当一个数组数据大小顺序已经不错的时候while循环不需要很多次直接跳出来了,

来看极端情况arr[]={0,1,2,3,4,5,6,7,8,9},此时只需要遍历一遍数组时间复杂度达到了O(N)

我们再来看看极端情况一个数组arr[]={9,8,7,6,5,4,3,2,1,0},属于完全逆序的情况,这样在while循环中每一次比较都不会落下,这就会导致时间复杂度很大

结论:我们可以得知插入排序的特点:在数组元素的排序情况导致时间复杂度的极端

---

3.希尔排序

如何解决以上问题:比如我们这里有一个10个元素的数组

1.我们可以给一个变量gap(希尔排序的间隔（Gap）是希尔排序算法中的一个关键概念)

1. 间隔gap的作用：

间隔用于将数组分成若干个子组，每个子组内的元素间隔为当前设定的间隔值。例如，当间隔为3时，数组中的元素将按照索引0、3、6...等分成若干组。

在每个子组内，使用直接插入排序进行排序。这样，通过比较相隔较远距离的元素，可2以使得数在移动时能跨过多个元素，从而加速排序过程。

---

通过设计gap这一个变量,我们可以渐渐把无序的数组变成一个无限接近有序的数组,此时我们再来一次插入排序,就变得很简单了

---

总结:  希尔排序:

             1.预排序

             2.插入排序

预排序:gap相对数组个数越大,大的数可以越快跳到后面,但是越不接近有序

            gap相对数组个数越小,就越慢,就越接近有序(当gap==1时,就是一次插入排序)

---

// 希尔排序
void ShellSort(int* a, int n)
{
	int gap = 3;//先假设gap为3
	for (int j = 0; j < gap; j++)//gap组依次排序
	{
		for (int i = j; i < n - gap; i += gap)
		{//一次排序,注意i<n-gap与上面插入排序越界一个问题
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
				a[end + gap] = tmp;
			}
		}
	}
}

我们观察发现预排序和插入排序十分相似,就是gap==1时就是插入排序

我们优化一下代码

void ShellSort(int* a, int n)
{
	int gap = 3;//先假设gap为3
	for (int i = 0; i < n - gap; i++)
	{
		//一次次排序,因为gap分组的元素互不影响,所以可以依次调整
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
			a[end + gap] = tmp;
		}
	}
}

---

我们再来看看gap的取值问题:

gap相对数组个数越大,大的数可以越快跳到后面,但是越不接近有序

gap相对数组个数越小,就越慢,就越接近有序(当gap==1时,就是一次插入排序)

按照前人的分析比较,取数组元素个数除以3时,效率是最高的

// 希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//              +1避免gap为0
		//for (int j = 0; j < gap; j++)
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
				a[end + gap] = tmp;
			}
		}
	}
}

---

分享到这里,若有疑问,可以在评论区,请各位大神讨论~

个人主页点这里~