7

【图解数据结构】 一组动画彻底理解选择排序

 3 years ago
source link: https://www.cxyxiaowu.com/2165.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

【图解数据结构】 一组动画彻底理解选择排序

由于LeetCode上的算法题很多涉及到一些基础的数据结构，为了更好的理解后续更新的一些复杂题目的动画，推出一个新系列 —–《图解数据结构》，主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

  1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

  3. 重复第二步，直到所有元素均排序完毕。

来源：https://github.com/hustcc/JS-Sorting-Algorithm

【图解数据结构】 一组动画彻底理解选择排序

排序动画过程解释

  1. 线性搜索数列并找到最小值，此时找到了为 2

  2. 将最小值替换为数列中左端的数字，即将 2 与 4 进行交换

  3. 此时 2 已经排序好

  4. 继续线性搜索剩余数列找到最小值，此时找到了 3

  5. 将最小值替换为数列中左端的数字，即将 3 与 4 进行交换

  6. 此时 2 与 3 已经排序好

  7. 继续线性搜索剩余数列找到最小值，此时找到了 4

  8. 如果最小值已经在左端，那么不执行任何操作，所以此时不做任何处理

  9. 此时 2 、 3  、 4 已经排序好

  10. 重复相同操作，直到所有数字都被排序

为了更好的让读者用自己熟悉的编程语言来理解动画，笔者将贴出多种编程语言的参考代码，代码全部来源于网上。

C++代码实现

【图解数据结构】 一组动画彻底理解选择排序

Java代码实现

【图解数据结构】 一组动画彻底理解选择排序

Python代码实现

【图解数据结构】 一组动画彻底理解选择排序

JavaScript代码实现

【图解数据结构】 一组动画彻底理解选择排序

如果你是iOS开发者，可以在GitHub上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。

如果你想获取高清的动画演示，在 五分钟学算法 公众号里回复 选择排序 即可。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK