常见排序算法

• 稳定性：如果a原本在b的前面，且a==b，经过排序后a仍然在b的前面。
• 非稳定性：如果a原本在b的前面，且a==b，经过排序后a不在b的前面。
• 原地排序：排序过程中不申请多余的存储空间，利用原来的存储空间进行交换和排序。
• 非原地排序：需要额外的数组空间进行交换和排序。
• 时间复杂度：执行算法所需要消耗的时间。
• 空间复杂度：执行算法所需要消耗的空间。

关于时间复杂度

• 平方阶(O(n2))：插入排序、选择排序和冒泡排序。
• 线性阶(O(n))：基数排序和桶排序。
• 线性对数阶(O(nlog n))：快速排序、堆排序和归并排序。

关于空间复杂度

• 线性阶(O(n))：归并排序。
• 线性对数阶(O(log n))：快速排序。
• 线性+K阶(O(n+k))：桶排序、基数排序。
• 常数阶(O(1))：冒泡排序、选择排序、插入排序、希尔排序和堆排序。

关于稳定性

• 稳定排序：冒泡排序、插入排序、归并排序和基数排序。
• 不稳定排序：选择排序、快速排序、希尔排序和堆排序。
  

冒泡排序

重复地访问要排序的数列，一次比较两个元素，如果他们的顺序错误就交换过来。访问数列的工作是重复地进行直到没有在需要交换的元素，也就说明数列已经排序完成。

• 比较相邻的元素，如果第一个比第二个大，则交换他们
• 对每一对元素执行相同的操作，从开始第一对到结束最后一对，经过一轮后最后的元素是最大的。
• 针对所有元素重复以上步骤，一直到最后一个。

选择排序

首先在未排序序列中找到最大（小）元素，存到排序序列的起始位置，然后在从剩余未排序元素中继续寻找最大（小）元素，然后放到已排序序列的末尾。

• 初始状态：无序区R[1…n]，有序区R[]
• 第i趟排序，当有序区和无序区分别为R[1…i-1]和R[i…n]
• 该趟排序从当前五序区中选出关键字最小的记录R[k]
• 将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n]分别变为记录个数加1的新有序区和记录个数减少1的新无序区
• n-1趟结束，数组有序化

表现最稳定的排序算法之一，无论数据规模大小时间复杂度都是o(n^2)，所以数据规模越小越好

插入排序

通过构建有序序列，对于未排序的数据在已排序序列中从后向前扫描，找到相应位置插入。

• 从第一个元素开始，该元素已经被认为有序
• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果该元素大于新元素，将该元素移到下一个位置
• 重复步骤3，直到找到已排序的元素小于或等于新的元素的位置
• 将新元素插入到该位置后，重复以上步骤

希尔排序

1959年shell发明，第一个突破O(n2)的排序算法，简单插入排序的改进版。与插入排序不同的是，它会优先比较距离较远的元素，又称缩小增量排序。

• 将整个排序序列分为若干个子序列分别执行直接插入排序
• 选择一个增量序列t1、t2，… ，tk，ti > tj，tk=1，对增量序列按个数K，对序列进行K趟排序
• 每趟排序根据对应的增量ti，对待排序序列分割成若干长度为m的子序列，分别对子表执行直接插入排序
• 当增量仅为1时，整个序列作为一个表来处理，表的长度为整个序列的长度

算法的核心在于间隔序列的设定，既可以设定动态间隔，也可以设定默认间隔。

归并排序

归并排序是建立在归并操作上的一种排序，采用的是分治的思想。先使每个子序列有序，在使子序列段有序，然后将两个有序表合并。将已有序的子序列合并，得到完全有序的序列。

• 把长度为n的输入序列分成两个长度为n/2的子序列
• 对两个子序列分别执行归并排序，将两个子序列合并为有序序列

归并排序是稳定排序算法，和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，时间复杂度始终为O(nlog2)

快速排序

通过一趟排序将序列分为两部分，其中一部分的关键字比另一部分的关键字小，分别对两部分进行排序，达到有序。使用分治的方法把串分成两个字串

• 从数列中挑出一个元素，称为基准，一般为首个元素
• 重新排序数列所有比基准小的元素放在基准前面，所有比基准大的放在后面
• 递归的把子序列按照步骤二执行，最终可得到一个有序的序列

堆排序

利用堆进行排序的一种算法，按照堆的子节点或索引总是大于或小于他的父节点的性质

• 将初始序列(R1,R2,…,Rn)构建成大顶堆，堆的初始状态为无序
• 将堆顶元素R[1]与最后一个元素R[n]进行交换，此时得到新的无序区(R1,R2,…,Rn-1)和有序区域Rn，且满足(R1,R2,…,Rn-1)<=Rn
• 由于交换后的新堆顶可能违反堆的性质，因此需要对当前无序区(R1,R2,…,Rn-1)进行调整为新的堆
• 然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)
• 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成

计数排序

将输入的数据值转换为键，存储在额外开辟的数组空间中，作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数，计数排序适用于小范围数

• 找出待排序的数组中最大和最小的元素
• 统计数组中每个值为i的元素出现的次数，存入数组c的第i项
• 对所有的计数累加(从c中的第一个元素开始，每一项和前一项相加)
• 反向填充目标数组，将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减1

计数排序是稳定排序，当输入的元素是n个0到k之间的整数时，时间复杂度为O(n+k)，空间复杂度为O(n+k)，速度比较快。当n不是很大时且数据比较集中时，计数排序是一个很有效的排序算法，。

桶排序

桶排序是计数排序的升级版，它利用了函数的映射关系，排序是否高效在于函数的映射关系。假设输入数据服从均匀分布，将数据分到有限个数量的桶里，然后在使用别的算法或者使用递归的方式对每个桶进行排序

• 设定一个定量的数组当作是空桶
• 遍历输入数据，把每个数据放入到对应的桶
• 对每个不是空的桶进行排序，从不是空的桶里把有序的数据拼接起来

桶排序最好的情况下使用线性的时间复杂度O(n)，桶排序的时间复杂度取决于每个桶之间数据排序的复杂度，因为其他的部分时间复杂度为O(n)，显然，桶划分的越小，各个桶之间的数据越少，排序用的时间也越少。

基数排序

基数排序按照高低位先排序，然后收集，在按照高位排序，然后在收集，以此类推，直到最高位；有时间有些属性是有优先级顺序的，先按照低优先级，在按照高优先级排序，最后的次序是高优先级高的在前面，高优先级相同的低优先级高的在前面

• 取得数组中的最大数，并取得位数，arr为原始数组，
• 从最低位开始取每个位组成的radix数组，对radix进行计数排序

基数排序是基于分别排序、分别收集，所以是稳定的，但是基数排序的性能比桶排序要差，每一次关键字的桶分配都需要O(n)的时间复杂度

推荐

1、数据结构算法可视化网站-Visualgo.net