【小白学算法】12. 排序算法-选择排序
选择排序(Selection sort)是一种简单直观的排序算法。
它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。
比如说现在有个数组[6,3,5,7,0]
,对其从小到大进行排序,那么选择排序的过程应该是这样的:
从这个过程中可以看出选择排序的一些规则:
•选择排序一共有 数组大小-1
轮。•而在每一轮的排序中,又会有一个小循环,规则是:
1.先假定当前的这个数是最小的。2.然后与后面的每个数进行比较,如果发现有更小的数,重新确定最小的数,并得到这个数的下标。3.继续遍历到数组最后,于是确定出本轮的最小数以及它的下标。4.进行位置交换
推导过程的代码
将数组[101,34,119,1]
从小到大进行排序。
package sort;
import java.util.Arrays;
public class SelectSorting {
public static void main(String[] args) {
int [] arr = {101,34,119,1};
selectSort(arr);
}
// 选择排序
public static void selectSort(int[] arr) {
// 原始数组[101,34,119,1]
// 第一轮排序
int minIndex = 0;
int min = arr[0]; //假定第一个元素就是最小值
for (int j = 0 + 1; j < arr.length; j++) {
if (min > arr[j]) { // 比较,如果是true,那么说明min不是最小值
min = arr[j]; // 重置最小值
minIndex = j; // 重置minIndex
}
}
// 最小值与arr[0]交换位置
if (minIndex != 0) { // 优化点:如果第一个用于比较的元素就是最小值,就不用交换位置
arr[minIndex] = arr[0];
arr[0] = min;
}
System.out.println("第一轮之后:");
System.out.println(Arrays.toString(arr)); // 第一轮之后 [1, 34, 119, 101]
// 第二轮排序
minIndex = 1;
min = arr[1]; //假定第二个元素就是最小值
for (int j = 1 + 1; j < arr.length; j++) {
if (min > arr[j]) { // 比较,如果是true,那么说明min不是最小值
min = arr[j]; // 重置最小值
minIndex = j; // 重置minIndex
}
}
// 最小值与arr[1]交换位置
if (minIndex != 1) {
arr[minIndex] = arr[1];
arr[1] = min;
}
System.out.println("第二轮之后:");
System.out.println(Arrays.toString(arr)); // 第二轮之后 [1, 34, 119, 101]
// 第三轮排序
minIndex = 2;
min = arr[2]; //假定第三个元素就是最小值
for (int j = 2 + 1; j < arr.length; j++) {
if (min > arr[j]) { // 比较,如果是true,那么说明min不是最小值
min = arr[j]; // 重置最小值
minIndex = j; // 重置minIndex
}
}
// 最小值与arr[2]交换位置
if (minIndex != 2) {
arr[minIndex] = arr[2];
arr[2] = min;
}
System.out.println("第三轮之后:");
System.out.println(Arrays.toString(arr)); // 第三轮之后 [1, 34, 101, 119]
}
}
根据推导过程发现的规律,转化成最终的代码:
package sort;
import java.util.Arrays;
public class SelectSorting {
public static void main(String[] args) {
int [] arr = {101,34,119,1};
selectSort(arr);
System.out.println("排序后:");
System.out.println(Arrays.toString(arr));
}
// 选择排序
public static void selectSort(int[] arr) {
// 原始数组[101,34,119,1]
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
int min = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (min > arr[j]) { // 比较,如果是true,那么说明min不是最小值
min = arr[j]; // 重置最小值
minIndex = j; // 重置minIndex
}
}
if (minIndex != i) { // 优化点:如果第一个用于比较的元素就是最小值,就不用交换位置
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
}
如果要从大到小进行排序,很简单,只要改动这里即可:
......
if (min < arr[j]) { // 大于号改成小于号
min = arr[j];
minIndex = j;
}
......
从过程推导再到最后形态,还是比上来直接看2层for循环要好理解的多了。