博客

1.选择排序算法含义

表现最稳定的排序算法之一，因为无论什么数据进去都是o(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

选择排序是一种简单直观的排序算法。它的工作原理：首先在未排序的序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.白话理解算法思想

之所以出现选择排序，主要是冒泡排序一直在和相邻的进行对比，比较不灵活，如果是一组学生排队，永远相邻对比进行交换，那不得疯啊！那么有没有别的方式呢？

那么选择排序就派上用场了，如一组同学站在队里，从小到大按个子排序，那么就找到队里个子最矮的小朋友站在第一个位置上，第一个小朋友和最矮的进行交换，在找到第二个矮的小朋友和第二个位置交换，依次类推直到全部从小到大排好队形

借用小灰算法漫画图片

1. 默认第0个坐标是最小的数据叫minindex=0，循环之后的数据和minindex坐标比对，直到有比minindex小的坐标，那么把minindex更改为比对完最小的坐标位置
2. 内层循环知道最小的坐标位置以后，用外层坐标i进行交换位置，因为i是轮数麽。
3. 依次类推，直到排序完毕。

3.算法动态演示

4.算法代码示例

package com.test.sort.simpleSort;

//import com.test.sort.utils;

import java.util.Arrays;

/**
 * @Author df
 * @Date 2019/8/6 12:28
 * @Version 1.0
 * 选择排序
 * 思想：
 * 1.默认就认为给的数组都是无序的，在无序里进行循环
 * 2.循环找到第一小的数据，放到左侧第一个位置。左侧第一个就是有序区
 * 3.再循环第二个小的数据，放到左侧末尾，这里就是第二个位置。
 * 4.循环依次类推，直到所有的数据都进行排序
 * 5.所有的操作都是在一个数组里进行的没有用到额外的空间所以空间复杂度是O(1)
 * 6.时间复杂度是O(n2)
 */
public class selectionSort {
    public static void main(String[] args) {
        int[] arr = {3, 10, 8, 4};
        yhsort(arr);
    }

    /**
     * 优化后的选择排序  6, 9, 8, 1, 4 ｜ 1，9，8，6，4 ｜ 1，4，8，6，9  / 1,4,6,8,9
     * 选择排序
     *
     * @param arr
     */
    public static void yhsort(int[] arr) {
        // 外层循环控制轮数和每一次完整循环的坐标交换使用
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            // 内层循环对比找到一次内部循环最小的数据
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

5.算法复杂度分析

1. 最佳情况：T(n)=O(n2)
2. 最差情况：T(n)=O(n2)
3. 平均情况：T(n)=O(n2)
4. 因为每一次都会进行完整的对比，所以最坏最好都是O(n2)

今日算法学习完毕，有不懂最好是打断点一点一点进行看，或者理解一下思想，自己按照每个排序算法思想进行默写，看看自己能不能写出这些算法。然后再看这些排序算法的代码，就能更加理解了。