选择排序【Java实现】

选择排序

基本介绍

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

选择排序思想:

选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值， 与 arr[0]交换，第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，第三次从 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 static void main(String[] args) { int arr[] = new int[]{101,34,119,1}; System.out.println("排序前"); System.out.println(Arrays.toString(arr)); selectSort(arr); } public static void selectSort(int[] arr){ //第1轮 //原始数组： 101,34,119,1 //第一轮排序： 1,34,119,101 int minIndex = 0; //先假定最小值的数组索引是0； int min = arr[0]; //假定数组的第一个元素是最小值 for (int j = 0+1;j<arr.length;j++){ if (min > arr[j]){ //说明假定的最小值 并不是最小 min = arr[j]; //重置最小值 minIndex = j; //重置最小值的下标 } } //将最小值，放在arr[0],即交换 if (minIndex!=0){ arr[minIndex] = arr[0]; arr[0] = min; } System.out.println("第一轮后"); System.out.println(Arrays.toString(arr)); //第二轮排序：第一个最小值已经确定 minIndex = 1; //由于第一轮已经把最小值确定，并放在第[0]位，所以第二轮假定最小值的数组索引是1； min = arr[1]; //假定数组的第二个元素是最小值 for (int j = 2;j<arr.length;j++){ if (min > arr[j]){ //说明假定的最小值 并不是最小 min = arr[j]; //重置最小值 minIndex = j; //重置最小值的下标 } } //将最小值，放在arr[1],即交换 if (minIndex!=1){ arr[minIndex] = arr[1]; arr[1] = min; } System.out.println("第二轮后"); System.out.println(Arrays.toString(arr)); //第三轮：前两个元素已经确定 minIndex = 2; //第三轮假定最小值的数组索引是2； min = arr[2]; //假定数组的第三个元素是最小值 for (int j = 3;j<arr.length;j++){ if (min > arr[j]){ //说明假定的最小值 并不是最小 min = arr[j]; //重置最小值 minIndex = j; //重置最小值的下标 } } //将最小值，放在arr[2],即交换 if (minIndex!=2){ arr[minIndex] = arr[2]; arr[2] = min; } System.out.println("第三轮后"); System.out.println(Arrays.toString(arr)); }

运行结果：

排序前 [101, 34, 119, 1] 第一轮后 [1, 34, 119, 101] 第二轮后 [1, 34, 119, 101] 第三轮后 [1, 34, 101, 119]

---

实现选择排序：

public static void main(String[] args) { int arr[] = new int[]{101,34,119,1,20}; System.out.println("排序前"+Arrays.toString(arr)); System.out.println(); selectSort(arr); } public static void selectSort(int[] arr){ for (int i=0;i<arr.length-1;i++){ int minIndex = i; //先假定最小值的数组索引是0； int min = arr[i]; //假定数组的第一个元素是最小值 for (int j = i+1;j<arr.length;j++){ //第一个数已经假定是最小值，所以从第二个数开始遍历 if (min > arr[j]){ //说明假定的最小值 并不是最小 min = arr[j]; minIndex = j; } } if (minIndex!=i){ arr[minIndex] = arr[i];//交换 arr[i] = min; //交换 } System.out.println("第"+(i+1)+"轮排序后"+Arrays.toString(arr)); } }

运行结果：

排序前[101, 34, 119, 1, 20] 第1轮排序后[1, 34, 119, 101, 20] 第2轮排序后[1, 20, 119, 101, 34] 第3轮排序后[1, 20, 34, 101, 119] 第4轮排序后[1, 20, 34, 101, 119]

---

选择排序(select sort):每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

选择排序与冒泡排序有何异同？

区别在于：在交换的方式上

冒泡算法，每次比较如果发现较小zhi的元素在后面，就交换两个相邻的元素。

而选择排序算法的改进在于：先并不急于调换位置，先从A[1]开始逐个检查，看哪个数最小就记下该数所在的位置P，等一躺扫描完毕，再把A[P]和A[1]对调，这时A[1]到A[10]中最小的数据就换到了最前面的位置。

所以，选择排序每扫描一遍数组，只需要一次真正的交换，而冒泡可能需要很多次。比较的次数一样的。