选择排序图解

举报
VIBE 发表于 2022/10/27 12:16:27 2022/10/27
【摘要】 七大排序之选择排序 前言博主个人社区:开发与算法学习社区博主个人主页:Killing Vibe的博客欢迎大家加入,一起交流学习~~ 一、直接选择排序选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。 1.1 算法图解每次从无序区间选择一个最大或者最小值的一个元素,放在无序区间的最...

七大排序之选择排序

前言

博主个人社区:开发与算法学习社区

博主个人主页:Killing Vibe的博客

欢迎大家加入,一起交流学习~~

一、直接选择排序

选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1.1 算法图解

每次从无序区间选择一个最大或者最小值的一个元素,放在无序区间的最后或者最前,直到待排序的所有元素排序完毕。

在这里插入图片描述
代码如下 :

    public static void selectionSort(int[] arr) {
        // 最开始无序区间[i...n)
        // 有序区间[]
        // 最外层的for循环指的循环走的趟数,每走一趟外层循环,就有一个最小值放在了正确的位置
        for (int i = 0; i < arr.length - 1; i++) {
            // min指的是最小元素的索引下标
            int min = i;
            // 内层循环在查找当前无序区间的最小值索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // j对应的元素比当前最小值还小
                    min = j;
                }
            }
            // min这个变量一定保存了当前无序区间的最小值索引
            // 有序区间[0..i) + 1
            // 无序区间[i..n) - 1
            swap(arr,i,min);
        }
    }

1.2 算法稳定性

拿 9,2,5(a),7,5(b),4,3,6 为例子:

【其中a,b用来标记经过排序后是否改变前后顺序,来检测稳定性】

for(int i = 0 ;i<arr.length ; i++) 【外层循环】

最开始时,待排序的数组(无序区间)为:[i…n)

已排序的数组(有序区间) [ ] => 区间中没有任何元素

==外层每一次排序:==

  • 有序区间 [0…i) +1
  • 无序区间 [i…n) -1

选择无序区间的最小值,放在了无序区间的最开始位置

  1. 进行第一次排序:序列变成:2,9,5(a), 7, 5(b), 4, 3, 6

  2. 进行第二次排序:序列变成:2,3,5(a),7,5(b),4,9,6

  3. 进行第三次排序:序列变成:2,3,4,7,5(b),5(a),9,6

此时5(a)和5(b)的先后顺序就改变了。

选择排序在是排序过程中无法保证相同的元素的先后顺序的。

所以选择排序不是一个稳定性的算法。

二、双向选择排序

之前选择排序一次只能选择一个最小值或者最大值,一次只选一个元素放在正确位置。

我现在一次选两个

每次从无序区间中选出最小值和最大值,存放在无序区间的最开始和最后面位置,重复上述过程~~

代码如下:

    public static void selectionSortOP(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        // low == high => 无序区间只剩下最后一个元素,其实整个数组已经有序了。
        while (low < high) {
            int min = low;
            int max = low;
            for (int i = low + 1; i <= high; i++) {
                if (arr[i] < arr[min]) {
                    min = i;
                }
                if (arr[i] > arr[max]) {
                    max = i;
                }
            }
            // 此时min对应了最小值索引,交换到无序区间的最前面
            swap(arr,min,low);
            // 边界条件 low == max
            if (max == low) {
                max = min;
            }
            swap(arr,max,high);
            low ++;
            high --;
        }
    }

==注意事项:==

注意代码中的边界条件:

 // 边界条件 low == max
            if (max == low) {
                max = min;
            }

解释:

拿一串数字举例:

在这里插入图片描述

正常经过一次过程可以放两个元素到正确位置:

在这里插入图片描述

但是在这个交换过程中:

若恰好max的索引就是low的索引,如图,最大值本来是9,但是经过交换,9到了2原本的位置,此时需要把max索引指针更新为2的位置,也就是min的位置。【不然max还是指向开头的2,那最大值就错了】

在这里插入图片描述

总结

以上就是选择排序的图解和代码,有什么疑问可以私信博主~有帮助的话可以关注博主后续更新。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。