优秀的文章，及时送达
作者浅斑马
来源|蓝桥(id :局域网中心) ) )。
排序算法可以分为以下两类。
1、非线性时间比较类排序：通过比较决定要素之间的相对顺序，由于其时间复杂度无法突破o(nlogn )，故称为非线性时间比较类排序。
2、线性时间非比较类排序：不通过比较来决定要素之间的相对顺序，可以突破基于比较排序的时间下界，按线性时间执行，所以称为线性时间非比较类排序。
相关概念
稳定：当a原本在b前面，a=b时，排序后a也在b前面。
不稳定：如果a本来在b前面，a=b，则排序后a有可能出现在b后面。
的复杂性：对已排序数据的操作总数。 n发生变化时，操作次数反映出什么样的法则。
空间复杂度是指在计算机内执行算法时所需的存储区域的尺度，也是数据规模n的函数。
一、插入排序
1.1直接插入排序
插入排序的基本操作是，通过在已经排序的有序数据中插入数据，得到新的、个数加1的有序数据。 算法适用于少量数据的排序，时间复杂度为o(n^2)。 稳定的排序方法。
直接插入排序算法的想法：
1、设置监视哨temp，将插入的记录的值分配给temp；
2、设定开始检索的位置j；
3、用数组arr进行检索，通过检索将第j个记录移动到temparr[j]为止；
4、将temp插入arr[j 1]的位置。
1.2水蛭排序
希尔排序(Shell's Sort )是一种插入排序，也称为“细化增量排序”(Diminishing Increment Sort )，是直接插入排序算法的效率更高的改进版。 希尔排序是一种非稳定排序算法。 该方法因1959年由d.l.shell提出而得名。
希尔排序算法的想法：
1、序列按标的一定增量分组；
2、各组使用直接插入排序算法进行排序
3、随着增量逐渐减少，各组包含的值越来越多，增量减少到1时，整个文件被分成一组，算法结束。
二、重新排序
2.1冒泡的排序
一组数据中，相邻的要素按顺序比较大小，最大的放在后面，最小的往上提。
对气泡排序算法的思考：
1 .比较相邻的元素。 如果第一个比第二个大，就换他们俩。
2 .从第一对到最后一对，对每个相邻的对进行相同的工作。 在这方面，最后的要素应该是最大的数量。
3 .对所有要素重复上述步骤，最后一个除外。
4 .每次对越来越少的元素重复上述步骤，直到没有需要比较的数字对为止。
2.2快速排序
“快速排序”是对冒泡排序的改进。
如果将数组按一次排序划分为两个子数组，一个数字小于另一个数字，然后分别对两个子数组进行高速排序，则可以递归地进行整个排序过程，从而生成整个数据的排序序列。
快速排序算法的想法：(分治法) )
1 .首先从数列中取出一个数作为中间值middle
2 .把小于这个数的数都放在其左边，再多的数都放在其右边
3 .对左右两个小数列重复步骤2，直到各区间达到一个个数。
三、排序的选择
3.1简单的选择排序
“选择排序”(Selection-sort )是一种简单直观的排序算法。 该机制首先在未排序的数组中找到最小(大)元素，将其存储在已排序数组的第一个位置，然后在剩下的未排序元素中查找最小)元素，最后放置在已排序数组中。 这样，等待所有元素都被排序。
简单排序的算法思路：
1 .首先在未排序的序列中找出最小(大)要素，存储在排序序列的开头
2 .从剩下的未排序元素中继续寻找最小(大)元素，并放置在排序序列的最后
就这样，到现在为止
所有元素均排序完毕。3.2 堆排序
堆排序（英语：Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。
堆排序的算法思路：
1.最大堆调整（Max Heapify）：将堆的末端子节点作调整，某个节点的值最多和其父节点的值一样大；
2.创建最大堆（Build Max Heap）：将堆中的所有数据重新排序,堆中的最大元素存放在根节点中；
3.堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。
四、归并排序
4.1 二路归并排序
归并排序（mergeSort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。例如：将2个有序数组合并。比较2个数组的第一个数，谁小就先取谁，取了后就在对应数组中删除这个数。然后再进行比较，如果有数组为空，那直接将另一个数组的数依次取出即可。
二路归并排序的算法思路：
1、将数组分成A，B 两个数组，如果这2个数组都是有序的，那么就可以很方便的将这2个数组进行排序。
2、让这2个数组有序，可以将A，B组各自再分成2个数组。依次类推，当分出来的数组只有1个数据时，可以认为数组已经达到了有序。
3、然后再合并相邻的2个数组。这样通过先递归的分解数组，再合并数组就完成了归并排序。
五、计数排序
计数排序（Counting sort）不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序的算法思路：
1、求出待排序数组的最大值 max 和最小值 min。
2、实例化辅助计数数组temp，temp数组中每个下标对应arr中的一个元素，temp用来记录每个元素出现的次数。
3、计算 arr 中每个元素在temp中的位置 position = arr[i] - min。
4、根据 temp 数组求得排序后的数组。
六、桶排序
桶排序 (Bucket sort)的工作原理是将数组分到有限数量的桶里。每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响，桶排序可用于最大最小值相差较大的数据情况。
桶排序的算法思路：
1、找出待排序数组中的最大值max和最小值min；
2、我们使用动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为 (max-min) / arr.length + 1；
3、遍历数组 arr，计算每个元素 arr[i] 放的桶；
4、每个桶各自排序；
5、遍历桶数组，把排序好的元素放进输出数组。
七、基数排序
基数排序（radix sort）是桶排序的扩展，基本思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。
基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。基数排序的算法思路：
1、取得数组中的最大数，并取得位数；
2、arr为原始数组，从最低位开始取每个位组成radix数组；
3、对radix进行计数排序（利用计数排序适用于小范围数的特点）。
。
【END】
如果看到这里，说明你喜欢这篇文章，请转发、点赞。微信搜索「web_resource」，关注后回复「进群」或者扫描下方二维码即可进入无广告交流群。