java八种排序算法-选择排序

选择排序( select sorting )

介绍

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素， 再依规定交换位置后达到排序的目的。

举个例子:

[8 , 3 , 2 , 1 , 7 , 4 ,6 , 5] 1.从 arr[0],arr[n- 1]中选取最小值，与arr[0]交换， 2. 从ar[1]ar[n- 1]中选取最小值，与arr[1]交换， 3.从arr[2]~ arr[n-1]中选取最小值，与arr[2]交换, 第i次从arr[i-1]arr[n-1]中选取最小值，与arr[i-1]交换. 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换， 总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

思路分析图:

代码实现

---

public class SelectSort { public static void main(String[] args) { int [] arr = {8,3,2,1,7,4,6 ,5}; System.out.println("排序前"); System.out.println(Arrays.toString(arr)); selectSort(arr); System.out.println("排序后"); System.out.println(Arrays.toString(arr)); } //选择排序 public static void selectSort(int[] arr) { //在推导的过程，我们发现了规律，因此，可以使用for来解决 //选择排序时间复杂度是 O(n^2) 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 } } // 将最小值，放在arr[0], 即交换 if (minIndex != i) { arr[minIndex] = arr[i]; arr[i] = min; } System.out.println("第"+(i+1)+"轮后~~"); System.out.println(Arrays.toString(arr)); } } }