排序算法整理

排序在编程中经常有使用，尤其是面对数据分析和数据整理的时候，我们更加需要一种合适情景的排序方式来满足我们的需求，之前有对排序进行一些学习和了解，但是一直没有做系统性的整理和记录，导致很多时候需要重新查询资料理解，借着这个空闲时间对常见的排序算法进行整理加以自己的理解，希望自己以后看到能快速回忆并能在工作中使用到这些思想。

冒泡排序（Bubble Sort）

这应该是我们最常见的排序算法之一，接触数据结构与算法里面也是以这个引入的排序内容，其核心思想是将需要排序的数据像气泡由水底到水面浮上一般，每次选定一个数据与未完成排序的数据进行对比，满足排序需求则进行位置互换（气泡上浮的过程），这样子保证了每次能让满足需求（最大或者最小的数据）的数据浮动至最后的位置，当排序的数据全部经过这样子的操作后自然已经排序完毕的。
需要两层循环分别控制浮动的气泡数和比较的未排序数的选定

选择排序（Selection Sort）

选择排序与前面提到的冒泡排序有相似的地方，也是单次取得最大或者最小的数据，但是选择排序并没有频繁的进行数据交换，而是通过记录需要的数据（最大的或者最小的）的下标，最后与已经排序好的区域的数据进行比对，完成正确的位置的选择。
也需要两层循环，性能十分稳定，适用于数据规模小的排序

插入排序（Insertion Sort）

插入排序的整体思想在我的理解是“先排后序”，既不需要先按整体数据的大小顺序得到数据，而是先只将需要排序的数据按大小进行排列。首先默认第一个数据是有序的，然后取下一个数据，从有序的数据队伍的最后开始往前比对，如果满足小于则插入该数据的前面，其他数据顺次后移，直到未排序数据取完并排序完，此时完成排序。
需要多次进行赋值操作完成数据后移

希尔排序（Shell Sort）

通过设置增量来将数据划分为几个组，然后组内进行数据对比，完成一次后改变增量并完成组内排序的流程，最后既可完成整个排序。
在插入排序的基础上通过设定间隔形成

归并排序（Merge Sort）

归并排序的主要思想是分而治之，通常是采取对排序模块进行细分，然后将细分部分先进行排序，排序完成后再将两个部分按顺序比较并组合（递归方法循环处理），这种排序方式在数据较多的时候性能依旧能保持稳定。
性能稳定，但是需要额外的内存空间存储数据

快速排序（Quick Sort）

这种排序方式是通过选定一个基准元素，然后读取数据剩余全部元素，将大于基准的数据和小于基准的数据分别置于基准的前面或者后面（将二者分离），完成后基准将处于两堆数据的中间，如此循环往复（递归操作），最后将数据完成排序。
通过基准元素对数据进行分类处理

堆排序（Heap Sort）

堆排序利用到了数据结构中的完全二叉树的思想形式，堆中的所有子树满足父节点大于左右子节点，首先得到一个未排序的数据，按照顺序组成一棵完全二叉树，然后按照从最后一颗子树到最顶上的子树的顺序去构建堆（建立堆的过程中更改堆内子树结构后需要对其原来两个节点的子树进行再一次调整），在完成建立堆后，我们便可以开始堆排序，原则是将定点节点和最后一个节点进行交换代表排序完成（因为堆会满足顶点节点是最大的），在完成交换后，我们需要对顶点节点重新进行堆的构建规则，以此循环操作，最后得到一个有序的数据。
需要利用到完全二叉树和堆的数据概念，通过堆挑选出最大的数据来作为排序依据

计数排序（Counting Sort）

计数排序方式是一种典型的以空间换取时间的操作方式，首先得到数组内的最大值和最小值，建立一个以二者为下标边界的数组，通过遍历未排序的数据，在遍历过程中同时统计不同的数据与下标数值相同的有多少，最后读取统计好的数组的值，有多少值便打印多少个下标相同的数据，以此达到排序的目的。
当数据规模较大且数据范围跨度不大的时候计数排序是一种稳定且实用的方式

桶排序（Bucket Sort）

桶排序是计数排序的升级版本，其排序性能主要取决于桶的划分方式，划分区间太小则造成空间需求多排序时间减少，划分区间太多则造成排序耗时变多。
其流程是首先划分好桶的分类区间，然后将数据依据标准投入到不同的桶中，然后对非空的桶内数据进行排序，最后将非空的桶按照之前的划分标准再进行拼接。
算法优劣在于对桶的分区设置，是计数排序的一种分而治之的形式

基数排序（Radix Sort）

基数排序结合了计数排序，首先取得未排序数据中最大的数据，得到该数据的位数，然后按照位数形成划分空间（从个位、十位、百位......），然后将数据进行划分，划分的空间内利用计数排序适用于小范围数据区间的特点进行排序，最后将排序好的不同区间的数据组合，然后选择下一个划分空间的依据，重复上面的步骤，最后达到排序的目的。
基数排序是计数排序更加精细的一种策略，避开了计数排序对于空间申请的不确定性