选择排序(Selection Sort)

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

算法描述

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

算法分析

动图演示

排序算法之选择排序-LMLPHP

代码实现

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

执行结果:
排序算法之选择排序-LMLPHP

与冒泡排序比较

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