选择排序图解

不念不忘少年蓝@ 2023-09-25 12:21 11阅读 0赞

## 七大排序之选择排序 ##

#### 文章目录 ####

*  七大排序之选择排序
 *  前言
 *  一、直接选择排序
 *   *  1.1 算法图解
     *  1.2 算法稳定性
 *  二、双向选择排序
 *  总结

--------------------

## 前言 ##

> 博主个人社区：[开发与算法学习社区][Link 1]
> 
> 博主个人主页：[Killing Vibe的博客][Killing Vibe]
> 
> 欢迎大家加入，一起交流学习~~

## 一、直接选择排序 ##

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

### 1.1 算法图解 ###

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

![在这里插入图片描述][f1ef4869c17a4546bd3bdc5c2427642e.gif_pic_center]  
**代码如下 ：**

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;
                }

**解释：**

拿一串数字举例：

![在这里插入图片描述][b64ce25068354017854f56a23509344a.png]

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

![在这里插入图片描述][e2c89cdff810480a92b412206a50e00f.png]

**但是在这个交换过程中：**

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

![在这里插入图片描述][8c835e43c78f4fda9b4ca11a6c61eb9e.png]

## 总结 ##

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

[Link 1]: https://bbs.csdn.net/forums/killingvibe?joinKey=bxrj0yyjeyrk-2o9q4217kn-1-a7ba228d3f0db23bd3e669796abef74b
[Killing Vibe]: https://blog.csdn.net/qq_43575801
[f1ef4869c17a4546bd3bdc5c2427642e.gif_pic_center]: https://img-blog.csdnimg.cn/f1ef4869c17a4546bd3bdc5c2427642e.gif#pic_center
[b64ce25068354017854f56a23509344a.png]: https://img-blog.csdnimg.cn/b64ce25068354017854f56a23509344a.png
[e2c89cdff810480a92b412206a50e00f.png]: https://img-blog.csdnimg.cn/e2c89cdff810480a92b412206a50e00f.png
[8c835e43c78f4fda9b4ca11a6c61eb9e.png]: https://img-blog.csdnimg.cn/8c835e43c78f4fda9b4ca11a6c61eb9e.png