1. 引子
1.1. 为什么要学习数据结构与算法?
有人说, 数据结构与算法, 计算机网络, 与操作系统都一样, 脱离日常开发, 除了面试这辈子可能都用不到呀!
有人说, 我是做业务开发的, 只要熟练 API, 熟练框架, 熟练各种中间件, 写的代码不也能 "飞" 起来吗?
于是问题来了: 为什么还要学习数据结构与算法呢?
# 理由一:
面试的时候, 千万不要被数据结构与算法拖了后腿
# 理由二:
你真的愿意做一辈子 CRUD Boy 吗
# 理由三:
不想写出开源框架, 中间件的工程师, 不是好厨子
1.2. 如何系统化学习数据结构与算法?
我想好了, 还是需要学习数据结构与算法. 但是我有两个困惑:
1. 如何着手学习呢?
2. 有哪些内容要学习呢?
学习方法推荐:
# 学习方法
1. 从基础开始, 系统化学习
2. 多动手, 每一种数据结构与算法, 都自己用代码实现出来
3. 思路更重要: 理解实现思想, 不要背代码
4. 与日常开发结合, 对应应用场景
学习内容推荐:
数据结构与算法内容比较多, 我们本着实用原则, 学习经典的, 常用的数据结构, 与常用算法
# 学习内容:
1. 数据结构的定义
2. 算法的定义
3. 复杂度分析
4. 常用数据结构
数组, 链表, 栈, 队列
散列表, 二叉树, 堆
跳表, 图
5. 常用算法
递归, 排序, 二分查找
搜索, 哈希, 贪心, 分治
动态规划, 字符串匹配
2. 考考你
上一篇: 数据结构与算法系列十二 (插入排序) 中, 我们详细分析了插入排序的核心思想, 和代码实现. 插入排序的核心思想很巧妙: 它是将待排序序列, 分为有序区间, 和无序区间, 循环遍历无序区间, 每一次将无序区间中的第一个元素, 插入到有序区间的合适位置, 每一次插入都要始终保证有序区间有序.
你需要对插入排序的核心思想再仔细琢磨一下, 因为我们今天的主角: 选择排序, 它的核心思想与插入排序类似.
# 考考你:
1. 你知道选择排序的核心思想吗?
2. 你能用 java 代码实现选择排序吗?
3. 你知道实际开发中, 为什么插入排序, 比选择排序更好吗?
3. 案例
3.1. 选择排序核心思想
假设有一个待排序序列:[4, 5, 6, 3, 2, 1]. 我们需要按照升序进行排序, 排序后的序列是这 样的:[1, 2, 3, 4, 5, 6].
如何通过选择排序实现呢?
选择排序核心思想:
将待排序序列, 分成两个区间: 有序区间, 无序区间. 一开始假定有序区间元素个数: 0, 无序区间元素个数: n. 循环遍历无序区间, 每一次从无序区间中, 选择最小的一个元素, 插入到有序区间的末尾.
这里的关键词有:
待排序序列, 分成: 有序区间, 无序区间
最开始, 假定有序区间元素个数: 0, 无序区间元素个数: n
每次循环遍历无序区间, 选择最小元素, 插入到有序区间末尾, 如下图:
3.2. 选择排序代码实现
3.2.1. 排序代码
- /**
- * 选择排序
- * @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;
- }
- }
3.2.2. 测试代码
- /**
- * 选择排序:
- * 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:\02teach\01soft\jdk8\bin\java
- 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
4. 讨论分享
# 考考你答案:
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. 关于选择排序, 不是稳定排序算法的分析, 你可以结合我们前面的图来理解
来源: https://www.cnblogs.com/itall/p/12611509.html