Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >浅析选择排序算法

浅析选择排序算法

作者头像
用户7656790
发布于 2021-10-21 02:19:21
发布于 2021-10-21 02:19:21
87300
代码可运行
举报
运行总次数:0
代码可运行

选择排序(Selection Sort)

一、算法描述

  1. 在一个长度为 N 的无序数组中,第一次遍历 n 个数找到最大的和最后一个数交换。
  2. 第二次从倒数第二个数开始遍历 n-1 个数,找到最大的数和倒数第二个数交换。
  3. 重复以上操作直到第 n 次遍历最大的数和第 1 个数交换,排序完成。

例如:我们有 [4 9 3 1 7 2] 这样一组数字。

第一趟:我们找出最大值9和最后一个数字2进行交换。就变成了 [4 2 3 1 7 9],这样我们就把最大值放在最后了。

第二趟:对前5个数字进行排序,同样找出最大值放在倒数第二个位置,因为7已经是这5个数字里面的最大值,所以不需要做交换。还是 [4 2 3 1 7 9]

第三趟:对前4个数字进行排序,找出最大的值放在倒数第三个位置,我们找出4和1进行交换,这样把4放在倒数第三的位置,变成[1 2 3 4 7 9]

第四趟:对前3个数字进行排序,找出最大的值放在倒数第三个位置,因为3是最大值所以不需要进行交换,还是[1 2 3 4 7 9]

第五趟:对前2个数字进行排序,找出最大的值放在倒数第三个位置,因为3是最大值所以不需要进行交换,还是[1 2 3 4 7 9]

第六趟:最后只剩一位数字我们就不用进行排序了,这样我们就对整个数组按照从小到大的顺序进行排序了。最后排序为 [1 2 3 4 7 9]

二、算法实现

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <stdio.h>

int findMaxPos(int arr[], int n){
  int max = arr[0]; 
  int pos = 0;
  for (int i=0; i<n; i++){
    if(arr[i]>max){
      max = arr[i];
      pos = i;
    }
  }
  return pos;
}

void selectionSort(int arr[], int n){
  while (n > 1){
    int pos = findMaxPos(arr,n);
    int temp = arr[pos];
    arr[pos] = arr[n-1];
    arr[n-1] = temp;
    n--;
  }
}

int main(){
  int arr[] = {4,9,3,1,7,2};
  selectionSort(arr,6);
  for(int i=0; i<6; i++){
    printf("%d\n",arr[i]);
  }
}

输出

三、算法分析

平均时间复杂度:O(n2)

空间复杂度:O(1)

稳定性:不稳定(例如序列9 8 5 2 5,我们知道第一遍选择第1个元素9会和5交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法)

四、适用场景

选择排序适用于数据量很小的排序场景,因为选择的实现方式较为简单。

关注下方公众号,分享硬核知识

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-10-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 五角钱的程序员 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
经典排序算法(二)选择排序
选择排序是一种简单排序算法。这是一个基于位置比较的算法,通常实现是左边是已经排好序的元素列表,右边是待排序的元素。当然,一开始的时候,我们认为都是未经排序的。
青山师
2023/05/04
4840
经典排序算法(二)选择排序
图文并茂的排序算法
本文给出常见的几种排序算法的原理以及java实现,包括常见的简单排序和高级排序算法,以及其他常用的算法知识。
用户1212940
2022/04/13
2280
图文并茂的排序算法
选择排序就这么简单
选择排序就这么简单 从上一篇已经讲解了冒泡排序了,本章主要讲解的是选择排序,希望大家看完能够理解并手写出选择排序的代码,然后就通过面试了!如果我写得有错误的地方也请大家在评论下指出。 选择排序介绍和稳定性说明 来源百度百科: 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始(末尾)位置,直到全部待排序的数据元素排完。选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,
Java3y
2018/03/30
9000
选择排序就这么简单
【Python排序算法系列】—— 选择排序
选择排序对冒泡排序进行了改进,保留了其基本的多趟比对思路,每趟都使当前最小项就位。 但选择排序对交换进行了削减,相比起冒泡排序进行多次交换,每趟仅进行1次交换,记录最小项的所在位置,最后再跟本趟第一项交换 ---> 两两对比,小(大)的放前(后)面,对比过程不发生交换。
ImAileen
2024/01/18
1590
【Python排序算法系列】—— 选择排序
java五大排序算法之选择排序
第1趟比较:拿第1个元素依次和它后面的每个元素进行比较,如果第1个元素大于后面某个元素,交换它们,经过第1趟比较,数组中最小的元素被选出,它被排在第一位
乱码三千
2021/07/29
2420
选择排序—简单选择排序(Simple Selection Sort)
在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。
瑾诺学长
2018/09/21
1.9K0
选择排序—简单选择排序(Simple Selection Sort)
选择排序
在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。
用户4645519
2022/05/09
1320
选择排序
2023 跟我一起学算法:排序算法
例如: 下面的字符列表按其 ASCII 值的升序排序。也就是说,具有较小 ASCII 值的字符将比具有较高 ASCII 值的字符先放置。
用户1418987
2023/11/24
2110
2023 跟我一起学算法:排序算法
排序五 简单选择排序
该文介绍了冒泡排序算法的基本原理和实现过程,并通过示例代码和运行结果来展示冒泡排序算法的运行过程。同时,文章还对冒泡排序算法的时间复杂度和空间复杂度进行了分析。
静默虚空
2018/01/05
6630
排序五 简单选择排序
Java数据结构和算法总结-冒泡排序、选择排序、插入排序算法分析
前言:排序在算法中的地位自然不必多说,在许多工作中都用到了排序,就像学生成绩统计名次、商城商品销量排名、新闻的搜索热度排名等等。也正因为排序的应用范围如此之广,引起了许多人深入研究它的兴趣,直至今天
codingblock
2017/12/29
1K0
Java数据结构和算法总结-冒泡排序、选择排序、插入排序算法分析
详解选择排序算法
选择排序的思想是: 给定一个数组arr,其长度为n; 第一次从 arr[0] 到 arr[n-1] 中选取一个最值(按照需求,可以是最大值,可以是最小值,下同)与arr[0]进行交换; 第二次从arr[1] 到 arr[n-1] 中选取一个最值与arr[1]进行交换; 以此类推,直到arr[n-2]到arr[n-1]中选出最值交换后即完成排序。(只剩下一个元素,前面的都是比它小(或者大)的)。
code随笔
2020/04/14
7900
详解选择排序算法
数据结构——lesson9排序之选择排序
图解如下: 以int a[] = {4,7,8,5,6,2,1,9}为例 1.建堆
大耳朵土土垚
2024/03/24
1020
数据结构——lesson9排序之选择排序
选择排序图解
每次从无序区间选择一个最大或者最小值的一个元素,放在无序区间的最后或者最前,直到待排序的所有元素排序完毕。
VIBE
2022/12/02
2400
冒泡排序算法
冒泡排序算法 原理 比较相邻的两个数,将值较大的元素放在最前面,由于较小的数字像泡泡一样浮上来,因此取名为冒泡 从后向前比较(小的数上浮) 第一趟:从数组的最后一个元素和倒数第二个元素比较,小的上浮(交换),之后倒数第二个和倒数第三个数字比较,小的上浮(交换),直至第二个数字和第一个数字比较,小的上浮,那么经过一趟排序之后,此时的第一个元素就是最小的 第二趟: 经过第一趟之后,第一个就是最小的数字,因此第二趟就不比较第一个和第二个数字了。从最后一个元素和倒数第二个元素比较,小的上浮,直至第三个元素和第二个元
爱撒谎的男孩
2018/05/25
5910
九大排序算法总结
计数排序非常基础,他的主要目的是对整数排序并且会比普通的排序算法性能更好。例如,输入{1, 3, 5, 2, 1, 4}给计数排序,会输出{1, 1, 2, 3, 4, 5}。这个算法由以下步骤组成:
用户9854323
2022/06/25
1880
九大排序算法总结
你对排序算法了解多少
说起排序算法,可能大家会脱口而出:冒泡排序,选择排序。没错,这是我们最熟悉的两种排序算法,其实,排序算法远不止这些。而且,你之前写的冒泡、选择排序真的是最优的吗?
贪挽懒月
2020/09/16
3170
十大排序算法详解(一)冒泡排序、选择排序、插入排序、快速排序、希尔排序[通俗易懂]
  冒泡排序是比较基础的排序算法之一,其思想是相邻的元素两两比较,较大的数下沉,较小的数冒起来,这样一趟比较下来,最大(小)值就会排列在一端。整个过程如同气泡冒起,因此被称作冒泡排序。   冒泡排序的步骤是比较固定的:
全栈程序员站长
2022/09/14
8670
十大排序算法详解(一)冒泡排序、选择排序、插入排序、快速排序、希尔排序[通俗易懂]
数据结构——排序算法分析与总结
最好情况:(接近有序或者有序),基本不用移动数据 ->O(N)、 稳定性:稳定
IsLand1314
2024/10/15
1410
数据结构——排序算法分析与总结
C# 排序算法2:选择排序
选择排序法 ,是在要排序的一组数中,选出最小(或最大)的一个数与第一个位置的数交换;在剩下的数当中找最小的与第二个位置的数交换,即顺序放在已排好序的数列的最后,如此循环,直到全部数据元素排完为止。 原理:1. 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,
明志德道
2023/10/21
2490
C# 排序算法2:选择排序
浅析冒泡排序算法
他的排序思想是这样的,依次比较相邻的数据,将小数据放在前,大数据放在后;即第一趟先比较第1个和第2个数,大数在后,小数在前,再比较第2个数与第3个数,大数在后,小数在前,以此类推第一趟将最大的数"滚动"到最后一个位置;第二趟则将次大的数滚动到倒数第二个位置......第n-1(n为无序数据的个数)趟即能完成排序。
用户7656790
2021/10/21
3160
浅析冒泡排序算法
相关推荐
经典排序算法(二)选择排序
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验