[数据结构与算法]数据结构与算法 选择排序

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

package com.sofwin.controller;
?
import java.util.Arrays;

public class SelectionSort {
?
 ? ?public static void main(String[]args){
 ? ? ? ?int[] a = {5,3,7,2,1,9,8,4};
 ? ? ? ?selection(a);
 ?  }
?
 ? ?private ?static ?void ?selection(int[] arr) {
// ? ? ?  数组元素有8个  只需要七轮选择就可以排好序了
 ? ? ? ?for (int i = 0; i < arr.length-1; i++) {
 ? ? ? ? ? ?//i 代表的每轮选择 最小元素要交换的目标索引
 ? ? ? ? ? ?//代表最小元素的索引 ? 假定第一个元素是最小的
 ? ? ? ? ? ?int min = i;
 ? ? ? ? ? ?for (int j = min + 1; j < arr.length; j++) {
 ? ? ? ? ? ? ? ?if (arr[min] > arr[j]) {
 ? ? ? ? ? ? ? ? ? ?//每次都把最小元素的索引赋值给min
 ? ? ? ? ? ? ? ? ? min = j;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ?  }
 ? ? ? ? ? ?//如果min不能i 代表找到最小的了  进行交换
 ? ? ? ? ? ?if (min != i) {
 ? ? ? ? ? ? ? ?swap(arr,min,i);
 ? ? ? ? ?  }
 ? ? ? ? ? ?System.out.println("第"+(i+1)+"轮选择："+Arrays.toString(arr));
 ? ? ?  }
 ?  }
?
 ? ?public static ?void swap(int[] arr, int i, int j) {
 ? ? ? ?int temp = arr[i];
 ? ? ? ?arr[i] = arr[j];
 ? ? ? ?arr[j] = temp;
?
 ?  }
}

?

冒泡排序和选择排序的比较

1. 两者的平均时间复杂度都为O（n^2）

2. 一般选择排序要快于冒泡排序 ，因为其交换次数少

3. 但如果集合有序度高 ，冒泡优于选择 （例如当已经拍好序了，冒泡能判断出来然后结束，但是选择是无法判断的 ，因此这个时候冒泡是优于选择的）

4. 冒泡属于稳定排序算法，选择属于不稳定排序算法

5. 不稳定是 数值相同的元素 排好序后可能 可能位置会发生改变

   例如 1,3【前】，2,3【后】,5,4

   不稳定排序过后可能出现 1,2,3【后】，3【前】，4,5 这种情况

   稳定排序过后 只会出现 1，2,3【前】,3【后】，4,5 这种情况