元旦特辑：Note6---选择排序

2023-12-31 02:52
文章标签 选择 排序 特辑 元旦 note6

本文主要是介绍元旦特辑：Note6---选择排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

前言❌

1. 基本思想⚠️

2. 直接选择排序🟢

2.1 思路分析✳️

2.2 代码实现❎

2.2.1 sort.h

2.2.2 sort.c

2.2.3 test.c

2.3 问题解决❇️

2.3.1 sort.c修改

2.4 特性总结✅

3. 堆排序🔵

3.1 代码实现🏧

3.2 特性总结🛜

4. 选择排序和插入排序性能对比🅿️

后语⭕️

前言❌

Hey young fella! Welcome to my channel!  前面一篇博客，我们学习了插入排序的2种实现方法。今天也是类似的，今天我们将一起学习选择排序的2种实现：直接选择排序+堆排序。

1. 基本思想⚠️

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

2. 直接选择排序🟢

2.1 思路分析✳️

目标：实现升序

思路：暴力选取

把数据遍历一遍，依次将最大（小）的，次大（小）的，次次大（小）的放到对应的前三位（每次选取都要遍历一遍），然后重复上述步骤，直到最后就剩下1个数据


当然，我们也可以优化一下：
第一次遍历选出最大的和最小的放到头和尾的位置
第二次遍历选出次大的和次小的放到头+1和尾-1的位置
......

2.2 代码实现❎

2.2.1 sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>//打印
void PrintArray(int* a, int n);
//直接插入排序
void SelectSort(int* a, int n);

2.2.2 sort.c

#include"sort.h"
//打印
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++)printf("%d ", a[i]);printf("\n");
}//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//直接插入排序
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1,i;while (begin < end){int min = begin, max = begin;//一次排2个min和maxfor (i = begin + 1; i <=end; i++){if (a[i] < a[min])min = i;if (a[i] > a[max])max = i;}Swap(&a[begin], &a[min]);Swap(&a[end], &a[max]);begin++;end--;}
}

2.2.3 test.c

#include"sort.h"
//直接插入排序
void testSelectSort()
{int a[] = { 3,2,6,8,9,7,5,10,1,4 };int n = sizeof(a) / sizeof(int);SelectSort(a, n);PrintArray(a, n);
}
int main()
{testSelectSort();return 0;
}

2.3 问题解决❇️

我们发现，排序结果怎么有点不对呢？5，6的顺序怎么反了？

通过调试，我们发现最后一次排序的时候，交换那里出现了问题：max和begin位置重合了
min和begin交换完之后，排序是正确的；但是，end和max又交换了一次，导致顺序出错

所以，我们需要判断一下max和begin是否重合，重合了就不交换max和end；没重合就交换

2.3.1 sort.c修改

//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//直接插入排序
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1,i;while (begin < end){int min = begin, max = begin;//一次排2个min和maxfor (i = begin + 1; i <=end; i++){if (a[i] < a[min])min = i;if (a[i] > a[max])max = i;}Swap(&a[begin], &a[min]);//判断max和begin位置是否重合if (begin != max)Swap(&a[end], &a[max]);begin++;end--;}
}

2.4 特性总结✅

1. 直接选择排序思考非常好理解，但是效率不是很好（后面会性能对比）。实际中很少使用

2. 时间复杂度：O(N^2)

最好的情况下也是O(N^2)：接近有序or有序
但是，我们不知道有序还是无序，还是需要遍历并且选出max和min交换--->O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

3. 堆排序🔵

之前的博客我们详细介绍过了堆排序的实现，这里就不再详述了，直接上代码。需要详述的小伙伴可以点击下方链接🔗：

Note3---初阶二叉树～～-CSDN博客文章浏览阅读1.1k次，点赞59次，收藏51次。这篇博客，我们一起来了解并学习数据结构中的初阶的二叉树的概念和性质；以及堆和堆堆应用二叉树的知识点和内容比较多，友友们一定要有耐心看完（跳到自己需要的部分也是OK的）。https://blog.csdn.net/2301_79184587/article/details/135033457

3.1 代码实现🏧

3.1.1 sort.h

//堆排序
void HeapSort(int* a, int n);

3.1.2 sort.c

//向下调整
void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){if (a[child + 1] > a[child] && child + 1 < size)child++;if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}elsebreak;}
}//堆排序
void HeapSort(int* a, int n)
{//建大堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

3.1.3 test.c

//堆排序
void testHeapSort()
{int a[] = { 3,2,6,8,9,7,5,10,1,4 };int n = sizeof(a) / sizeof(int);HeapSort(a, n);PrintArray(a, n);
}
int main()
{testHeapSort();return 0;
}

3.2 特性总结🛜

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

4. 选择排序和插入排序性能对比🅿️

// 测试排序的性能对比
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);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand()+i;a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();//QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();//MergeSort(a6, N);int end6 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);
}
int main()
{TestOP();return 0;
}

我们发现，10万数据的时候，堆排序和希尔排序相差不大；100万个数据时，希尔排序的时间复杂度远超于堆排序的时间复杂度

后语⭕️

今天，我们学习了选择排序的实现和性能对比以及他们的特性总结。希望小伙伴们自己也可以练习一下，加强记忆和理解。

下一篇博客，我们将一起学习交换排序的相关知识点！请大家多多期待🙏

本次的分享到这里就结束了！！！

PS：小江目前只是个新手小白。欢迎大家在评论区讨论哦！有问题也可以讨论的！期待大家的互动！！！

公主/王子殿下，请给我点赞👍+收藏⭐️+关注➕（这对我真的很重要！！！）

这篇关于元旦特辑：Note6---选择排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/554757。

相关文章

如何选择适合孤独症兄妹的学校？

如何选择适合孤独症兄妹的学校？

在探索适合孤独症儿童教育的道路上，每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时，选择一所能够同时满足两个孩子特殊需求的学校，更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择，并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症，这一复杂的神经发育障碍，影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...
cross-plateform 跨平台应用程序-03-如果只选择一个框架，应该选择哪一个?

cross-plateform 跨平台应用程序-03-如果只选择一个框架，应该选择哪一个?

跨平台系列 cross-plateform 跨平台应用程序-01-概览 cross-plateform 跨平台应用程序-02-有哪些主流技术栈？ cross-plateform 跨平台应用程序-03-如果只选择一个框架，应该选择哪一个? cross-plateform 跨平台应用程序-04-React Native 介绍 cross-plateform 跨平台应用程序-05-Flutte
阅读更多...
如何选择SDR无线图传方案

如何选择SDR无线图传方案

在开源软件定义无线电（SDR）领域，有几个项目提供了无线图传的解决方案。以下是一些开源SDR无线图传方案： 1. **OpenHD**：这是一个远程高清数字图像传输的开源解决方案，它使用SDR技术来实现高清视频的无线传输。OpenHD项目提供了一个完整的工具链，包括发射器和接收器的硬件设计以及相应的软件。 2. **USRP（Universal Software Radio Periphera
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【软考】希尔排序算法分析

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组，例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量，换值int temp;in
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2