选择排序
排序 选择
2023-09-14 09:08:15 时间
昨日写完冒泡排序,和大多数人的感觉一样,太简单,丝毫没有挑战性。但楼主是一个追求踏实平稳的人,希望地基坚固,也为方便后面学习和研究更加高深的算法。但在研究效率上还有待提高,楼主一定好好努力。今天将会写完选择排序 和 插入排序,本文主在选择排序。
一. 算法描写叙述
选择排序:比方在一个长度为N的无序数组中,在第一趟遍历N个数据,找出当中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出当中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出当中最小的数值与第N-1个元素交换,至此选择排序完毕。
以以下5个无序的数据为例:
56 12 80 91 20(文中仅细化了第一趟的选择过程)
第1趟:12 56 80 91 20
第2趟:12 20 80 91 56
第3趟:12 20 56 91 80
第4趟:12 20 56 80 91
二. 算法分析
平均时间复杂度:O(n2)
空间复杂度:O(1) (用于交换和记录索引)
稳定性:不稳定 (比方序列【5, 5, 3】第一趟就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)
三. 算法实现
//交换data1和data2所指向的整形 void DataSwap(int* data1, int* data2) { int temp = *data1; *data1 = *data2; *data2 = temp; } /******************************************************** *函数名称:SelectionSort *參数说明:pDataArray 无序数组; * iDataNum为无序数据个数 *说明: 选择排序 *********************************************************/ void SelectionSort(int* pDataArray, int iDataNum) { for (int i = 0; i < iDataNum - 1; i++) //从第一个位置開始 { int index = i; for (int j = i + 1; j < iDataNum; j++) //寻找最小的数据索引 if (pDataArray[j] < pDataArray[index]) index = j; if (index != i) //假设最小数位置变化则交换 DataSwap(&pDataArray[index], &pDataArray[i]); } }
相关文章
- 汇编排序知识之冒泡排序
- Java实现 LeetCode 81 搜索旋转排序数组 II(二)
- Java实现Labeling Balls(拓扑排序的应用)
- Python实现的选择排序算法原理与用法实例分析
- Python排序算法之选择排序定义与用法示例
- 使用选择排序对一维数组进行排序
- java面试准备之基础排序——冒泡与选择排序
- file.listFiles()按文件大小、名称、日期排序方法
- [数据结构] 选择排序
- LeetCode(26): 删除排序数组中的重复项
- LeetCode(4):两个排序数组的中位数
- 【u019】排序(sort)
- C# 选择排序
- PHP面试题:请写出常见的排序算法,并用PHP实现冒泡排序,将数组$a = array()按照从小到大的方式进行排序。
- 经典算法学习——直接选择排序
- 选择排序
- python各个版本的排序
- 2171. 拿出最少数目的魔法豆-快速排序+前缀和
- 2475. 数组中不等三元组的数目-快速排序+遍历求和
- 面试题 17.14. 最小K个数-快速排序
- java比较排序Comparable和Comparator
- C++ 排序函数 sort(),qsort()的使用方法
- python3 sort 排序 自定义函数 cmp 重写__lt__即可
- 图解大顶堆的构建、排序过程
- 快速排序(c++,java)
- 简单选择排序+直接插入排序知识点复习