经典排序算法之选择排序
经典排序算法之选择排序
java代码实现
public class Main{private static int[] selectionSort(int[] arr) {if(arr.length <= 1){return arr;}// 外层循环,每循环一次排好一个位置的数for (int i=0; i<arr.length-1; i++){// 记录i位置后最小数的下标int minIndex = i;// 内层循环,比较,记录最小值下标for (int j = i+1; j< arr.length; j++){// 有最小值产生,记录最小数下标if(arr[j] < arr[minIndex]){minIndex = j;}}// 交换i位置与最小值位置if (minIndex != i) {int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}}return arr;}public static void main(String args[]) {int[] arr = {10,5,9,7,6,3,8,2};selectionSort(arr);for (int i = 0;i<arr.length;i++) {System.out.print(arr[i] + " ");}}}
工作原理
通过两层循环实现排序;
外层循环的第i次循环会找到数组中i位置上正确的数并与i位置交换,保证数组0-i位置上的数变成有序,注意i从0开始,由于java中数组的下标从0开始;
内层循环开始前会初始化最小值的索引minIndex为i,从i+1的位置开始,拿当前下标位置的数与最小值比较,如果有更小的数产生,则将minIndex赋值为更小值的下标,直到比较完数组中最后一个数后,将下标为minIndex的数与i位置上的数交换位置,如果比较完i位置后的所有数,minIndex还是i,则不需要交换位置,说明i位置已经是排序好的.
当外层循环i到数组长度n-1的时候,表示已经完成所有排序.
时间复杂度
选择排序的交换操作介于 0 和 (n - 1)次之间,比较操作为 n (n - 1) / 2 次,最坏情况交换n-1次，逆序交换n/2次,时间复杂度为o(n^2).
空间复杂度
只使用了几个临时变量,所以空间复杂度为O(1).
稳定性
如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了,所以选择排序是不稳定的排序方法.