选择排序

关注

发布于: 2020 年 07 月 03 日

  原理：将需要排序的数据划分为已排序区间和未排序区间，初始状态下全部为未排序区间，然后依次从未排序区间的元素中找到最小的值与未排序区间的首位元素进行交换，直到全部排序完成。
﻿
对数组8,5,1,5,3,2,4进行选择排序演示图：
选择排序流程演示
﻿
java代码实现上面的过程如下：
public static void selectionSort(int[] a) {
        if (a == null || a.length == 0) return;
        int length = a.length;
        //当未排序区间只有一个元素的时候这个数组已经是有序不需要再比较了
        for (int i = 0; i < length - 1; ++i) {
            int minValue = a[i];//记录当前最小值
            int minindex = i;//记录最小值所在的索引,交换数据用
            for (int j = i; j < length; ++j) {
                //如果未排序区间存在更小的值更新最小值数据和索引
                if (a[j] < minValue) {
                    minValue = a[j];
                    minindex = j;
                }
            }
            //最后最小值和未排序区间的首位进行位置交换
            swap(a, i, minindex);
        }
    }
    public static void swap(int[] a, int i, int j) {
        if (a[i] != a[j]) {
            a[i] = a[i] ^ a[j];
            a[j] = a[i] ^ a[j];
            a[i] = a[i] ^ a[j];
        }
    }
﻿
总结：
  选择排序是不稳定的排序算法（选择排序的过程是从未排序区间中选择最小值与未排序区间的首位元素进行交换，存在把前面的元素换到后面打乱原有顺序的可能性）
  选择排序的时间复杂度为O(n²)
﻿