复习数据结构：排序（三）——选择排序

Myth丶恋晨 2022-08-07 01:53 160阅读 0赞

选择排序的核心是：每趟选择最小的元素和首部交换。

时间复杂度：O(n^2)。

选择排序是一种不稳定的排序，为什么呢？因为不好处理相等两个数的前后位置，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。所以稳定排序是一定不会改变相等数之间之前位置关系的。

实现代码如下：

#include<iostream>
    using namespace std; 
    
    void SelectSort(int a[], int n)
    {
    	for(int i = 0; i < n-1; i++)  // 注意到n-1
    	{
    		int minIndex = i+1; 
    		for(int j = i+1; j < n; j++)
    		{
    			if(a[j] < a[minIndex])
    				minIndex = j;  // 选择i+1往后最小的数
    		}
    		if(a[minIndex] < a[i])
    			swap(a[minIndex], a[i]); 
    	}
    }
    
    int main()
    {
    	int a[] = {1, 6, 4, 3, 8, 2}; 
    	SelectSort(a, 6); 
    
    	for(int i = 0; i < 6; i++)
    		cout<<a[i]<<' '; 
    	cout<<endl; 
    
    	return 0; 
    }

参考链接：

http://blog.csdn.net/xiazdong/article/details/8462393

http://blog.csdn.net/hguisu/article/details/7776068

http://zhidao.baidu.com/link?url=zFcwJJZtDlBDx-5GK6\_4EVHMseEJg\_mWwNnPVAym4yPJk9YjYch3qpF\_-FSyKspp\_wxQZnS1UUzlpZxGhspHUK

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】选择排序—堆排序

目录一、什么是选择排序？二、堆排序 -------------------- 一、什么是选择排序？ 1. 选择排序的主要思想是每一趟从待排序列中选取

绝地灬酷狼/ 2024年04月03日 10:51/ 0 赞/ 85 阅读

相关【数据结构】选择排序—直接选择排序、树形选择排序

目录一、什么是选择排序？二、直接选择排序三、树形选择排序 -------------------- 一、什么是选择排序？ 1. 选择排序的主要思想是每

叁歲伎倆/ 2024年04月03日 10:43/ 0 赞/ 76 阅读

相关【数据结构】-内部排序(选择排序)

内部排序-选择排序写在前面 1.头文件及类型定义 2.函数声明 3.基本操作 3.1 简单选择排序 3.1.1

落日映苍穹つ/ 2022年11月25日 13:28/ 0 赞/ 191 阅读

相关复习数据结构：排序算法（七）——桶排序

桶排序是一种稳定的排序方法，也是一种外排序。桶排序的时间复杂度：最坏情况运行时间：当分布不均匀时，全部元素都分到一个桶中，则O(n^2)，当然\[算法导论8.

刺骨的言语ヽ痛彻心扉/ 2022年08月07日 01:57/ 0 赞/ 198 阅读

相关复习数据结构：排序算法（六）——堆排序

对于堆排序，前面一篇博文中已经复习到了堆排序，这里就简单介绍一下，并给出核心部分的解释。堆排序是一种不稳定的排序，也是内排序。时间复杂度为O(nlogn

淡淡的烟草味﹌/ 2022年08月07日 01:56/ 0 赞/ 180 阅读

相关复习数据结构：排序（三）——选择排序

选择排序的核心是：每趟选择最小的元素和首部交换。时间复杂度：O(n^2)。选择排序是一种不稳定的排序，为什么呢？因为不好处理相等两个数的前后位置，举个例

Myth丶恋晨/ 2022年08月07日 01:53/ 0 赞/ 161 阅读

相关复习数据结构：排序（一）——插入排序

从这一篇开始，我开始复习数据结构的知识点，博文主要偏重于每个知识点的核心思想，以及代码实现。这一篇先从排序算法中的插入排序开始。稳定排序、内排序、适合少量数据

╰+哭是因爲堅強的太久メ/ 2022年08月07日 01:52/ 0 赞/ 142 阅读

相关复习数据结构：排序算法（二）——冒泡排序

这篇复习冒泡排序。冒泡排序也是一种稳定排序、内排序。冒泡排序的基本思想：对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下

￡神魔★判官ぃ/ 2022年08月07日 01:52/ 0 赞/ 183 阅读

相关数据结构-选择排序

昨天写了数据结构简单排序中的冒泡排序BubblSort：一般来说第一次排序N个数据，有N-1次比较，第二次又N-2次排序........；总共约N^2/2次比较（最坏的情况

谁践踏了优雅/ 2022年06月16日 09:42/ 0 赞/ 171 阅读

相关数据结构 — 选择排序

选择排序选择排序其实算是排序家族当中比较容易理解的排序方法.选择排序的思想最重要的就是这个选择. 你不是要排序嘛. 那么每次在你的所

雨点打透心脏的1/2处/ 2022年06月05日 06:52/ 0 赞/ 179 阅读