选择排序图解

简介: 选择排序图解

七大排序之选择排序

前言

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

博主个人主页: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,那最大值就错了】

在这里插入图片描述

总结

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

相关文章
|
6月前
|
算法 搜索推荐 Java
图解冒泡排序
图解冒泡排序
43 4
|
20天前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
13 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
存储
图解:非递归实现快速排序
方法的调用实际是使用了方法调用栈。递归不就是方法调用本身就是入栈和出栈的过程吗。如果是这样的话,我们就可以使用栈来替换之前的递归,在栈中存储方法每次传入的参数即可。
129 0
图解:非递归实现快速排序
|
算法
【二分查找】详细图解
【二分查找】详细图解
164 0
冒泡排序图解
冒泡排序图解
60 0
|
搜索推荐
排序算法图解(二):选择排序
文章目录 1 选择排序简介 2 图解选择排序算法 3 选择排序代码实现 写在最后
排序算法图解(二):选择排序
|
算法 搜索推荐
排序算法图解(三):插入排序
文章目录 1 插入排序简介 2 插入排序思想及图解 3 插入排序代码实现 写在最后
排序算法图解(三):插入排序
|
搜索推荐 算法 Shell
排序算法图解(四):希尔排序
文章目录 1 希尔排序简介 2 希尔排序算法图解 3 希尔排序代码实现
排序算法图解(四):希尔排序
|
搜索推荐 算法
排序算法图解(一):冒泡排序与冒泡排序的优化
文章目录 1 冒泡排序简介 2 图解算法 3 冒泡排序代码实现 4 冒泡排序算法的优化 写在最后
排序算法图解(一):冒泡排序与冒泡排序的优化
|
算法 搜索推荐
插入排序图解
插入排序图解
101 0
插入排序图解