选择排序 【SelectionSort】

本文主要是介绍选择排序 【SelectionSort】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

选择排序

假设初始的数组是[5,4,7,2] 以从小到大排序为例，我们可以将数组分为两个区域，一个是无序区，一个是有序区，在一开始所有的数据都在无序区。

1. 进行第一轮排序，对无序区的数组[5,4,7,2]进行遍历，记录最小值2，然后将它与第0个元素进行位置交换。此时无序数组[4,7,5]，有序数组[1]，原本的数组[1,4,7,5]
2. 进行第二轮排序，对无序区的数组[4,7,5]进行遍历，记录最小值4，然后将它与第1个元素进行位置交换。当然自己本身就处于第一个元素的位置，所以可以不变，此时无序区数组[7,5] ，有序数组[1,4]，原本的数组[1,4,7,5]
3. 进行第三轮排序，对无序区数组[7,5]进行遍历，记录最小值5，然后将它与第2个元素进行位置交换。此时数组[2,4,,5,7]

总结：
1. 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置
2. 重复一过程

算法实现

public class SelecitionSort {public void selectionSort(int[] arr) {if(arr == null || arr.length == 1) {return ;}for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;for (int j = i + 1; j < arr.length; j++) {minIndex = arr[j] < arr[minIndex] ? j : minIndex;}swap(arr, i, minIndex);}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp; }
}

时间复杂度

需要进行n-1次排序(n为数组长度)，每一次排序需要进行n-i次比较(i为当前第几次排序)。所以时间复杂度为 O(N^2)

即使考虑了初始化数据的情况，时间复杂度也是O(N^2), 只是需要交换的次数为0，最坏的情况会交换n-1次。

稳定性

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

这篇关于选择排序 【SelectionSort】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---