选择排序算法（基于Java实现）

2020-12-15

字数统计: 720字 | 阅读时长≈ 3分

选择排序算法（基于Java实现）

选择排序算法原理及代码实现：

一、选择排序算法的原理

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

二、选择排序算法的代码实现

package com.company;

import java.util.Arrays;

public class SelectionSort {

    public static int[] selectionSort(int[] a){
        if(a.length <= 1){
            return a;
        }

        for(int i = 0; i<a.length-1; i++){
            int minIdex = i;

            for(int j = i+1; j< a.length; j++){
                //找到最小数
                if(a[j] < a[minIdex]){
                    //保存最小数的索引
                    minIdex = j;

                }
            }

            //如果一轮比较下来都没有变更最小值得索引则无需调换顺序
            if(i != minIdex){

                int tmp = a[i];
                a[i] = a[minIdex];
                a[minIdex] = tmp;
            }
        }
        return a;
    }

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

        selectionSort(a);
        System.out.println("之后的排序：");
        System.out.println(Arrays.toString(a));
    }
}

输出的结果：

之前的排序：
[10, 9, 7, 4, 3, 2, 1, 8]
之后的排序：
[1, 2, 3, 4, 7, 8, 9, 10]

选择排序的另一种代码写法，更容易理解和记忆。

package TestSort;

import java.util.Arrays;

public class Test_select {

    public static void selectionSort(int[] arr){

        for(int i = 0; i < arr.length - 1; i++){

            int minIndex = i;
            int min = arr[i];

            for(int j = i+1; j <arr.length; j++){
                if(min > arr[j]){
                min = arr[j];//重置min
                minIndex = j;//重置minIndex
                }
            }
            if(minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {23, 43, 3, 32, 67, 78, 34, 56};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));

        selectionSort(arr);

        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }
}

输出结果为：

排序前：
[23, 43, 3, 32, 67, 78, 34, 56]
排序后：
[3, 23, 32, 34, 43, 56, 67, 78]

首先，选择排序空间复杂度为 O(1)**，是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n^2)**。

选择排序是一种不稳定的排序算法。从我前面画的那张图中，你可以看出来，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。

本文作者： feng之锋
本文链接： http://example.com/2020/12/15/选择排序算法/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！