一文搞懂八大排序算法

大家好，欢迎来到IT知识分享网。

概念：

1. 空间复杂度，是否需要申请空间辅助
2. 时间复杂度，简单说就是循环次数
3. 稳定性，排序完成后，待排序队列中相等元素先后顺序不变

排序方式：

1. 插入法 ：不需要申请辅助空间，取出待排序元素，依次和有序列表元素比较 ，找到位置合适位置插入，排序过程中需要移动有序列表内的元素

1.1 直接插入排序

1.1.1 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

1.1.2 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

1.2 shell排序对直接插入排序的优化，采用分治思想将待排序分为若干个，因为相等元素可能分布在不同子序列，所以排序结果是不稳定的。

1.2.1 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

1.2.2 按增量序列个数k，对序列进行k 趟排序；

1.2.3 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2.选择法

2.1 直接选择排序 实现稳定排序需要按大（小）方式，决定遍历策略，如果从小到大排序需要从右到左遍历待排序元素，相等的元素取最后一个，同理如果从大到小排序需要从左到左右遍历待排序元素，相等的元素取最后一个

2.1.1 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；

2.1.2 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；

2.1.3 重复第二步，直到所有元素均排序完毕。

2.2 堆排序 分为大顶堆和小顶堆 不稳定

大顶堆：每个节点的值都大于或者等于它的左右子节点的值。

小顶堆：每个节点的值都小于或者等于它的左右子节点的值。

2.2.1 将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；

2.2.2 将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；

2.2.3 重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。

3.交换法

3.1 冒泡排序

3.1.1 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

3.1.2 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3.1.3 针对所有的元素重复以上的步骤，除了最后一个。

3.1.4 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

3.2 快速排序

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）

3.2.1 从数列中挑出一个元素，称为 “基准”（pivot）。

3.2.2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3.2.3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

4.归并法

4.1 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

4.1.1 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

4.1.2 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

4.1.3 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4.1.4 重复步骤3直到某一指针达到序列尾；

4.1.5 另一序列剩下的所有元素直接复制到合并序列尾。

5.基数法 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

5.1 桶排序

算法思想：是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（O（n））。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响。简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的数据排序。

例如要对大小为[1..1000]范围内的n个整数A[1..n]排序。

首先，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储[10..20]的整数，……集合B[i]存储[(i-1)*10, i*10]的整数，i=1,2,..100。总共有100个桶。

然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。

最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这 样就得到所有数字排好序的一个序列了。

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果对每个桶中的数字采用快速排序，那么整个算法的复杂度是O(n+m*n/m*log(n/m))=O(n+nlogn–nlogm)。从上式看出，当m接近n的时候，桶排序复杂度接近O(n).

当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

前面说的几大排序算法，大部分时间复杂度都是O（n2），也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O（n）的时间复杂度。但桶排序的缺点是：

1. 首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。
2. 其次待排序的元素都要在一定的范围内等等。

总结：

关于时间复杂度：

1. 平方阶(O(n2))排序:直接插入、直接选择和冒泡排序。
2. 线性对数阶(O(nlog2n))排序：快速排序、堆排序和归并排序。
3. 线性阶(O(n))排序：桶排序、箱排序等。

关于稳定性：
稳定的排序算法有：冒泡排序、插入排序、归并排序和桶排序；
不是稳定的排序算法有：选择排序、快速排序、希尔排序、堆排序。