您现在的位置是:首页 > 编程 > 

【初阶数据结构与算法】八大排序算法之选择排序(直接选择排序、堆排)

2025-07-28 21:00:24
【初阶数据结构与算法】八大排序算法之选择排序(直接选择排序、堆排) 一、单向直接选择排序   选择排序很好理解,就是按照字面意思来,比如我们想要将一个数组排成升序,那么小的值就会被放在前面,我们就可以每次都到数组中的最小值,把它往前面放,循环往复,最终我们就可以将数组排成升序    降序也是如此,就是每次我们都到数组中的最小值,把它往后面放,最后我们就能将数组排成降序,这就是单向直接选择排序

【初阶数据结构与算法】八大排序算法之选择排序(直接选择排序、堆排)

一、单向直接选择排序

   选择排序很好理解,就是按照字面意思来,比如我们想要将一个数组排成升序,那么小的值就会被放在前面,我们就可以每次都到数组中的最小值,把它往前面放,循环往复,最终我们就可以将数组排成升序    降序也是如此,就是每次我们都到数组中的最小值,把它往后面放,最后我们就能将数组排成降序,这就是单向直接选择排序,我们画个简易图理解理解:

   如上图就是使用单向直接选择进行排序的例子,思路很简单,那么有了思路,我们接下来就开始写代码,如下:

代码语言:javascript代码运行次数:0运行复制
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//直接选择排序(单向)
void SelectSort1(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		Swap(&arr[begin], &arr[mini]);
		begin++;
	}
}

我们来使用它排序试试,如图:

   可以看到单向直接选择排序很好地帮我们完成了任务,接下来我们分析一下它的时间复杂度,它拥有两层用于遍历的循环,所以时间复杂度为O(^2),虽然不是很好,但是它的思路很简单    其中单向直接选择排序就是选最小的元素往前或往后放,一次只选一个元素,所以叫单向,那么双向选择排序是什么样子的呢?我们一起来学习一下

二、双向直接选择排序

   单向直接选择排序就是一次只选一个值出来往前或往后放,那么双向选择排序就是,一次把当前最小的和最大的元素的下标出来,把最小的元素往前放,把最大的元素往后放    这样我们是不是一次遍历就可以排好两个元素,而单向的一次遍历只能排好一个元素,相当于是一种优化,那么是不是双向一定比单向快呢?我们在最后的测试阶段给出答案    由于双向直接选择排序和单向直接选择排序很相似,所以我们这里直接就根据上面的思路来写代码了,就是每次最小值往前放,同时最大值往后放,但是其实会有坑,但是先不管,我们先把大思路写出来,后面再分析坑在哪里,如下:

代码语言:javascript代码运行次数:0运行复制
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//直接选择排序(双向)
void SelectSort2(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		Swap(&arr[begin], &arr[mini]);
		Swap(&arr[end], &arr[maxi]);
		begin++, end--;
	}
}

   这里的双向直接选择排序几乎和单向直接选择排序差别不大,那么是否它已经没有问题了呢?我们来看看代码的运行结果:

   可以看到代码出现了一些小问题,没有将数组完全排成升序,那么问题在哪里呢?这里我也不再墨迹了,直接举一个例子画图讲解,如图:

   根据上图我们已经发现了问题,我们来分析一下为什么会出现这种问题,根本原因就是数组中最大值就在begin的位置上,当最小值和begin位置元素进行交换时,把这个最大值交换到mini位置上去了    然后maxi和end位置数据进行交换时,end就拿到了最小值,所以最后导致了上面的问题,根本原因就是最大值在begin的位置上,所以我们想个办法来优化一下    由于begin和mini位置的数据总是先交换,如果begin位置就是最大值的话,经过begin和mini的交换后,这个最大值就会跑到mini的位置上去,所以我们解决的方案就是,如果begin位置就是最大值的话,让maxi = mini    这样的话经过begin和mini的一次交换,将最大值交换到了mini的位置, 现在我们又让maxi走到mini的位置,maxi现在指向的就是最大值,可以放心交换,如图:

现在我们就解决掉这个问题了,我们改正一下我们的代码,如下:

代码语言:javascript代码运行次数:0运行复制
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//直接选择排序(双向)
void SelectSort2(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&arr[begin], &arr[mini]);
		Swap(&arr[end], &arr[maxi]);
		begin++, end--;
	}
}

接下来我们再次来测试一下代码,如图:

   可以看到之前的问题被我们完全解决了,这就是我们真正的双向直接选择排序,接着我们分析一下它的时间复杂度,虽然比起单向的循环少了一半,但是还是属于O(^2)级别,也不算太优,到最后我们再将它们来进行比较,我们继续学习下面的内容

三、堆排

   堆排我在堆的应用部分就已经讲过了,如果有兴趣就去看看原理,这里直接给出源代码,如下:

代码语言:javascript代码运行次数:0运行复制
//向上调整算法
void AdjustUp(int* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//向下调整算法
void AdjustDown(int* arr, int parent, int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] > arr[child])
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//堆排
void HeapSort(int* arr, int n)
{
	//向上调整建堆
	/*for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}*/
	
	//向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}

	//建堆后进行排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}

   我们之前在堆的应用也讲过堆排的时间复杂度,这里再提一下,大致为O(l * log),这个时间复杂度非常优秀,在最后我们进行对比时也可以看出来

四、直接选择排序以及堆排性能对比

   我们还是按照上一篇文章的样子来写一个专门测试排序性能的函数,它可以帮我们生成10万个随机数,如下:

代码语言:javascript代码运行次数:0运行复制
void TestOP()
{
    srand((unsigned int)time(ULL));
    ct int  = 100000;
    int* a1 = (int*)malloc(sizeof(int) * );
    int* a2 = (int*)malloc(sizeof(int) * );
    int* a = (int*)malloc(sizeof(int) * );

    for (int i = 0; i < ; ++i)
    {
        a1[i] = rand();
        a2[i] = a1[i];
        a[i] = a1[i];
    }
     int begin1 = clock();
     SelectSort1(a1, );
     int end1 = clock();

     int begin2 = clock();
     SelectSort2(a2, );
     int end2 = clock();

    int begin = clock();
    HeapSort(a, );
    int end = clock();

    printf("SelectSort1(单向):%d\n", end1 - begin1);
    printf("SelectSort2(双向):%d\n", end2 - begin2);
    printf("HeapSort:%d\n", end - begin);

    free(a1);
    free(a2);
    free(a);
}

int main()
{
    TestOP();
    return 0;
}

   注意我们在运行这段代码之前,要把模式改成Release,这样才能真正测试它们的性能,运行结果如下:

   可以看到,我们排10万个随机数,堆排只用了5毫秒,而单向和双向直接选择排序则直接来到了4秒左右,我们再来测试一下排序100万个随机数的时间,如图:

   可以发现,堆排的速度依旧非常非常快,仍然在0.1秒之内,而两个直接选择排序则是慢了非常多,已经以分钟来计数了,这就是O( * log )的力量    当我们比较完堆排和直接选择排序之后,我们来比较一下单向和双向两个直接选择排序,我们惊讶地发现,单向的直接选择排序居然更快,理论上来说,双向是单向的优化,循环次数更少,为什么还会出现这种问题呢?    大致原因应该是单向选择排序它的交换逻辑和条件判断更简单,编译器在编译代码时,就做了更多和更好的优化,导致单向比双向快,但是我们要知道理论上双向是单向的优化

   那么到这里我们选择排序就到这里介绍完毕了    bye~

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。 原始发表:2024-12-20,如有侵权请联系 cloudcommunity@tencent 删除int排序排序算法数据结构与算法数组

#感谢您对电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格的认可,转载请说明来源于"电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格

本文地址:http://www.dnpztj.cn/biancheng/1239995.html

相关标签:无
上传时间: 2025-07-26 23:18:52
留言与评论(共有 17 条评论)
本站网友 mios
15分钟前 发表
而两个直接选择排序则是慢了非常多
本站网友 哈尔滨新房出售
15分钟前 发表
将最大值交换到了mini的位置
本站网友 姜枣茶什么人不能喝
15分钟前 发表
这个最大值就会跑到mini的位置上去
本站网友 搜房网成都租房
26分钟前 发表
int n) { int begin = 0
本站网友 pasteurized
28分钟前 发表
仍然在0.1秒之内
本站网友 渣滓
2分钟前 发表
当最小值和begin位置元素进行交换时
本站网友 底商
7分钟前 发表
思路很简单
本站网友 梅陇二手房
11分钟前 发表
我们来分析一下为什么会出现这种问题
本站网友 北理人
13分钟前 发表
导致单向比双向快
本站网友 fieldset
4分钟前 发表
所以我们解决的方案就是
本站网友 婚庆公司装修
18分钟前 发表
编译器在编译代码时
本站网友 新浪评论
16分钟前 发表
但是其实会有坑
本站网友 商贷还款计算器
11分钟前 发表
分享自作者个人站点/博客
本站网友 捞金子
19分钟前 发表
&arr[end]); AdjustDown(arr
本站网友 罗湖租房信息
30分钟前 发表
将最大值交换到了mini的位置
本站网友 儿童催眠曲
13分钟前 发表
我们改正一下我们的代码