前言
手撕算法，面试必备，你懂得！
一、排序及其分类
所谓排序就是将一组无序的记录序列调整为有序的记录序列。
① 选择排序：主要包括简单选择排序和堆排序；
② 插入排序：简单插入排序、希尔排序；
③ 交换排序：冒泡排序、快速排序；
④ 归并排序
⑤ 非比较排序：计数排序、桶排序、基数排序属于非比较排序，算法时间复杂度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）：从待排序元素的最左边开始计算（如果是数字类型，即从最高位开始）。
代码实现为：
输入随机案例进行验证：
三、排序算法的比较
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/bcyy/60012.html