数据结构从入门到精通——直接选择排序

直接选择排序

  • 前言
  • 一、选择排序的基本思想：
  • 二、直接选择排序
  • 三、直接选择排序的特性总结：
  • 四、直接选择排序的动画展示
  • 五、直接选择排序的代码展示
    • test.c
  • 六、直接选择排序的优化
    • test.c

前言

直接选择排序是一种简单的排序算法。它的工作原理是每一次从未排序部分选出最小（或最大）的一个元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。这种算法的时间复杂度为O(n^2)，其中n是待排序元素的数量，因此在处理大数据集时效率较低。然而，它的实现简单，对于小规模的数据排序是一个不错的选择。

一、选择排序的基本思想：

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

选择排序的基本思想是从未排序的序列中找到最小（或最大）的元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

这种排序算法的优点在于其实现过程相对简单，对于小规模的数据排序，其效率是可以接受的。然而，选择排序也存在明显的缺点。由于其每次都需要从未排序的元素中找到最小（或最大）的元素，这导致算法的时间复杂度为O(n^2)，其中n为待排序元素的数量。这意味着当处理大规模数据时，选择排序的性能可能会变得非常低下。

在实际应用中，选择排序往往不是最优的选择，特别是对于大规模数据的排序。更高效的排序算法，如快速排序、归并排序、堆排序等，在处理大规模数据时，通常会有更好的性能表现。

但是，选择排序的思想在某些特定情境下仍然有其应用价值。例如，在某些需要稳定排序且数据量较小的场景中，选择排序可以作为一个简单且有效的解决方案。此外，选择排序的思想也可以作为其他更复杂排序算法的基础，帮助理解和学习更高级的排序算法。

总的来说，选择排序的基本思想虽然简单，但其性能上的局限性使得它在实际应用中并不常见。然而，这并不意味着它没有价值，通过深入理解和应用选择排序的思想，我们可以更好地理解排序算法的本质，并为学习更高级的排序算法打下坚实的基础。

二、直接选择排序

  • 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
  • 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
  • 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

直接选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

首先，我们假设有一个无序的整数列表，我们想要通过直接选择排序将其按升序排列。算法的工作流程可以分为以下几个步骤：

  1. 找到最小（大）元素：在列表中找到最小（大）的元素。这个步骤通常涉及遍历整个列表，比较每个元素的值。
  2. 交换位置：一旦找到最小（大）元素，将其与列表的第一个元素交换位置。这样，最小（大）的元素就被放到了它应该在的位置。
  3. 移除已排序元素：从列表中移除已排序的第一个元素（现在是最小（大）元素），然后对剩余的元素重复上述两个步骤。
  4. 重复过程：继续这个过程，每次从剩余的未排序元素中找到最小（大）元素，并将其与未排序部分的第一个元素交换。
  5. 结束条件：当整个列表都被排序时，算法结束。

直接选择排序的时间复杂度是O(n^2)，其中n是列表的长度。这是因为它包含两个嵌套循环：一个用于找到最小（大）元素，另一个用于遍历整个列表。尽管这种排序方法在处理小型或中型列表时可能是有效的，但对于大型列表，更高效的排序算法（如快速排序、归并排序或堆排序）通常是更好的选择。

然而，直接选择排序有一个显著的优点，那就是它的实现相对简单，对于初学者来说是一个很好的学习工具。通过理解这个算法，可以对排序的基本概念有一个直观的认识，从而为学习更复杂的排序算法打下基础。

在实际应用中，直接选择排序可能不是最优选择，但它在教育、演示和教学方面仍然具有很高的价值。此外，对于某些特定类型的数据集（如部分有序的数据集），直接选择排序的性能可能会比其他算法更好。

三、直接选择排序的特性总结：

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

直接选择排序的特性总结起来，主要是其直观易懂、原地排序和不稳定排序的特点。

直接选择排序是一种简单直观的排序算法，其基本原理是每一次从未排序的部分选出最小（或最大）的一个元素，存放到排序序列的起始位置。它的操作过程是从左到右逐个选择剩余元素中的最小者，并将其与未排序部分的第一个元素交换。这种选择过程一直持续到未排序部分为空，排序也就完成了。因此，直接选择排序的直观性是其显著特点之一，使得初学者容易理解和实现。

另一个特性是原地排序，这意味着直接选择排序不需要额外的存储空间来进行排序，它直接在原始数组上进行操作，改变了原始数组的顺序。这一特性使得它在处理内存受限的场景时非常有用。

然而，直接选择排序也是一种不稳定的排序算法。稳定性是指如果两个元素的键值相等，那么在排序之后它们的相对位置不会改变。由于直接选择排序在每次选择最小（或最大）元素进行交换时，可能会改变相等元素的原始相对位置，因此它不具备稳定性。

总的来说，直接选择排序是一种简单直观、原地进行的排序算法，但它是不稳定的。在实际应用中，根据数据的特性和排序要求，可能需要选择更合适的排序算法。例如，对于大规模数据集，直接选择排序的效率可能较低，因为它需要多次遍历和交换操作。而对于小规模数据集或者对稳定性要求不高的场景，直接选择排序则是一个简单有效的选择。

四、直接选择排序的动画展示

直接选择排序是一种简单的排序算法。它通过每次从未排序部分选择最小（或最大）元素，与未排序部分的第一个元素交换位置，从而达到排序的目的。在动画展示中，可以看到每次选择的最小（或最大）元素逐步“冒泡”到已排序部分的末尾，直到整个序列有序。这种排序方法的时间复杂度为O(n^2)，适用于小规模数据的排序。

选择排序

五、直接选择排序的代码展示

test.c

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void SelectSort(int* a, int n);
void PrintArray(int* a, int n);
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void TestSelectSort()
{
	int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };
	//int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	PrintArray(a, sizeof(a) / sizeof(int));

	SelectSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));
}


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void TestOP()
{
	srand(time(0));
	const int N = 10000;
	int* a1 = (int*)malloc(sizeof(int) * N);

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


	int begin1 = clock();
	SelectSort(a1, N);
	int end1 = clock();

	
	
	printf("SelectSort:%d\n", end1 - begin1);

	free(a1);
}
void SelectSort(int* a, int n)
{
	for (int k = 0; k < n; k++)
	{
		int max = 0;
		for (int i = 0; i < n - k; i++)
		{
			if (a[i] >= a[max])max = i;
		}
		Swap(&a[n - 1 - k], &a[max]);
	}
	
}
int main()
{
	TestSelectSort();
	TestOP();

	return 0;
}

这段代码实现的是选择排序（Selection Sort）算法，而不是通常的冒泡排序（Bubble Sort）。选择排序是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

接下来我将逐步解释这段代码：

  1. 函数定义：
void SelectSort(int* a, int n)

这是一个名为 SelectSort 的函数，它接受一个整数数组 a 和一个整数 n 作为参数。n 是数组 a 的长度。

  1. 外层循环：for (int k = 0; k < n; k++)

这个循环从 0 到 n-1 迭代，用于确定当前应该放置最小元素的位置。

  1. 初始化 max 变量：int max = 0;

在每次外层循环开始时，max 被初始化为 0。这个变量用于存储当前找到的最小元素的位置。

  1. 内层循环：for (int i = 0; i < n - k; i++)

这个循环从 0 到 n-k-1 迭代。每次迭代，它都会检查从 a[0] 到 a[n-k-1] 的元素，以找到当前最小元素的位置。

  1. 判断并更新最小元素的位置：if (a[i] >= a[max]) max = i;

这个条件检查 a[i] 是否大于或等于 a[max]。如果是，则更新 max 为 i。注意这里使用了 >= 而不是 >，这意味着如果有多个相同的最小元素，它们都会被正确地处理。

  1. 交换元素：Swap(&a[n - 1 - k], &a[max]);

在内层循环结束后，我们已经找到了从 a[0] 到 a[n-k-1] 中的最小元素，它的位置是 max。现在，我们需要将这个最小元素与当前位置 n-1-k 的元素交换。

整体上，这段代码通过不断地选择并交换最小元素，最终将数组 a 排序为升序。

六、直接选择排序的优化

使用min和max对直接选择排序进行优化可以减少交换的次数。

在原始的直接选择排序算法中，每次迭代会通过查找最小值和最大值的索引来确定需要交换的元素。然后分别进行交换。这样可能会导致不必要的交换操作。

优化的思路是，在每次迭代中，同时查找最小值和最大值的索引，然后将它们记录下来，最后再进行一次交换操作。

具体实现如下：

void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int min = begin, max = end;
        for (int i = begin; i <= end; i++)
        {
            if (a[i] <= a[min]) min = i;
            if (a[i] >= a[max]) max = i;
        }

        // 将最小值放到已排序部分的起始位置
        Swap(&a[begin], &a[min]);
        
        // 如果最大值的索引是begin，将最大值的索引更新为min
        if (max == begin) max = min;
        
        // 将最大值放到已排序部分的末尾位置
        Swap(&a[end], &a[max]);
        
        begin++;
        end--;
    }
}

这样的优化可以减少交换的次数，提高排序的效率。同时，可以确保每次迭代只进行一次交换操作，减少了内存的读写次数，提高了算法的性能。

 if (max == begin) max = min;

关于这个代码是为了防止min正好在end,而max正好在begin这种的特殊情况

test.c

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void SelectSort(int* a, int n);
void PrintArray(int* a, int n);
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void TestSelectSort()
{
	int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };
	//int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	PrintArray(a, sizeof(a) / sizeof(int));

	SelectSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));
}


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void TestOP()
{
	srand(time(0));
	const int N = 10000;
	int* a1 = (int*)malloc(sizeof(int) * N);

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


	int begin1 = clock();
	SelectSort(a1, N);
	int end1 = clock();

	
	
	printf("SelectSort:%d\n", end1 - begin1);

	free(a1);
}
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int min = begin, max = end;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] <= a[min])min = i;
			if (a[i] >= a[max])max = i;
		}
		Swap(&a[begin], &a[min]);
		if (max == begin)max = min;
		Swap(&a[end], &a[max]);
		begin++;
		end--;
	}
	
	
}
int main()
{
	TestSelectSort();
	TestOP();

	return 0;
}

这段代码实现的是选择排序算法，用于对数组a中的元素进行排序。传入参数是数组a和数组长度n。

代码的主要思路是：通过每一次迭代，从未排序的元素中找到最小值和最大值，并将它们分别放到已排序部分的起始位置和末尾位置。然后缩小未排序部分的范围，再次进行迭代直至完成排序。

  1. 初始化变量begin为数组的起始索引0，end为数组的终止索引n-1。
  2. 进入循环，判断begin是否小于end。如果是，继续下面的操作；如果不是，说明排序已完成，退出循环。
  3. 在每一次迭代中，定义变量min和max，分别用于记录当前未排序部分的最小值和最大值的索引，初始值分别设为begin和end。
  4. 从begin到end遍历数组a，找到当前最小值和最大值的索引，更新min和max。
  5. 交换最小值和begin位置的元素，使当前最小值放到已排序部分的起始位置。
  6. 如果max等于begin，说明最大值原本就在begin位置，交换后已经移到了最小值应该在的位置，所以需要将max更新为min。
  7. 交换最大值和end位置的元素，使当前最大值放到已排序部分的末尾位置。
  8. 完成一次迭代后，已排序部分的范围向两端缩小，begin增加1，end减少1。
  9. 重复2-8步骤，直到begin不小于end，排序完成。

总结起来，选择排序每次迭代都会确定未排序部分的最小值和最大值的位置，并将它们交换到已排序部分的起始和末尾位置。通过多次迭代，最终达到整个数组的有序状态。

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/472626.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux-docker安装数据库mysql

Linux-docker安装数据库mysql

1、拉去mysql镜像&#xff1a; docker pull mysql2、创建容器挂载路径 mkdir -p /usr/local/jiuxiang/mysql/data # 数据存储位置 mkdir -p /usr/local/jiuxiang/mysql/logs # 日志存储位置 mkdir -p /usr/local/jiuxiang/mysql/conf # 配置文件3、启动容器 docker run -…
阅读更多...
详细分析Python模块中的雪花算法（附模板）

详细分析Python模块中的雪花算法（附模板）

目录 前言1. 基本知识2. 模板3. Demo 前言 分布式ID的生成推荐阅读&#xff1a;分布式ID生成方法的超详细分析&#xff08;全&#xff09; 1. 基本知识 Snowflake 算法是一种用于生成全局唯一 ID 的分布式算法&#xff0c;最初由 Twitter 设计并开源 它被设计用于解决分布式…
阅读更多...
sentinel整合openFeign实现fall服务降级

sentinel整合openFeign实现fall服务降级

服务提供方: 导入依赖&#xff1a; <!--openfeign--><dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-openfeign</artifactId></dependency><!--alibaba-sentinel--><depend…
阅读更多...
猫猫编号

猫猫编号

解法&#xff1a; 暴力 #include<iostream> #include<algorithm> #include<vector> using namespace std; #define endl \nint main() {int n, m, sum 1;cin >> n >> m;string s;cin >> s;int pre s[0] - 0;int t 0;for (int i 1; i…
阅读更多...
【DAY13 软考中级备考笔记】操作系统

【DAY13 软考中级备考笔记】操作系统

操作系统 3月17日 – 天气&#xff1a;晴 凑着周末&#xff0c;赶紧把操作系统完结一下。 1. 管程 管程也属于操作系统中的一种同步机制&#xff0c;为了解决多线程环境中的并发控制问题。它提供了一系列的高级同步原语。 作用于信号量一样&#xff0c;但是管程便携程序更加简单…
阅读更多...
腾讯云优惠券介绍、领取入口及使用教程

腾讯云优惠券介绍、领取入口及使用教程

腾讯云作为国内领先的云服务提供商&#xff0c;一直以其稳定、高效、安全的服务赢得了广大用户的信赖。为了回馈广大用户&#xff0c;腾讯云经常会推出各种优惠活动&#xff0c;其中优惠券就是最为常见和受欢迎的一种。 一、腾讯云优惠券介绍 腾讯云优惠券是腾讯云官方推出的一…
阅读更多...
Json Web Token(JWT) 快速入门

Json Web Token(JWT) 快速入门

推荐视频&#xff1a;【从零开始掌握JWT】 目录 第一章 会话跟踪 01 使用Cookie和Session&#xff0c;jsessionid 02 使用token 例子一&#xff1a;自定义token 例子二&#xff1a;使用redis存储token 第二章 会用JWT 01 TOKEN的特点 02 什么时候使用JWT 03 JWS-JWE…
阅读更多...
Linux学习：git补充与调试工具gdb

Linux学习：git补充与调试工具gdb

目录 1. git版本控制器&#xff08;续&#xff09;1.1 git本地仓库结构1.2 git实现版本控制与多人协作的方式1.3 git相关指令&#xff0c;多分支模型与.gitignore文件 2. gdb调试工具2.1 企业项目开发流程简述与调试的必要性2.2 bug的调试思路方法与调式工具的使用 1. git版本控…
阅读更多...
目标检测---IOU计算详细解读(IoU、GIoU、DIoU、CIoU、EIOU、Focal-EIOU、SIOU、WIOU)

目标检测---IOU计算详细解读(IoU、GIoU、DIoU、CIoU、EIOU、Focal-EIOU、SIOU、WIOU)

常见IoU解读与代码实现 一、✒️IoU&#xff08;Intersection over Union&#xff09;1.1 &#x1f525;IoU原理☀️ 优点⚡️缺点 1.2 &#x1f525;IoU计算1.3 &#x1f4cc;IoU代码实现 二、✒️GIoU&#xff08;Generalized IoU&#xff09;2.1 GIoU原理☀️优点⚡️缺点 2…
阅读更多...
深入理解Java中的TCP连接：三次握手和四次挥手

深入理解Java中的TCP连接：三次握手和四次挥手

欢迎来到我的博客&#xff01;今天我们将一起探索网络通信的奥秘。在Java编程中&#xff0c;我们经常会涉及到网络通信&#xff0c;而TCP协议是实现可靠数据传输的重要协议之一。在建立TCP连接和断开连接的过程中&#xff0c;三次握手和四次挥手是至关重要的步骤。本文将深入探…
阅读更多...
rt-thread(5.0版本)之sfud组件的使用问题记录(w25q128存储模块)

rt-thread(5.0版本)之sfud组件的使用问题记录(w25q128存储模块)

前言 记录一下5.0版本时使用官方推荐的函数与底层驱动存在的不兼容问题 相关宏定义 // -----------------------------SPI 组件 #define RT_USING_SPI #define RT_USING_SFUD #define RT_SFUD_USING_SFDP #define RT_SFUD_USING_FLASH_INFO_TABLE #define RT_SFUD_SPI_MAX_HZ…
阅读更多...
生骨肉冻干喂养有哪些优点？对猫身体好的生骨肉冻干分享

生骨肉冻干喂养有哪些优点？对猫身体好的生骨肉冻干分享

随着科学养猫知识的普及&#xff0c;生骨肉冻干喂养越来越受到养猫人的青睐。生骨肉冻干不仅符合猫咪的饮食天性&#xff0c;还能提供均衡的营养&#xff0c;有助于维护猫咪的口腔和消化系统健康。很多铲屎官看到了生骨肉冻干喂养的好处&#xff0c;打算开始生骨肉冻干喂养&…
阅读更多...
ES 常见面试题及答案

ES 常见面试题及答案

目录 es 写入数据流程 es 删除数据流程 es 读数据流程 es 部署的服务有哪些角色 es 的实现原理 es 和lucence 关系 如何提高写入效率 提高搜索效率 es doc value指的啥 分片指的啥&#xff0c;定义后可不可义再修改 深分页如何优化 对于聚合操作是如何优化的 元数据…
阅读更多...
微服务高级篇（二）：分布式事务+Seata架构

微服务高级篇（二）：分布式事务+Seata架构

文章目录 一、分布式事务理论基础1.1 CAP定理1.2 BASE理论 二、初始Seata2.1 Seata的架构2.2 部署TC【事务协调者】服务2.3 微服务集成Seata 三、实践3.1 XA模式3.1.1 原理3.1.2 实现 3.2 AT模式3.2.1 原理3.2.2 脏写问题以及解决方案【全局锁超时处理】3.2.3 实现 3.3 TCC模式…
阅读更多...
机器人路径规划：基于迪杰斯特拉算法(Dijkstra)的机器人路径规划（提供Python代码）

机器人路径规划：基于迪杰斯特拉算法(Dijkstra)的机器人路径规划（提供Python代码）

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的&#xff0c;因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法&#xff0c;解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始&#xff0c;采用贪心算法的策略&#…
阅读更多...
【漏洞复现】Progress Kemp LoadMaster 命令注入漏洞(CVE-2024-1212)

【漏洞复现】Progress Kemp LoadMaster 命令注入漏洞(CVE-2024-1212)

0x01 产品简介 Progress Kemp LoadMaster是一款高性能的应用交付控制器&#xff0c;具有可扩展性&#xff0c;支持实体硬件和虚拟机的负载均衡。它提供了当今应用服务所需的各种功能&#xff0c;包括深度用户验证、资安防护&#xff08;如WAF/IPS/DDoS防护&#xff09;以及零信…
阅读更多...
Cannot run program “C:\Program Files\Java\jdk-17\bin\java.exe“

Cannot run program “C:\Program Files\Java\jdk-17\bin\java.exe“

错误提示&#xff1a;Cannot run program “C:\Program Files\Java\jdk-17\bin\java.exe” 解决办法&#xff1a; 检查环境变量是否配置是否正确检查项目环境是否正确&#xff0c;可能会出现多个JDK版本&#xff0c;将不需要的删除
阅读更多...
Spring Cloud(Finchley版本)系列教程(四) 断路器(Hystrix)

Spring Cloud(Finchley版本)系列教程(四) 断路器(Hystrix)

Spring Cloud(Finchley版本)系列教程(四) 断路器(Hystrix) 为了更好的浏览体验&#xff0c;欢迎光顾勤奋的凯尔森同学个人博客http://www.huerpu.cc:7000 一、断路器Hystrix hystrix是Netlifx开源的一款容错框架&#xff0c;防雪崩利器&#xff0c;具备服务降级&#xff0c;…
阅读更多...
如何实现在固定位置的鼠标连点

如何实现在固定位置的鼠标连点

鼠大侠的鼠标连点功能是免费的 浏览器搜索下载鼠大侠&#xff0c;指定连点间隔和启动快捷键 点击设置&#xff0c;指定点击位置
阅读更多...
2024年熔化焊接与热切割证模拟考试题库及熔化焊接与热切割理论考试试题

2024年熔化焊接与热切割证模拟考试题库及熔化焊接与热切割理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年熔化焊接与热切割证模拟考试题库及熔化焊接与热切割理论考试试题是由安全生产模拟考试一点通提供&#xff0c;熔化焊接与热切割证模拟考试题库是根据熔化焊接与热切割最新版教材&#xff0c;熔化焊接与热切割大…
阅读更多...
最新文章

Copyright @ 2022~2023