算法学习(二)—— 选择排序
2021/7/5 22:22:39
本文主要是介绍算法学习(二)—— 选择排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
系列文章目录
第一章:二分查找及大O表示法
第二章:选择排序
文章目录
- 系列文章目录
- 前言
- 一、数组和链表
- 1、链表
- 2、数组
- 二、选择排序
- 3、总结
前言
积累算法,记录学习
一、数组和链表
1、链表
链表中的元素可以储存在内存的任何地方。链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。
插入元素是链表的优势,因为它不需要进行元素的移动,只需要变动插入位置前后的地址索引即可。但是缺点也很明显,无法快速获取某个元素的位置,都需要从头进行索引查询。
2、数组
数组储存了一系列的数,而且你可以轻松get每个元素的位置和每个位置的元素,但它的缺点就是插入元素时需要移动后面所有元素的位置,从而造成时间的消耗。
下面给出了常见的数组和链表的操作时间:
数组 | 链表 | |
---|---|---|
读取 | O(1) | O(n) |
插入 | O(n) | O(1) |
既然数组列表各有好坏,因此选择的时候我们看具体的需求是什么,从而去选择用什么来存储数据
小知识:Facebook存储数据时使用了一种混合数据:链表数组。感兴趣的小伙伴可以去了解一下。
二、选择排序
假设我们有一组无序的数,需要将其进行从小到大排列,简单的做法是进行一次遍历选出最大值,然后pop出最大值,再进行下一遍遍历,以此类推直到选完,这样的简单排序算法复杂度是O(n2):
>>> def Sort(arr): new_arr = [] for i in range(len(arr)): min_arr = arr[0] arr_index = 0 for j in range(len(arr)): if arr[j] < min_arr: min_arr = arr[j] arr_index = j new_arr.append(min_arr) arr.pop(arr_index) return new_arr >>> Sort([9,4,1,3,6,2]) [1, 2, 3, 4, 6, 9]
采用选择排序:
>>> def findSmallest(arr): smallest = arr[0] smallest_index = 0 for i in range(1, len(arr)): if arr[i] < smallest: smallest = arr[i] smallest_index = i return smallest_index >>> def selectionSort(arr): newArr = [] for i in range(len(arr)): smallest = findSmallest(arr) newArr.append(arr.pop(smallest)) return newArr >>> selectionSort([9,4,1,3,6,2]) [1, 2, 3, 4, 6, 9]
3、总结
- 数组元素都在一起
- 链表元素可以分散存储,但其中每个元素都存储了下一个元素的地址
- 数组的读取速度很快
- 列表的插入和删除速度很快
- 在同一个数组中,所有的元素类型必须相同。
这篇关于算法学习(二)—— 选择排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)