排序嘉年华———希尔排序

2023-12-20 06:31:25

一.排序基础,插入排序。

1.什么是插入排序?
插入排序是一种简单直观的排序算法,其步骤如下:

1. 从第一个元素开始,该元素可以认为已经被排序。
2. 取出下一个元素,在已经排序的元素序列中从后向前扫描。
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置。
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5,直到整个数组排序完成。

这样,数组的每个元素都会被插入到已排序的数组中,直到整个数组都被排序完成。

在这里插入图片描述

void Insertsort(int* a, int n)
{

	for (int i = 0; i < n - 1; i++)
	{
		int end=i;
		int tmp = a[end + 1];//保存end+1
		while(end>=0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

for循环内,可理解为排序的一个单趟,将要比较位置存储到tmp中,在将tmp前一个值a[end]不断后移,直到找到合适的地方停止,将tmp放下。就像扑克牌插牌一样,每一个单趟检索一次

void test1()
{
	int a[10] = { 9,8,7,6,5,4,3,2,1,0 };
	/*Bubblesort(a, 10);
	Printarr(a, 10);*/
	Insertsort(a, 10);
	Printarr(a, 10);
	/*Shellsort(a, 10);
	Printarr(a, 10);*/
}

在这里插入图片描述

二.希尔排序

1.希尔排序的预排序

1.一组预排序

1.选择一个增量序列,例如使用希尔提出的增量序列(1, 4, 10, 23, ...)或者其他增量序列。

2.根据选定的增量序列,将数组分成若干个子序列,每个子序列的元素间隔为增量序列中的一个数。

3.对每个子序列进行插入排序,即将子序列中的元素按照插入排序的方式进行排序。

4.逐渐缩小增量序列的间隔,重复步骤2和步骤3,直到增量序列的间隔为1,此时整个数组成为一个子序列,再进行一次插入排序。

为了在处理大量数据时,我们可以通过分组,设置gap间隔,使得靠后的位置的值快速比较从而提到前方。
假设有10个数,我们规定gap为3,进行一次处理,如下,将红色箭头所指位置进行调整
在这里插入图片描述

int gap=3;
	for (int i = 0; i < n - gap; i += gap)
	{
		int end=i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = tmp;
	}

通过gap快速打破,这种极端,接近有序
在这里插入图片描述

2.n/gap组预排序

将i+=gap改成i++

for (int i = 0; i < n - gap; i++)

这样就完成了全部预排,使数组接近有序
在这里插入图片描述
在这里插入图片描述
如果再加上,一组插入排序,便可完成有序状态
那么问题来了?为什么不直接排序呢,因为预排序可以大大降低时间复杂度,毕竟连做饭都需要加工食材,没有谁一上来直接起锅烧油的。

2.希尔排序的优化

上面预排序讲的代码是为了方便大家理解,而真正实践上我们需要将预排序与最终排序结合起来,而且要形成有层次的预排序。
gap不能是一个固定值,需要富有变化

根据大多数人和查阅资料可知gap=n/3+1,为一个比较优势的值,通过不断变化,使gap=1,完成排序
void Shellsort(int* a, int n)
{
	int gap = n ;
	while (gap > 1)
	{
		 gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

这里gap不是标准值,或者说没有标准,任何能使gap为1的式子都可以只不过,gap=gap/3+1更优一些

3.希尔排序的强势之处

我们设计一个测试函数100000个随机值数组进行排序,统计其时间长短

void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	

	for (int i = 0; i < N; i++)
	{
		a1[i] = rand();
		a2[i] = rand();
		a3[i] = rand();
		

	}
	int begin1 = clock();
	Insertsort(a1, N);
	int end1 = clock();
	int begin2 = clock();
	Bubblesort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	Shellsort(a3, N);
	int end3 = clock();

	printf("Insertsort:%d\n", end1 - begin1);
	printf("Bubblesort:%d\n", end2 - begin2);
	printf("Shellsort:%d\n", end3 - begin3);

	free(a1);
	free(a2);
	free(a3);
	
}

利用clock函数计算排序所用时间
在这里插入图片描述
如图所示,在vs的release版本下,插入排序,冒泡排序,希尔排序的时间长短
希尔排序完胜
在这里插入图片描述

感谢各位阅读,记得点赞订阅,后面会推出更多优质作品。

文章来源:https://blog.csdn.net/2301_79181624/article/details/134896719
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。