数据结构(初阶)—— 排序算法(上)

数据结构(初阶)—— 排序算法(上),第1张

目录

前言

一、直接插入排序

1.动图演示

2.代码实现 

二、希尔排序 

1.希尔大佬来告诉你他是怎么想的?

2.如何实现单趟的分组预排(含动态演示)

3. 多组预排序的方法(含动态演示)

方法1

方法2

代码实现

4. 希尔排序实现

三、选择排序 

思路1

思路2

四、堆排序 


前言

        排序在我们日常生活中很常见,如:打扑克牌、商品的销量、价格、好评度等都需要用到排序;排序目的在于让我们跟容易对事物一目了然;所以掌握好排序也是非常有必要的;接下来我们介绍排序算法的前两个:插入排序和选择排序;

一、直接插入排序

什么是直接插入排序? 

        相信大家都完过扑克牌,摸得一手好牌(如果全是炸d^-^)牌堪比人上人呀;我们从开始摸第一张牌起其后摸得所有牌,都需要插入到相应的位置,让自己手中的牌按升序或降序的排列方式组合起来;

1.动图演示

对于一个随机组合的数组[ 6, 2, 10, 3, 9, 4, 8, 5, 1, 7 ] ,我们如何利用直接插入排序,将其排列成升序或降序的排列方式呢?

 看过了动图,那么如何 *** 作实现呢?

2.代码实现 
// 插入排序
void InsertSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; i++)
	{
		//将x插入【0,end】有序区间
		int end = i;
		int x = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > x)
			{
				a[end + 1] = a[end];//将前一个数向后挪动
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = x;
	}
}
二、希尔排序 

        希尔排序,顾名思义就是有一个叫希尔的大佬想出的排序算法;也被称为"缩小增量排序"它的本质还是插入排序,是在直接插入排序算法的基础上进行改进;他是如何一步一步改进的呢?

1.希尔大佬来告诉你他是怎么想的?

2.如何实现单趟的分组预排(含动态演示)

我们以间距(gap)为3为例;来对这10个数据进行第一组的与排序; 

从上面的动图可以看出,本质思想还是直接插入;

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

3. 多组预排序的方法(含动态演示) 方法1:

在单趟与排序的基础上外面套一层循环,一共gap组,那就循环gap次;

动图演示:

方法2:

在方法1的基础上做了一些改进,它不再是先排完第一组再排第二组,再排第三组;它让三组同时开始预排;

动图演示: 

上述两种方法都是不错的,方法2并没有质的提升,但是在量上略微提升了一些;

代码实现
// 希尔排序
void ShellSort(int* a, int n)
{ 
	//多组一锅炖1
	int gap = 3;
	for (int j = 0; j < gap; j++)
	{
		for (int i = 0; i < n - gap; i+=gap)
		{
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = x;
		}
	}
	//多组一锅炖2
    int gap = 3;
	for (int i = 0; i < n - gap; ++i)
	{
		int end = i;
		int x = a[end + gap];
		while (end >= 0)
		{
			if (a[end] < x)
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = x;
	}
}
4. 希尔排序实现

        从本段第一点的介绍,希尔大佬提出先将数组以间距为3分为3组数据进行预排,再以间距为2将数组分为2组进行预排;最后再以间距为1(即直接插入排序)进行最后的一次排序;达到升序或降序的排列组合; 

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

阅读本段至此,我们可以发现一些问题? 

1.gap越大,预排越快,预排后越不接近有序;

        间距越大,意味着越小的数字能够很快的跳的前面来,越大的数字能很快的跳到后面去;虽然预排比较快,但是整体看不出来有序;
2.gap越小,预排越慢,预排后越接近有序;

        间距越小,意味着它每部分的数据都接近于有序,整体相对有序,但是预排相对比较慢;
3.gap == 1 ,就是直接插入排序;

        当间距在发生变化时,不断进行预排,每次都在向有序靠近,知道最后间距变化为1时,就能将整个数组排列完成;

一般gap是如何确定呢?

        起初,希尔大佬认为gap=n/2、gap=gap/2直到gap=1;后来Knuth提出取gap=gap/3+1.还有人认为取奇数为好,也有人提出取gap互质为好。无论哪一种主张都没有得到证明;小伙伴就可以以 gap=gap/2gap=gap/3+1 来取;需要强调的是 gap=gap/3+1

这里为什么需要加1呢?当有N个数据时且N为偶数时,除到最后是,gap就为0了,我们需要最后一次达到gap=1,去进行直接插入排序,所以这里加1的目的就在于此;

三、选择排序  思路1:

        每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的 数据元素排完 。

//选择排序1
void SelectSort(int* a, int n)
{
	int begin = 0;
	while (begin < n - 1)
	{
		int min = begin;
		for (int i = begin; i <= n - 1; i++)
		{
			if (a[i] < a[min])
			{
				min = i;//找最小值的下标
			}
		}
		Swap(&a[begin], &a[min]);
		++begin;
	}
}
思路2:
        思路1是每次选一个较小数(以升序为例)放到左边,直到全部排序完成;思路二的思想就是一次选两个数,小的放左边,大的放右边;

 注意点:

如何解决呢?

此时最大值被换走了,我们可以修正一下max和min的位置;

// 选择排序2
void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;//找最小值的下标
			}
			if (a[i] > a[maxi])
			{
				maxi = i;//找最大值的下标
			}
		}
		Swap(&a[begin], &a[mini]);
		//begin == maxi时,最大值被换走了,修正一下maxi的位置
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}
四、堆排序 
        堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排 升序要建大堆 ,排 降序建小堆 向下调整算法:   堆排序:

如果对堆的应用还不清楚的小伙伴可以去看这里:

链接:https://blog.csdn.net/sjsjnsjnn/article/details/124201028?spm=1001.2014.3001.5501 

//向下调整函数(大堆(升序)用大于,小堆(降序)用小于)
void AdjustDown(int* a, int n, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < n)
	{
		//选出左右孩子中小的那个
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}

		//如果小的孩子小于父亲,则交换,并继续向下调整
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 堆排序
void HeapSort(int* a, int n)
{
	//倒着建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	//O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/719531.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-25
下一篇 2022-04-25

发表评论

登录后才能评论

评论列表(0条)

保存