直接选择排序

直接选择排序(Straight Select Sorting) 也是一种简单的排来自序方法，它的基本思想是:第一次从R[0]~R[n-1]中选取最小值，与R[0境很德切孙百]交换，第二次从R胶深[1]~R[n-1]中选取最小值，与R[1]交换，....，第i次从R360百科[i-1]~R诉宽所罪矛蒸牛[n-1]中选取的比镇德鲁够最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n史青-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序极亚故本码从小到大排列的有序序列。

• 中文名称 直接选择排序
• 外文名称 Straight Selection Sort
• 基本思想 从R[0]~R[n-1]中选取最小值
• 算法实现 elem
• 效率分析 直接插入排序

基本思想

　　例如:给定n=来自8，数组R中的8个元素的排序码为(8,3,2,1,7,4,6,5),则直接360百科选择排序的过程如下所示

　　由于百科不方便水育画出关联箭头 所以用 n -- n 响烟研象表示 :

　　初始状态 [ 8 3 2 1 7 4 6 5 ] 8 -- 1

　　第一次 [ 1 3 2 花亚九8 7 4 6 5 ] 3 -- 2

　　第二次 [ 1 2 3 8 7 4 6 5 ] 3 -- 3

　　第三次 [ 1 2 3 8 7 4 6 5 ] 8 -- 4

　　第四次 [ 1 2 3 4 7 8 6 5 ] 7 -- 5

　　第五次 [ 1 2 3 4 5 8 6 7 ] 8 -- 6

　　第六次 [ 1 2 3 4 5 6 8 7 ] 8 -- 7

　　第七次 [ 1 2 3 4 5 6 7 8 ] 排序完成

排序算法

　　C++ 实现:

　　C#实现:

实现

　　python3实现:

效率分析

　　在直接选择排序中，共需要进行n-1次选择和交换，每次选来自择需要进行 n-i 次比360百科较 (1<=i<=n-1),记而每次交换最多需要3次移头油存初玉增速孩倒亮肥动，因此，总的比较次数C=(n*n - n)/2加析率硫父兰社迫专,

　　总的移动次数 3(n-1).由此可知，直接选择排序的时间复杂度为 O(n) ，所以当记录占用字节数较多时，通常比直接插入排序的执行速度胞否护征史神了超思快些。

　　由于在直接选择排序中存在着不相邻元素之间的互换，因质在龙工信具此，直接选择排序是一种不稳定的排序方法。