简单选择排序

tylin 发布于2019-08-14 15:11 / 2695人阅读

摘要：因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。选择排序的时间复杂度和空间复杂度分别为和。

概述

在要排序的一组数中，选出最小的一个数与第1个位置的数交换；然后在剩下的数当中再找最小的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

换句话说：

以 i 代表当前需要排序的序号，则需要在剩余的 [i... n-1] 中找出其中的最小值，然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。选择排序的时间复杂度和空间复杂度分别为 O(n²) 和 O(1) 。

直观释义图：

步骤

从n 个记录中找出关键码最小的记录与第一个记录交换

从第2 个记录开始的 n-1 个记录中再选出最小的记录与第2 个记录交换

从第i (i是不断+1的)个记录开始的 n-i+1 个记录中选出最小的与第i 个记录交换

直到整个序列有序

实例

原始数据：

3 5 2 6 2

第一轮，找出 [5 2 6 2] 中最小的第三个位置 2 ，与第一个位置 3 进行交换

2 5 3 6 2

第二轮，找出 [3 6 2] 中最小的 2 与第一轮中第二个位置 5 进行交换

2 2 3 6 5

第三轮，找出 [6 5] 中最小的 5 与第二轮中第三个位置 3 不需交换

2 2 3 6 5

第四轮，找出 [5] 中最小的 5 与第三轮中的第四个位置 6 进行交换

2 2 3 5 6

第五轮，没有了，最终结果

2 2 3 5 6

简单选择排序也可以认为是稳定的排序。

代码实现(Java)

package com.coder4j.main.arithmetic.sorting;
    
public class SimpleSelection {

    /**
     * 简单选择排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.println("第" + (i + 1) + "轮比较结果：");
            int minPosition = i;
            // 找出i之后的数组中的最小索引
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minPosition]) {
                    minPosition = j;
                }
            }
            // 判断是否需要调换位置
            if (array[i] > array[minPosition]) {
                int temp = array[i];
                array[i] = array[minPosition];
                array[minPosition] = temp;
            }
            // 输出此轮排序结果
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }
}

测试输出结果：

第1轮比较结果：
2 5 3 6 2 
第2轮比较结果：
2 2 3 6 5 
第3轮比较结果：
2 2 3 6 5 
第4轮比较结果：
2 2 3 5 6 
第5轮比较结果：
2 2 3 5 6 
最终结果
2 2 3 5 6

经测试，与实例中结果一致。

GPU云服务器云服务器最简单的排序算法简单的c语言排序选择排序选择排序法

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

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

选择排序就这么简单

摘要：选择排序就这么简单从上一篇已经讲解了冒泡排序了，本章主要讲解的是选择排序，希望大家看完能够理解并手写出选择排序的代码，然后就通过面试了如果我写得有错误的地方也请大家在评论下指出。选择排序就这么简单从上一篇已经讲解了冒泡排序了，本章主要讲解的是选择排序，希望大家看完能够理解并手写出选择排序的代码，然后就通过面试了！如果我写得有错误的地方也请大家在评论下指出。选择排序介绍和稳定性说明...

wua_wua2012 2019-08-15 14:50 评论0 收藏0
数据结构与算法（三）：带你读懂选择排序（Selection sort）

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

Kaede 2019-08-16 18:24 评论0 收藏0
【算法日积月累】1-选择排序

摘要：选择排序算法实现实现选择排序，记录最小元素的索引，最后才交换位置说明交换两个数组中的元素，在中有更简单的写法，这是的语法糖，其它语言中是没有的。和语言中比较器的实现前面我们说到了，我们为了突出排序算法的思想，将所有的例子仅限在数组排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...

neuSnail 2019-07-31 11:21 评论0 收藏0
Github标星2w+，热榜第一，如何用Python实现所有算法

摘要：归并排序归并排序，或，是创建在归并操作上的一种有效的排序算法，效率为大符号。以此类推，直到所有元素均排序完毕。与快速排序一样都由托尼霍尔提出的，因而也被称为霍尔选择算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);编译：周素云、蒋宝尚学会了Python基础知识，想进阶一下，那就来点算法吧！毕竟编程语言只...

zxhaaa 2019-07-31 10:23 评论0 收藏0
排序算法（Java）——那些年面试常见的排序算法

摘要：下面会介绍的一种排序算法快速排序甚至被誉为世纪科学和工程领域的十大算法之一。我们将讨论比较排序算法的理论基础并中借若干排序算法和优先队列的应用。为了展示初级排序算法性质的价值，我们来看一下基于插入排序的快速的排序算法希尔排序。前言　　排序就是将一组对象按照某种逻辑顺序重新排列的过程。比如信用卡账单中的交易是按照日期排序的——这种排序很可能使用了某种排序算法。在计算时代早期，大家普遍...

Harpsichord1207 2019-08-15 14:50 评论0 收藏0