上篇博文介绍插入排序
, 以及插入排序
相比同时间复杂度的冒泡排序存在的优势: 即每个内层循环少了两次变量值交换的赋值过程(所以, 插入排序的效率更优)
本篇博文介绍选择排序
, 类似插入排序, 同样将数据集划分为已排序和未排序区间
还是原地排序(在原数组中或者原集合中进行排序)
时间复杂度: O(n*n)
空间复杂度: O(1)
算法逻辑:
1, 不断在未排序区间内找最小的元素;
2, 每次遍历得到的最小元素, 替换到已排序区间.
代码注释中详细解释了具体逻辑
import org.junit.Test; /** * 功能说明: 选择排序 * 1, 找未排序区间里面找最小的 * 2, 替换 已排序区的最后位置 <--交换--> 未排序区的最小值 * 开发人员:@author MaLi */ public class T02_SeletctionSort { public int[] sort(int[] arr) { // 检测参数 if (arr == null || arr.length <= 1) return arr; //外层逻辑: 变量0到倒数第2位区间, 即[0,length-2], 找最小 (不遍历到length-1这个位置的原因: 只剩一位, 没有大小可比) for (int i = 0; i < arr.length - 1; i++) { //记录下最小值的索引, 用于结果赋值 int minIndex = i; //内层逻辑: 找未排序区间中最小的元素索引, 即区间[i+1,length-1], (之所以左边界为i+1, 如果起始设定在第i个位置, 那浪费一次比较--和自己比没有意义) for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // 在外层遍历中, 把未排序区中最小的放到指定位置 int tmp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = tmp; } return arr; } @Test public void testSort() { int[] arr = {3, 2, 1}; arr = sort(arr); for (int i : arr) { System.out.println(i); } arr = new int[]{1}; arr = sort(arr); for (int i : arr) { System.out.println(i); } arr = new int[]{}; arr = sort(arr); for (int i : arr) { System.out.println(i); } arr = null; arr = sort(arr); //此处返回null System.out.println(arr); } }
分析: 既然插入排序相比冒泡排序, 在同时间复杂度下, 少了两次替换赋值的过程, 性能效率更优, 那么选择排序呢, 是否同样优于冒泡
?
回答: 选择排序同样优于冒泡排序
, 因为在上面代码中, 内层循环仅仅是记录了未排序区间的最小值索引, 在外层循环进行了赋值交换. 冒泡, 是在内层中进行三次赋值交换.