java算法基础——选择排序及优化

首先是标准的选择排序算法(时间复杂度O(n2))：

 1 public static void sortLow(int[] array) {
 2         int count = 0;
 3         for (int i = 0; i < array.length - 1; i++) {
 4             int min_pos = i;
 5             for (int j = i; j < array.length; j++) {
 6                 if (array[min_pos] > array[j]) {
 7                     min_pos = j;
 8                 }
 9                 count++;
10             }
11             swap(array, min_pos, i);
12         }
13         printArray(array, count);
14     }

然后是自己优化过的选择排序算法：

 1 public static void sortBetter(int[] array) {
 2         int count = 0;
 3         for (int i = 0; i < array.length / 2; i++) {
 4             int min_pos = i;
 5             int max_length = array.length - (1 + i);
 6             int max_pos = max_length;
 7 
 8             for (int j = i + 1; j < array.length - i; j++) {
 9                 if (array[min_pos] > array[j]) {
10                     min_pos = j;
11                 }
12                 if (array[max_pos] < array[array.length - j - 1]) {
13                     max_pos = array.length - j - 1;
14                 }
15                 count++;
16             }
17             if (min_pos != i) {
18                 swap(array, min_pos, i);
19             }
20             if (i == max_pos) {
21                 swap(array, min_pos, max_length);
22             } else {
23                 swap(array, max_pos, max_length);
24             }
25         }
26         printArray(array, count);
27     }

PS: swap交换两个item位置，print的时候打印了一下循环次数。哪里还有优化的空间可指出，学习交流。