排序算法之选择排序

选择排序(Selection Sort)

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

算法描述

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

算法分析

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
选择排序	O(n²)	O(n²)	O(n²)	O(1)	In-place	不稳定

动图演示

代码实现

public class SelectionSort {

    public static void swap(int[] array, int begin, int end){
        int temp = array[begin];
        array[begin] = array[end];
        array[end] = temp;
    }

    public static void sort(int[] array) {
        
        //存储最大值得下标
        int maxIndex;
        for (int end = array.length - 1; end > 0; end--) {
            maxIndex = 0;
            for (int begin = 1; begin <= end; begin++) {
                if (array[maxIndex] <= array[begin]) {
                    //将当前下标赋值给 maxIndex
                    maxIndex = begin;
                }
            }
            //交换最大值
            swap(array,maxIndex,end);
            System.out.println("第" + (array.length - end) + "次排序： " + Arrays.toString(array));
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 9, 7, 4, 1, 3, 2, 8};
        System.out.println("排序前： " + Arrays.toString(array));
        sort(array);
    }
}

执行结果：

与冒泡排序比较

1. 二者平均时间复杂度都是 O(n²)
2. 选择排序一般要快于冒泡，因为其交换次数少
3. 但如果集合有序度高，冒泡优于选择
4. 冒泡属于稳定排序算法，而选择属于不稳定排序
   • 稳定排序指，按对象中不同字段进行多次排序，不会打乱同值元素的顺序
   • 不稳定排序则反之