深入浅出排序算法之简单选择排序

1. 原理和执行流程

2. 代码实现

3. 性能分析

4. 双向选择排序（了解）

1. 原理和执行流程

选择排序包含了堆排序和简单选择排序。

每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完。

选择类排序的主要动作是“选择”，简单选择排序采用最简单的选择方式，从头至尾顺序扫描序列。找出最小的一个关键字，和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终使序列有序。

2. 代码实现

    //选择排序public static void selectSort(int[] array){for(int i = 0;i < array.length - 1;i++){//剩下最后一个元素，不需要选择了，因为已经在最合适的位置boolean flag = false;//用来比较是否更好minIndex的值int j = i + 1;//往后一位进行比较int minIndex = i;for(;j < array.length;j++){if(array[minIndex] > array[j]){minIndex = j;flag = true;}}if(flag){int tmp = array[minIndex];array[minIndex] = array[i];array[i] = tmp;}}}public static void main(String[] args) {int[] arr = {3,1,2,4,5};Sort.selectSort(arr);for (int x : arr) {System.out.print(x + " ");}}

3. 性能分析

时间复杂度	空间复杂度
O(N^2)	O(1)
数据不敏感	数据不敏感

4. 双向选择排序（了解）

每一次从无序区间选出最小 + 最大的元素，存放在无序区间的最前和最后，直到全部待排序的数据元素排完。

    public static void main(String[] args) {int[] arr = {5,2,1,3,4};Sort.selectSortOP(arr);for (int x : arr) {System.out.print(x + " ");}}//双向选择排序//和单向的时间复杂度一致，可能只是更帅一点吧public static void selectSortOP(int[] array){int low = 0;int high = array.length - 1;// [low, high] 表示整个无序区间// 无序区间内只有一个数也可以停止排序了while(low < high){int min = low;int max = low;for(int i = low + 1;i <= high;i++){if (array[i] < array[min]) {min = i;}if(array[i] > array[max]){max = i;}}swap(array,low,min);//见下面解析：最大值可能在low的位置上，min和low一交换，最大值就到了min的位置if(max == low){max = min;}swap(array,high,max);low++;high--;}}

array = { 9, 5, 2, 7, 3, 6, 8 }; // 交换之前
// low = 0; high = 6
// max = 0; min = 2
array = { 2, 5, 9, 7, 3, 6, 8 }; // 将最小的交换到无序区间的最开始后
// max = 0，但实际上最大的数已经不在 0 位置，而是被交换到 min 即 2 位置了
// 所以需要让 max = min 即 max = 2
array = { 2, 5, 8, 7, 3, 6, 9 }; // 将最大的交换到无序区间的最结尾后