前言
手撕算法，面试必备，你懂得！
一、排序及其分类
所谓排序就是将一组无序的记录序列调整为有序的记录序列。
① 选择排序：主要包括简单选择排序和堆排序；
② 插入排序：简单插入排序、希尔排序；
③ 交换排序：冒泡排序、快速排序；
④ 归并排序
⑤ 非比较排序：计数排序、桶排序、基数排序属于非比较排序，算法时间复杂度O(n)， 属于空间换时间。
二、经典排序算法的实现
2.1 选择排序
从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
实现的代码如下：
输入随机案例进行验证：
2.2 插入排序
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。算法适用于少量数据的排序，时间复杂度为
讯享网。
实现步骤如下：
输入随机案例进行验证：
2.3 希尔排序
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。克服了插入排序每次只比较相邻元素的缺陷。
希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
输入随机案例进行验证：
2.4 冒泡排序
详见本人的另外一篇博客：关于冒泡排序及其优化（Python实现）。
2.5 归并排序
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了之后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
输入随机案例进行验证：
2.6 堆排序
详见本人的另外一篇博客：算法之堆排序（python实现）。
2.7 快速排序
快速排序（Quicksort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
详细步骤为：
输入随机案例进行验证：
2.8 计数排序
基本思想： 对于数组 中的每一个元素 ，确定小于 的元素总个数。所以直接可以把 放到输出数组的相应位置上，比如数组 中有 个数小于 ，则 应该放在输出数组的第六个位置上。
代码实现为：
输入随机案例进行验证：
2.9 桶排序
基本思想： 把数组 划分为n个大小相同的区间（即桶），每个子区间各自排序，最后合并。桶排序要求数据的分布必须均匀，否则可能会失效。计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
代码实现为：
输入随机案例进行验证：
2.10 基数排序
基本思想： 将待排序的数据按照位数切割成不同的数字，然后按每个位数分别比较。
基数排序可以采用两种方式：
① LSD（Least Significant Digital）：从待排序元素的最右边开始计算（如果是数字类型，即从最低位个位开始）。
② MSD（Most Significant Digital）：从待排序元素的最左边开始计算（如果是数字类型，即从最高位开始）。
代码实现为：
输入随机案例进行验证：
三、排序算法的比较
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/168362.html