图解选择排序算法及优化

​

文章目录

1. 算法思想
2. 算法图解
3. 代码实现
4. 选择排序算法的优化
5. 选择排序特点
6. 算法思想

1. 算法图解

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

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

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

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

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

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

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

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

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

至此排序完成

1. 代码实现

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

}
结果：

1. 选择排序算法的优化

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

遍历数组找到最大值和最小值 ， 将最小值放到数组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));
}

}
结果： 

1. 选择排序特点

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

​