详解选择排序

2020年3月25日15:09:00算法评论36阅读模式

基本思想

选择排序的思想是:
给定一个数组arr,其长度为n;
第一次从 arr[0] 到 arr[n-1] 中选取一个最值(按照需求,可以是最大值,可以是最小值,下同)与arr[0]进行交换;
第二次从arr[1] 到 arr[n-1] 中选取一个最值与arr[1]进行交换;
以此类推,直到arr[n-2]到arr[n-1]中选出最值交换后即完成排序。(只剩下一个元素,前面的都是比它小(或者大)的)。文章源自随机的未知-https://sjdwz.com/11138.html

例子

给定数组 arr 为 [ 300, 50 , 120 , 110 ];
则其初始状态为:
详解选择排序文章源自随机的未知-https://sjdwz.com/11138.html

定义两个变量minIndexmin,分别表示最小值元素的索引,和最小值元素的值。
先假定最小值元素为循环开始的第一个元素。
第一次循环将minIndexmin分别赋值为 0300
循环变量为当前元素的下一个元素的索引。
由图来演示算法过程:
黄色表示当前循环需要遍历的元素。文章源自随机的未知-https://sjdwz.com/11138.html

第一趟排序文章源自随机的未知-https://sjdwz.com/11138.html

详解选择排序
第一趟排序状态1

此时 50 < min当前值300,将minIndex赋值为1,将min赋值为50;文章源自随机的未知-https://sjdwz.com/11138.html

详解选择排序
循环变量向后移动。文章源自随机的未知-https://sjdwz.com/11138.html

详解选择排序
第一趟排序状态3

此时 120 > min当前值50,循环变量直接向后移动;文章源自随机的未知-https://sjdwz.com/11138.html

详解选择排序
第一趟排序状态4

此时 110 > min当前值50,循环变量无法向后移动,当前循环结束。文章源自随机的未知-https://sjdwz.com/11138.html

minIndex不等于循环开始前的首元素的索引0,发生交换。文章源自随机的未知-https://sjdwz.com/11138.html

详解选择排序
第一趟排序状态5

第二趟排序文章源自随机的未知-https://sjdwz.com/11138.html

详解选择排序
第二趟排序状态1

此时 120 > min当前值100,循环变量直接向后移动;文章源自随机的未知-https://sjdwz.com/11138.html

详解选择排序
第二趟排序状态2

此时 120 > min当前值110,循环变量向后移动则会发生越界,当前循环结束。文章源自随机的未知-https://sjdwz.com/11138.html

minIndex等于循环开始前的首元素的索引1,不发生交换。文章源自随机的未知-https://sjdwz.com/11138.html

第三趟排序文章源自随机的未知-https://sjdwz.com/11138.html

详解选择排序
第三趟排序状态1

此时 110 < min当前值120,将minIndex赋值为3,将min赋值为110;文章源自随机的未知-https://sjdwz.com/11138.html

详解选择排序
第三趟排序状态2

循环变量再向后移动则会发生越界,当前循环结束。文章源自随机的未知-https://sjdwz.com/11138.html

minIndex不等于循环开始前的首元素的索引2,发生交换。文章源自随机的未知-https://sjdwz.com/11138.html

详解选择排序
第三趟排序状态3

因为前n-1个元素均排序完毕,所以原数组排序完毕。文章源自随机的未知-https://sjdwz.com/11138.html

我们由例子可知:
选择排序的趟数为数组长度-1文章源自随机的未知-https://sjdwz.com/11138.html

代码

由上面的讲解知道要写成双重循环,最终代码如下:文章源自随机的未知-https://sjdwz.com/11138.html

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int [] arr = new int[]{300,50,120,110};
        System.out.println("排序前的数组" + Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序前的数组" + Arrays.toString(arr));
    }
    public static void selectSort(int[] arr){

        int minIndex;//最小值元素索引
        int min;//最小值元素
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            //交换
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }
}

时间复杂度

比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1= 。为 。文章源自随机的未知-https://sjdwz.com/11138.html

稳定性

选择排序是不稳定的排序算法
举个例子来说明:
序列 6 9 6 3 10
在第一趟排序时第一个6会和3交换位置,那么原序列中两个6的相对前后顺序就被破坏了。
所以选择排序是一个不稳定的排序算法。文章源自随机的未知-https://sjdwz.com/11138.html

欢迎关注

欢迎大家的关注文章源自随机的未知-https://sjdwz.com/11138.html

扫描下方的二维码或者微信搜一搜即可关注我的微信公众号:随机的未知
详解选择排序文章源自随机的未知-https://sjdwz.com/11138.html

文章源自随机的未知-https://sjdwz.com/11138.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
算法最后更新:2022-2-24
  • 本文由 发表于 2020年3月25日15:09:00
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11138.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定