数据结构-排序算法-简介篇

两个菜鸟程序猿 2020-02-12

263

今天我们讨论的问题是，我们数据结构里面的知识，排序算法。排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

那么，下面我们看一看我们排序算法的分类，如下图：

根据上图，我们知道：

内部排序算法：冒泡排序、快速排序、直接择排序、直接插入排序、希尔排序、归并排序、堆排序

其中冒泡排序和快速排序属于交换排序，直接插入排序和希尔排序属于插入排序

外部排序算法：计数排序、基数排序、桶排序等

基本概念：

每一种算法，都会有自己的稳定性、时间复杂度以及空间复杂度。

稳定性：如果i=j，排序前i在j的前面，排序后i仍然在j的前面，即相等的两个数字的相对位置在排序前后不变，则该算法是稳定的，否则不稳定。大家一定会有疑问，稳定性有什么用呢，是这样的，排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。可能比较难理解，这里再举个例子方便理解，比如在基数排序中，先将低位排序，再逐次按高位排序，稳定的话就可以保证排序后低位元素的顺序在高位相同时是不会改变的。

时间复杂度：指执行算法所需要的工作量，即对待排序数据的总操作次数，我们用它来描述算法的运行时间。

空间复杂度：指执行算法所需的内存空间。

那么，接下来，我们分别看一下我们每一种排序算法的实现的原理。

今日推荐阅读：

Redis（缓存数据库）面试题

Java初级-SpringMVC常见面试题总结

Java初级-Mybatis常见面试题

更多的内容请访问：https://blog.breakpoint.vip/

喜欢就在看吧！！！

数据库

文章转载自两个菜鸟程序猿，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

数据结构-排序算法-简介篇

评论

相关阅读