数据结构 — 选择排序

雨点打透心脏的1/2处 2022-06-05 06:52 178阅读 0赞

# 选择排序 #

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

有数据当中 选出来最小的哪一个放到前面. 然后再次选一个次小的放到第二个的位置. 听起来跟插入排序很相似. 但是这里有很大的不

同. 插入排序是不同的元 素找位置住下来. 选择排序是不同的位置找元素来住.但是呢两者的目的都是相等的. 但其实吧插入排序是优于

选择排序的,你这样想选择排序他要找 到最小的他必须把这一组数据遍历完. 而插入排序每次其实不一定会把所有数据遍历完,有时候只

需要循环一次就插入了. 但是今天我们的主题是选择 排序，那么我就不损选择排序了.

其实选择排序的过程非常容易具体分为三个步骤:

1.从你需要排序的序列找出最小的元素.

2.如果最小元素不是待排序列的第一个元素，将其和第一个元素互换.

3.从余下N-1个元素中，找出关键字最小的元素,重复(1)(2)操作，直到排序结束.

![20171120202049318][]

**实现代码：**

void ChooseSort(int* a, size_t size)
    {
    	int mix = 0;
    
    	for (int i = 0; i < size; i++)
    	{
    		mix = i;
    		for (int j = i + 1; j < size; ++j)
    		{
    			if (a[mix] > a[j])
    			{
    				mix = j;
    			}
    		}
    		swap(a[i], a[mix]);
    	}
    }

简单选择排序的比较与序列的初始序列没有关系，就算你给我的时候就是一个有序的序列. 选择排序还是会老老实实的去循环查找，因为

我不遍历 完根本就不知道我到底是不是最小的. 假设待排序列有N个元素，则比较次数总是N(N-1)/2. 所以时间复杂度无论无何都是O(N^2).

[算法][Link 1]名称　　最差时间复杂度　　平均时间复杂度　　最优时间复杂度　　空间复杂度　　稳定性

**选择排序　　　　O(n2)　　　　 O(n2)　****O(****n**2**)　** O(1)　　　 不稳定

[20171120202049318]: /images/20220605/f7fe55f8c7854be5988388cf38cb4c47.png
[Link 1]: http://lib.csdn.net/base/datastructure

发表评论取消回复

表情：

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

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

相关阅读

相关简单选择排序（数据结构）

简单选择排序的算法实现和复杂度分析。

Dear 丶/ 2024年04月23日 20:12/ 0 赞/ 72 阅读

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

目录一、什么是选择排序？二、堆排序 -------------------- 一、什么是选择排序？ 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)。选择排序是一种不稳定的排序，为什么呢？因为不好处理相等两个数的前后位置，举个例

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

相关数据结构-选择排序

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

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

相关数据结构－杂记--选择排序

动态存储空间 `c`语言允许在程序运行时，进行存储空间的分配,这段空间就是系统堆; 通常申请动态内存空间使用的函数是`

清疚/ 2022年06月07日 03:48/ 0 赞/ 180 阅读

相关数据结构 — 选择排序

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

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

相关数据结构(四)选择排序

1、算法流程 (1)首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 (2)然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。 (3

野性酷女/ 2022年06月01日 11:12/ 0 赞/ 156 阅读

相关 C++数据结构--选择排序

\include <stdio.h> typedef int InfoType; \define n 5 //假设的文件长度，即待排序的记录数目 typedef i

野性酷女/ 2022年01月22日 01:05/ 0 赞/ 252 阅读