图解选择排序算法及优化

小灰灰 2023-10-10 14:49 54阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 2]

文章目录

1. 算法思想

2. 算法图解

3. 代码实现

4. 选择排序算法的优化

5. 选择排序特点

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

## ![556b41a70265423492026022f8a28ac6.png][] ##

## 1. 算法思想 ##

> 1. 找到数组中最大（小）的那个元素
> 
> 2. 将它和数组的第一个元素交换位置（如果第一个元素就是最大或者最小的元素，那么就和自己交换位置）
> 
> 3. 在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置，一直循环，直到整个数组有序
> 
> 该算法是在不断地选择剩余元素之中最大（小）的元素然后进行排序，因此该算法叫做选择排序

## 2. 算法图解 ##

以数组array图解选择排序，排序结果为升序

int[] array = {25,33,10,15,70,45};

![2ff6cda2526f4aa4ab79796c2bc0f128.png][]

假设每个循环开始第一个数是总是最小，minIndex保存最小数的下标i，i范围：从0开始到array.length-1

![056d85db906541e78c82629d4039cc1f.png][]

开始遍历数组，找到最小的数，将索引保存并且交换最小数和当前minIndex所指向的数

![9b44579547c644c9a04719e647512861.png][]

假设最小数是33，开始向后遍历，找到最小数15，交换![4cf0d2ce5fd44c65b85548da1ccc346c.png][]

![7d09b02125b84ef1937a8e898bbac28b.png][]

继续循环，25当前是最小，自己和自己交换

![7299c8a3e27e46cb9582b960f1c3116e.png][]

继续循环，33当前是最小，自己和自己交换

![3241b12b3dfb4567918d90dda48fdb32.png][]

继续循环，最小数是45，和70交换

![964b4e51823c435d9a6ac4755c29bc04.png][]

![fdb0ee8e438f4747b0d21d0ee6bd2ad3.png][]

继续循环，70当前是最小，自己和自己交换![b3a5e987c8884dd49ace80d84efda6c6.png][]

至此排序完成

![75143ba734f14f3cabf8a35d6db8dad3.png][]

## 3. 代码实现 ##

import java.util.Arrays;
    
    public class ChoiceSort{
        public int[] sortArray(int[] nums){
            if(nums.length == 0){
                return nums;
            }
            for (int i = 0; i < nums.length; i++) {
                int minIndex = i;//最小数的下标，每个循环开始总是假设第一个数是最小数
                for (int j = i; j < nums.length; j++) {
                    if (nums[j] < nums[minIndex]){//找到最小数
                        minIndex = j;//保存最小数索引
                    }
                }
                System.out.println("本轮最小数："+nums[minIndex]);
                //交换最小数和当前i所指向的元素
                int tmp = nums[minIndex];
                nums[minIndex] = nums[i];
                nums[i] = tmp;
                PrintArray.print(nums);
                System.out.println("————————————————");
            }
            return nums;
        }
        public static void main(String[] args) {
            int[] array = {25,33,10,15,70,45};
            System.out.println("初始数组：");
            PrintArray.print(array);
            ChoiceSort choiceSort = new ChoiceSort();
            choiceSort.sortArray(array);
            System.out.println("排序完成");
            PrintArray.print(array);
        }
    }
    class PrintArray{
        public static void print(int[] array){
            System.out.println(Arrays.toString(array));
        }
    }

结果：

![3352c140a09a4cfda67b273ba182ceaa.png][]

## 4. 选择排序算法的优化 ##

思路：一般是在一趟遍历中，同时找出最大值与最小值，放到数组两端，这样就能将遍历的趟数减少一半

![74671e65796e4c21951915c235f12139.png][]

遍历数组找到最大值和最小值 ， 将最小值放到数组left处，将最大值放到数组right处，然后继续重复操作，直至排序完成

![d069e0695a7947799d8bfd181b29b980.png][]

![0754a3f05ab2412e85e841a560544bc9.png][]

代码：

import java.util.Arrays;
    
    public class ChoiceSort{
        public int[] sortArray(int[] nums) {
            if (nums.length == 0) {
                return nums;
            }
            /*初始化左端、右端元素索引*/
            int left = 0;
            int right = nums.length - 1;
            while (left < right) {
                /*初始化最小值、最大值元素的索引*/
                int min = left;
                int max = right;
                for (int i = left; i <= right; i++) {
                    /*标记每趟比较中最大值和最小值的元素对应的索引min、max*/
                    if (nums[i] < nums[min])
                        min = i;
                    if (nums[i] > nums[max])
                        max = i;
                }
                /*最大值放在最右端*/
                int temp = nums[max];
                nums[max] = nums[right];
                nums[right] = temp;
                /*此处是先排最大值的位置，所以得考虑最小值（arr[min]）在最大位置（right）的情况*/
                if (min == right)
                    min = max;
                /*最小值放在最左端*/
                temp = nums[min];
                nums[min] = nums[left];
                nums[left] = temp;
                /*每趟遍历，元素总个数减少2，左右端各减少1，left和right索引分别向内移动1*/
                left++;
                right--;
            }
    
            return nums;
        }
        public static void main(String[] args) {
            int[] array = {25,33,10,15,70,45};
            System.out.println("初始数组：");
            PrintArray.print(array);
            ChoiceSort choiceSort = new ChoiceSort();
            choiceSort.sortArray(array);
            System.out.println("排序完成");
            PrintArray.print(array);
        }
    }
    class PrintArray{
        public static void print(int[] array){
            System.out.println(Arrays.toString(array));
        }
    }

结果：

![b11891b3bf4e4353a89c1cb8e10fdf57.png][]

## 5. 选择排序特点 ##

待排序序列中，元素个数较少时，适合选用选择排序，时间复杂度为O(n2)  
  在选择排序中，每趟都会选出最大元素与最小元素，然后与两端元素交换，此时，待排序序列中如果存在与原来两端元素相等的元素，稳定性就可能被破坏

> “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

![ced485cbb11e458d81a746890b32cf3f.gif][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[556b41a70265423492026022f8a28ac6.png]: https://img-blog.csdnimg.cn/556b41a70265423492026022f8a28ac6.png
[2ff6cda2526f4aa4ab79796c2bc0f128.png]: https://img-blog.csdnimg.cn/2ff6cda2526f4aa4ab79796c2bc0f128.png
[056d85db906541e78c82629d4039cc1f.png]: https://img-blog.csdnimg.cn/056d85db906541e78c82629d4039cc1f.png
[9b44579547c644c9a04719e647512861.png]: https://img-blog.csdnimg.cn/9b44579547c644c9a04719e647512861.png
[4cf0d2ce5fd44c65b85548da1ccc346c.png]: https://img-blog.csdnimg.cn/4cf0d2ce5fd44c65b85548da1ccc346c.png
[7d09b02125b84ef1937a8e898bbac28b.png]: https://img-blog.csdnimg.cn/7d09b02125b84ef1937a8e898bbac28b.png
[7299c8a3e27e46cb9582b960f1c3116e.png]: https://img-blog.csdnimg.cn/7299c8a3e27e46cb9582b960f1c3116e.png
[3241b12b3dfb4567918d90dda48fdb32.png]: https://img-blog.csdnimg.cn/3241b12b3dfb4567918d90dda48fdb32.png
[964b4e51823c435d9a6ac4755c29bc04.png]: https://img-blog.csdnimg.cn/964b4e51823c435d9a6ac4755c29bc04.png
[fdb0ee8e438f4747b0d21d0ee6bd2ad3.png]: https://img-blog.csdnimg.cn/fdb0ee8e438f4747b0d21d0ee6bd2ad3.png
[b3a5e987c8884dd49ace80d84efda6c6.png]: https://img-blog.csdnimg.cn/b3a5e987c8884dd49ace80d84efda6c6.png
[75143ba734f14f3cabf8a35d6db8dad3.png]: https://img-blog.csdnimg.cn/75143ba734f14f3cabf8a35d6db8dad3.png
[3352c140a09a4cfda67b273ba182ceaa.png]: https://img-blog.csdnimg.cn/3352c140a09a4cfda67b273ba182ceaa.png
[74671e65796e4c21951915c235f12139.png]: https://img-blog.csdnimg.cn/74671e65796e4c21951915c235f12139.png
[d069e0695a7947799d8bfd181b29b980.png]: https://img-blog.csdnimg.cn/d069e0695a7947799d8bfd181b29b980.png
[0754a3f05ab2412e85e841a560544bc9.png]: https://img-blog.csdnimg.cn/0754a3f05ab2412e85e841a560544bc9.png
[b11891b3bf4e4353a89c1cb8e10fdf57.png]: https://img-blog.csdnimg.cn/b11891b3bf4e4353a89c1cb8e10fdf57.png