作者：敲代码の流川枫

博客主页：流川枫的博客

专栏：和我一起学java

语录：Stay hungry stay foolish

工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网

点击免费注册和我一起刷题吧    

文章目录

1. 算法思想

2. 算法图解

3. 代码实现

4. 选择排序算法的优化

5. 选择排序特点

1. 算法思想

1. 找到数组中最大（小）的那个元素

2. 将它和数组的第一个元素交换位置（如果第一个元素就是最大或者最小的元素，那么就和自己交换位置）

3. 在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置，一直循环，直到整个数组有序

该算法是在不断地选择剩余元素之中最大（小）的元素然后进行排序，因此该算法叫做选择排序

2. 算法图解

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

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

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

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

 假设最小数是33，开始向后遍历，找到最小数15，交换

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

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

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

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

至此排序完成

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

结果：

4. 选择排序算法的优化

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

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

代码： 

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

结果： 

5. 选择排序特点

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

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