数据结构与算法系列十三（选择排序）
- 2020 年 4 月 1 日
- 筆記
有人说，数据结构与算法，计算机网络，与操作系统都一样，脱离日常开发，除了面试这辈子可能都用不到呀！
有人说，我是做业务开发的，只要熟练API，熟练框架，熟练各种中间件，写的代码不也能“飞”起来吗？
于是问题来了：为什么还要学习数据结构与算法呢？
#理由一： 面试的时候，千万不要被数据结构与算法拖了后腿 #理由二： 你真的愿意做一辈子CRUD Boy吗 #理由三： 不想写出开源框架，中间件的工程师，不是好厨子
我想好了，还是需要学习数据结构与算法。但是我有两个困惑：
1.如何着手学习呢？
2.有哪些内容要学习呢？
学习方法推荐：
#学习方法 1.从基础开始，系统化学习 2.多动手，每一种数据结构与算法，都自己用代码实现出来 3.思路更重要：理解实现思想，不要背代码 4.与日常开发结合，对应应用场景
学习内容推荐：
数据结构与算法内容比较多，我们本着实用原则，学习经典的、常用的数据结构、与常用算法
#学习内容： 1.数据结构的定义 2.算法的定义 3.复杂度分析 4.常用数据结构 数组、链表、栈、队列 散列表、二叉树、堆 跳表、图 5.常用算法 递归、排序、二分查找 搜索、哈希、贪心、分治 动态规划、字符串匹配
上一篇：数据结构与算法系列十二（插入排序）中，我们详细分析了插入排序的核心思想，和代码实现。插入排序的核心思想很巧妙：它是将待排序序列，分为有序区间，和无序区间，循环遍历无序区间，每一次将无序区间中的第一个元素，插入到有序区间的合适位置，每一次插入都要始终保证有序区间有序。
你需要对插入排序的核心思想再仔细琢磨一下，因为我们今天的主角：选择排序，它的核心思想与插入排序类似。
#考考你： 1.你知道选择排序的核心思想吗？ 2.你能用java代码实现选择排序吗？ 3.你知道实际开发中，为什么插入排序，比选择排序更好吗？
假设有一个待排序序列：[4, 5, 6, 3, 2, 1]。我们需要按照升序进行排序，排序后的序列是这 样的：[1, 2, 3, 4, 5, 6]。
如何通过选择排序实现呢？
选择排序核心思想：
将待排序序列，分成两个区间：有序区间、无序区间。一开始假定有序区间元素个数：0，无序区间元素个数：n。循环遍历无序区间，每一次从无序区间中，选择最小的一个元素，插入到有序区间的末尾。
这里的关键词有：
1.待排序序列，分成：有序区间、无序区间 2.最开始，假定有序区间元素个数：0，无序区间元素个数：n 3.每次循环遍历无序区间，选择最小元素，插入到有序区间末尾，如下图：
/** * 选择排序 * @param array：待排序数组 * @param n：待排序数组大小 */ public static void sort(Integer [] array,int n) { // 如果排序数组规模小于等于1，直接返回 if (n <= 1) { return; } // 将待排序数组，分为：有序区间、无序区间 // 一开始，假设整个序列都无序，那么有序区间的元素个数是：0 // 无序区间的元素个数是：n // 每次从无序区间中，选择最小元素 // 插入有序区间末尾：n个元素，n次选择 for(int i = 0; i < n; i++){ // 从无序区间第一个位置开始查找：最小元素位置 int min = i; for(int j = i+1; j < n; j++){ // 比较大小，设定新的最小元素位置标记 if(array[min] > array[j]){ min = j; } } // 找到新的最小元素位置后，进行数据交换 System.out.println("第【"+(i+1)+"】次选择，最小元素是："+array[min]); int tmp = array[i]; array[i] = array[min]; array[min] = tmp; } }
/** * 选择排序： * 1.时间复杂度： * O(n^2) * 2.空间复杂度： * O(1)是原地排序算法 * 3.算法稳定性： * 不是稳定排序算法 */ public static void main(String[] args) { // 初始化测试数组 Integer[] array = {4,5,6,3,2,1}; // 排序前 System.out.println("1.排序前数组：" + Arrays.deepToString(array)); // 排序 System.out.println("2.开始排序-------------------------------start"); sort(array,array.length); // 排序后 System.out.println("3.排序后数组：" + Arrays.deepToString(array)); }
测试结果：
D: 2teach 1softjdk8binjava com.anan.algorithm.sort.SelectSort 1.排序前数组：[4, 5, 6, 3, 2, 1] 2.开始排序-------------------------------start 第【1】次选择，最小元素是：1 第【2】次选择，最小元素是：2 第【3】次选择，最小元素是：3 第【4】次选择，最小元素是：4 第【5】次选择，最小元素是：5 第【6】次选择，最小元素是：6 3.排序后数组：[1, 2, 3, 4, 5, 6] Process finished with exit code 0
#考考你答案： 1.你知道选择排序的核心思想吗？ 1.1.将待排序序列，分成：有序区间、无序区间 1.2.最开始，有序区间元素个数：0，无序区间元素个数：n 1.3.循环遍历无序区间，每次选择最小元素，插入有序区间末尾 2.你能用java代码实现选择排序吗？ 2.1.参考【3.2】节代码实现 3.你知道实际开发中，为什么插入排序，比选择排序更好吗？ 3.1.我们在排序算法概述中说过，衡量一个排序算法的优劣， 有三个因素：时间复杂度、空间复杂度、是否稳定 3.2.插入排序与选择排序，它们的时间复杂度都是：O(n^2) 3.3.插入排序与选择排序，它们的空间复杂度都是：O(1) 3.3.插入排序，是稳定的排序算法 3.4.【注意】：选择排序，不是稳定排序算法 3.5.假设有一个待排序序列：int a[]={4,5,6,4,3,2,1} 3.6.待排序序列中，有重复元素：a[0]=4,a[3]=4 3.7.第一轮选择排序，选择最小元素：a[6]=1 3.8.将a[0]=4,a[6]=1进行交换 3.9.【注意】：第一轮选择排序后，重复元素4的顺序发生了改变 3.10.待排序序列变成：a[]={1,5,6,4,3,2,4} 3.11.此时重复元素：a[3]=4,a[6]=4 3.12.a[3]还是原来的a[3],a[6]是原来的a[0] 3.13.我们说稳定排序算法，是指待排序序列中重复元素， 排序前的顺序，与排序后的顺序保持不变 3.14.可见选择排序，不符合稳定排序算法的定义 3.15.关于选择排序，不是稳定排序算法的分析，你可以结合我们前面的图来理解
