排序算法之选择排序

  选择排序算法的流程是这样的:首先,找到数组中最小的那个元素的下标,其次,将次下标上的元素和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。再次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。如此循环往复,直到将整个数组排序。所谓选择就是一直在选择剩余元素中的最小元素。

先上代码:

 1 public static void selectSort(int[] arr) {
 2         for (int i = 0; i < arr.length - 1; i++) {
 3             // 定义最小元素的下标,如果和当前元素相同,就和自己交换。
 4             int min = i;
 5             // 定义临时变量用来交换元素
 6             int tmp = 0;
 7             for (int j = i + 1; j < arr.length; j++) {
 8                 if (arr[j] < arr[i]) {
 9                     min = j;
10                 }
11             }
12             // 交换元素
13             tmp = arr[i];
14             arr[i] = arr[min];
15             arr[min] = tmp;
16         }
17         System.out.println(Arrays.toString(arr));
18     }

上个例子:{10,9,8,7,6,5}

代码运行示意图如下:

其实,从图中可以看出,自己和自己交换这一步完全可以跳过,只要在代码里加上判断就行:

 1     public static void selectSort(int[] arr) {
 2         for (int i = 0; i < arr.length - 1; i++) {
 3             // 定义最小元素的下标,如果和当前元素相同,就和自己交换。
 4             int min = i;
 5             // 定义临时变量用来交换元素
 6             int tmp = 0;
 7             for (int j = i + 1; j < arr.length; j++) {
 8                 if (arr[j] < arr[i]) {
 9                     min = j;
10                 }
11             }
         // 当min等于i的时候,说明arr[i]本身就是最小的,那么就没有必要再和自己交换了。
12 if (min != i) { 13 // 交换元素 14 tmp = arr[i]; 15 arr[i] = arr[min]; 16 arr[min] = tmp; 17 } 18 } 19 System.out.println(Arrays.toString(arr)); 20 }
原文地址:https://www.cnblogs.com/huashui/p/3192046.html