数据结构与算法（三）：带你读懂选择排序（Selection sort）

Kaede 发布于2019-08-16 18:24 / 3301人阅读

摘要：基本介绍选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。而移动次数与序列的初始排序有关。空间复杂度简单选择排序需要占用个临时空间，在交换数值时使用。

1. 基本介绍

选择式排序（select sorting）也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

2. 选择排序思想

基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值，与 arr[0]交换，第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，第三次从 arr[2]~arr[n-1]中选取最小值，与 arr[2]交换，…，第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换，…, 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值，与 arr[n-2]交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。

3. 选择排序理解

3.1 选择排序图解

1.选择排序一共有数组大小-1 次排序
2.每一次排序，又是一个循环，循环规则如下
2.1 先假定当前这个数是最小数
2.2 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标
2.3 当遍历到数组的最后时，就得到本轮最小数和小标
2.4 交换代码，再继续

4. 选择排序代码

/**
 * @author: Coder编程
 * @create: 2019-6-20 22:06
 * @description: 选择排序
 **/
public class SelectionSort {

    /**
     * 选择排序
     * @param arr 待排序数组
     */
    public void selectionSort(Integer[] arr) {
        // 需要遍历获得最小值的次数
        // 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列
        for (int i = 0; i < arr.length - 1; i++) {

            int minindex = i; // 用来保存最小值得索引
            int min = arr[i]; // 用来保存最小值

            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {// 说明假定的最小值，并不是最小
                    min = arr[j]; // 重置 min
                    minindex = j; // 重置 minIndex
                }
            }
 
            // 如果假定最小值的索引发生了改变，则进行交换
            if(minindex != i){
                arr[minindex] = arr[i]; //此时minindex为j，因此i与j交换
                arr[i] = min;  //最小值给下标i
            }
            System.out.format("
第 %d 趟:	", i + 1);
            Arrays.asList(arr).stream().forEach(x -> System.out.print(x + " "));
        }
    }


    public static void main(String[] args) {
        //初始数组
        Integer arrays[] = {2,9,7,5,3};
 
        // 调用选择排序方法
        SelectionSort selection = new SelectionSort();
        System.out.print("欢迎个人公众号Coder编程：选择排序前：	");
        Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " "));
        selection.selectionSort(arrays);
        System.out.print("
欢迎个人公众号Coder编程：选择排序后:	");
        Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " "));
    }
 
}

打印结果

如果还有什么不理解的，可以把代码Debug抛一遍就明白了。

5. 选择排序性能分析 5.1 时间复杂度

简单选择排序的比较次数与序列的初始排序无关。假设待排序的序列有n个元素，则比较次数总是n(n - 1) / 2。
而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0.
当序列反序时，移动次数最多，为3n (n- 1) / 2。
所以，综合以上，简单排序的时间复杂度为 O(n^2)。

5.2 空间复杂度

简单选择排序需要占用 1 个临时空间，在交换数值时使用。

6. 选择排序扩展阅读 6.1 C语言版

#include 
int main()
{
    int i,j,t,a[11];    //定义变量及数组为基本整型
    printf("请输入10个数：
");
    for(i=1;i<11;i++)
        scanf("%d",&a[i]);    //从键盘中输入要排序的10个数字
    for(i=1;i<=9;i++)
        for (j=i+1;j<=10;j++)
            if(a[i]>a[j])    //如果前一个数比后一个数大，则利用中间变量t实现两值互换
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
    printf("排序后的顺序是：
");
    for(i=1;i<=10;i++)
        printf("%5d", a[i]);    //输出排序后的数组
    printf("
");
    return 0;
}

6.2 Python版

def selectedSort(myList):
    length = len(myList)
    for i in range(0,length-1):
        smallest = i
        for j in range(i+1,length):

            if myList[j]
6.3 JS版
var example=[2,9,7,5,3];
function selectSort(arr){
    var len=arr.length;
    var minIndex,temp;
    console.time("选择排序耗时")；
    for(i=0;i
文末
欢迎关注个人微信公众号：Coder编程
获取最新原创技术文章和免费学习资料，更有大量精品思维导图、面试资料、PMP备考资料等你来领，方便你随时随地学习技术知识！
新建了一下qq群：315211365，欢迎大家进群交流一起学习。谢谢了！也可以介绍给身边有需要的朋友。
文章收录至
Github: https://github.com/CoderMerli...
Gitee: https://gitee.com/573059382/c...



参考文章：
https://blog.csdn.net/qq_3624...
https://www.cnblogs.com/shen-...
推荐文章：
带你了解时间复杂度和空间复杂度到底是什么？
带你读懂冒泡排序（Bubble Sorting）

超融合服务器 idc机房托管 sort排序算法选择排序的算法过程字符串选择排序算法用c语言三个数的排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75006.html

数据结构与算法（二）：带你读懂冒泡排序（Bubble Sorting）

摘要：经过一次冒泡排序，最终在无序表中找到一个最大值，第一次冒泡结束。也是我们后面要说的冒泡排序的优化。冒泡排序只执行第一层循环，而不会执行第二层循环。因此冒泡排序的时间复杂度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...

chuyao 2019-08-19 11:46 评论0 收藏0
少啰嗦！一分钟带你读懂Java的NIO和经典IO的区别

摘要：的选择器允许单个线程监视多个输入通道。一旦执行的线程已经超过读取代码中的某个数据片段，该线程就不会在数据中向后移动通常不会。 1、引言很多初涉网络编程的程序员，在研究Java NIO（即异步IO）和经典IO（也就是常说的阻塞式IO）的API时，很快就会发现一个问题：我什么时候应该使用经典IO，什么时候应该使用NIO？在本文中，将尝试用简明扼要的文字，阐明Java NIO和经典IO之...

Meils 2019-08-16 18:23 评论0 收藏0
一篇带你读懂TCP之“滑动窗口”协议

摘要：问题一如何保证次序提出问题在我们滑动窗口协议之前，我们如何来保证发送方与接收方之间，每个包都能被收到。文末从我们为了增加网络的吞吐量，想讲数据包一起发送过去，这时候便产生了滑动窗口这种协议。前言你现在的努力，是为了以后有更多的选择。在上一篇文章通过表白方式，让我们快速了解网络七层协议了解了网络七层协议。接下来我们要把重心放在网络传输的可靠性上面。一起来看TCP协议，它是如何解决...

malakashi 2019-06-24 17:27 评论0 收藏0
带你了解数据库中group by的用法

摘要：注意是先排序后分组语法语法说明，，表达式未封装在聚合函数中，必须包含在语句末尾的子句中。语句的存在弥补了关键字不能与聚合函数联合使用的不足。前言本章主要介绍数据库中group by的用法，也是我们在使用数据库时非常基础的一个知识点。并且也会涉及Join的使用，关于Join的用法，可以看我写的上一篇文章：带你了解数据库中JOIN的用法如有错误还请大家及时指出~ 以下都是采用mysq...

qc1iu 2019-08-01 13:53 评论0 收藏0
5分钟带你读懂事务隔离性与隔离级别

摘要：串行化是最严格的隔离级别。接下来我们再提高一个事务隔离级别。事务隔离级别设置为查询事务隔离级别更改数据库隔离级别，设置隔离级别为串行化时间轴事务事务等待中这里就不再对流程做过多赘述。前言我们在上一章节中介绍过数据库的带你了解数据库中事务的ACID特性的相关用法。本章节主要来介绍下数据库中一个非常重要的知识点事务的隔离级别。如有错误还请大家及时指出~ 问题：事务的隔离级别有哪...

muzhuyu 2019-08-01 13:54 评论0 收藏0