十大排序算法原理及Java实现
status
category
date
summary
slug
icon
tags
password
排序概述
排序算法分类
排序算法是最常见的算法之一，也是面试考察较为频繁的题目之一，在此总结一下，以便以后复习。
如上图，经常提及的十大排序算法如果按原理划分，可以分为：
- 交换排序：冒泡排序、快速排序
- 插入排序：直接插入排序、希尔排序
- 选择排序：简单选择排序、堆排序
上面的6种加上归并排序都是基于比较的排序，还有三种非比较类排序：计数排序、桶排序和基数排序，如上图所示。
相关概念
- 稳定性：若a=b，排序不影响ab的相对位置。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
冒泡排序
基本思想
冒泡排序（Bubble Sort）需要重复访问序列，一次比较相邻两个元素，如果顺序错误就交换它们。重复访问序列的工作一直进行到不需要交换元素为止，这个算法的名称由来，是因为越小的元素会经过交换逐渐上浮到序列顶端，就像水中的气泡从水底上浮一样。
冒泡排序的具体步骤如下（以升序为例）：
- 比较相邻元素，如果前者比后者大，就交换他们的位置。
- 对每一对相邻元素重复上一步操作，这一步做完之后，最后的元素已经是最大的元素。
- 对除了最后一个元素之外的相邻元素，重复第一步和第二步，直到没有任何相邻元素需要比较。
代码实现
算法效率
冒泡排序是稳定的排序算法，最坏情况是数组已经逆序排列（例如我们希望升序排列，但数组已经降序排列好了，本文都以升序为例），供需遍历n(n-1)/2次，时间复杂度为O(n2)。
最好情况是已经排序好了，此时的代码需要一点改动，即设置是否需要交换的标志位，如果内循环发现已经排序完成，则直接返回，此时时间复杂度为O(n)，代码如下：
平均来讲，冒泡排序的时间复杂度为O(n2)；因为只需要交换元素时的缓存temp，所以空间复杂度为O(1)。
交换数字的三种方法
在排序中经常遇到需要交换数字的情景，这里简单总结一下。
快速排序
基本思想
快速排序是对冒泡排序的一种改进，使用了分治的思想：通过一趟排序将需要排序的数据分割成独立的两部分，其中一部分所有的数比另一部分所有的数都要小，然后对这两个部分的数再次重复操作，整个排序递归进行，直到整个序列排序完成。
快速排序的具体步骤为：
- 从数列中调出一个数为基准(pivot)，一般是该部分的第一个数，“随机快速排序”的基准是随机选取的。
- 将所有比基准小的数放在基准前面，比基准大的数放在基准后面，基准位于中间，称为分区（partition）。
- 在两个分区重复第一步和第二步，递归进行，直到某个分区大小为1或0。
具体实现起来，一般有两种方式。
挖坑法
- 以第一个数为例，将基准数挖出，形成第一个坑array[left]
- right—，从右向左找比基准小的数，找到后挖出此数，将其填到第一步挖出的坑坑array[left]中。
- left++，从左向右找比基准大的数，找到后挖出此数，将其填到第二步挖出的坑array[right]中。
- 重复执行第二步和第三步，直到left == right，将基准填入坑中。
挖坑法首先挖出了基准数，需要一个临时变量缓存，即在数组的n个位置中只有n-1个数，不断地填坑之后，最后再将基准数填入，跟临时变量交换法的思路有些相似。
左右指针法
- 首先选取基准，以第一个数为例。
- right—，从右向左找到比基准小的数。
- left++，从左向右找到比基准大的数。
- 交换第二步和第三步找到的数。
- 重复第二步至第四步，直到左右指针相遇，即left == right，此时将基准和相遇处的数值交换。
左右指针法不需要临时变量缓存，完全在数组内部操作。另外，让右指针先走，可以保证相遇位置的数小于基准，循环结束之后交换基准与此数，确保了此数在基准左侧。
代码实现
挖坑法
左右指针法
算法效率
快速排序并不稳定，快排每次交换的元素可能不是相邻的，所以它有可能打破原来相邻元素的顺序。
快速排序的好坏情况跟分区情况有关，最好情况是每次分区都是均匀的，那么一次递归共需比较n次，递归树深度为logn，所以最好情况时间复杂度为O(nlogn)。
最坏情况下，数组已经顺序或者逆序排列好，每次分区的元素都只能得到比上一次分区少一个元素，并且另一个分区为空。此时每次递归需要n-1次比较，递归树是一棵斜树，因此比较次数为n(n-1)/2，时间复杂度为O(n2)。
平均情况的时间复杂度为O(nlogn)，由于每次递归都使用了常数的空间，所以空间复杂度为O(1)。
直接插入排序
基本思想
直接插入排序的思路是：将数组中所有元素依次与前面已经排好序的元素比较，如果选择的元素比已排序的元素小，则交换，直到找到一个前面比它小，后面比它大的位置，就插入。这个方式跟打牌的时候，摸牌插入非常相似。
具体步骤：
- 默认第一个元素已经被排序完成
- 取出下一个元素，在已排序的元素中从右往左扫描
- 如果该元素（被选择的元素）小于已排序的元素，则继续往左移动
- 重复步骤三，直到找到大于等于已排序元素的位置，插入该元素后面
- 重复第二步至第四步，直到数组最后一个元素被插入
代码实现
移位法
移位法先取出带插入的数据保存，找到合适的位置后再插入该数，有点类似于快速排序中的挖坑法。
交换法
交换法不需要额外地保存待插入的数据，而是相邻交换，类似于冒泡排序的思想。
算法效率
直接插入排序是稳定的排序算法，最好情况自然是已经排好序，只需要遍历一边数组，发现每次都不需要插入，此时时间复杂度为O(n)。
最坏的情况是数组完全逆序，总共需要n(n-1)/2次交换，时间复杂度为O(n2)。平均来讲，时间复杂度为O(n2)，空间复杂度为O(1)。
希尔排序
基本思想
希尔排序是直接插入排序的一种改进版，它先将整个数组划分为若干个子序列，并对子序列分别进行直接插入排序，当各个子序列“基本有序”时，再对整个数组进行直接插入排序。
具体步骤：
- 选择一个增量gap（一般初始值为数组长度的一半）
- 按照数组下标递增gap，可将数组划分为若干子序列，针对每个子序列，进行直接插入排序
- gap减半，重复第二步，直至gap为1时，对整个数组进行一次直接插入排序
代码实现
算法效率
由于相邻元素可能划分到不同的子序列，所以希尔排序是不稳定的排序算法。它与直接插入排序的区别在于，它会优先比较距离较远的元素。希尔排序的时间复杂度与gap的选择有关，时间复杂度在O(n2)和O(nlog2n)之间。一般采用的是Shell增量排序（即n/2），但这不一定是最好的增量，增量的选择不在本文的探讨范围内。
直接选择排序
基本思想
在未排序的序列中找到最小的元素，将其放到未排序序列的起始位置（即已排序序列的末尾），然后再继续从未排序序列中寻找最小元素，直至全部排序完毕。
具体步骤：
- 在未排序序列中寻找到最小元素
- 将该最小元素与未排序序列的第一个元素互换位置
- 在剩下的待排序序列中，重复第一步和第二步，直到排序结束
代码实现
算法效率
因为每一次最小元素都需要交换，所以选择排序是不稳定的，无论是哪种情况，即使数组已经排序完成，它都需要遍历n(n-1)/2次来确认，所以时间复杂度为O(n2)。唯一特殊的是它并不需要额外的存储空间。
堆排序
先补充几个概念：
- 满二叉树：所有结点，要么是叶子结点（没有子结点），要么有两个子结点。
- 完全二叉树：除最后一层外，所有层的结点个数均为最大值，且最后一层的所有结点集中在最左边。
对于完全二叉树的结点k（结点和编号一一对应，根节点编号为0），它的左子结点为2k+1，右子结点为2k+2。
基本思想
堆排序利用了堆这一特殊的数据结构，一般来说是完全二叉树，并满足堆的性质：子结点的值总是大于（或总是小于）父结点的值。
具体过程：
- 将数组构建成最大堆，此时称为初始的无序区（R1，R2，……Rn），堆顶元素最大
- 将堆顶元素和最后一个元素交换，得到新的无序区（R1，R2，……Rn-1）和有序区（Rn）
- 将无序区重新构建最大堆，然后重复第二步
- 重复第三步，直至有序区元素个数为n-1，整个排序过程结束
建堆的过程是递归的，每次比较该节点与其左右子节点，因此为了提高效率，不需要从最后一个元素开始，而应当从最后一个元素的父节点开始。最后一个元素序号为length - 1，若它是左子节点，则父节点为(length - 2)/2；若它是右子节点，则父节点为(length - 3)/2，故最后一个节点的父节点序号总是length/2 - 1。
代码实现
算法效率
由于堆排序中，初始化堆的过程中比较次数较多，因此它不适用于小序列。同时由于多次交换，所以它不是稳定的排序。
- 建立初始堆的过程，从length/2一直到到0，时间复杂度为O(n)
- 堆的重构过程沿父子结点进行，执行次数为堆的深度，时间复杂度为O(logn)
- 堆排序由第二步执行n-1次完成，所以时间复杂度为O(nlogn)
归并排序
基本思想
归并排序利用了分治的思想，先把未排序的序列分成若干个子序列，然后将子序列排序完成，最后将子序列合并。
具体步骤：
- 将长度为n的序列分成两个长度为n/2的子序列
- 对两个子序列分别采用归并排序，递归直至子序列元素数为1
- 将排好序的子序列合并成最终的排序序列
代码实现
算法效率
假设数组长度为n，那么拆分数组共需操作logn次，每次合并的时间复杂度都是O(n)，所以时间复杂度为O(nlogn)。但合并时需要保存拆分的子序列，所以空间复杂度为O(n)。另外，因为最终的排序序列是从子序列合并而来的，只要保证合并过程稳定（即相等时优先放入左侧数据），则整个排序就是稳定的。
计数排序
基本思想
计数排序不是基于比较的排序算法，其核心在于将需要排序的数值转化为“键”储存在额外的数组空间中，因此要求需要排序的数据必须是确定范围的整数。
具体步骤：
- 找出待排序数组中最大的元素和最小的元素
- 统计数组中每个值为i的元素的次数，并存入辅助数组C的第i项
- 从辅助数组C的第一项开始叠加，后一项等于前一项加上自身的和
- 填充目标数组：将每个元素i放在新数组的第C[i]项，且C[i]项自减
代码实现
算法效率
计数排序是一个稳定的排序，当待排序的数是n个从0到k的整数时，时间复杂度为O(n+k)，空间复杂度为O(n+k)，牺牲空间的算法使得计数排序的速度高于任何基于比较的排序算法。当k不是很大，且序列比较集中时，计数算法的效率非常高。
桶排序
基本思想
桶排序是计数排序的升级版，它将待排序的数据放入有限量、有排序的桶里，每个桶内再分别排序，最后按照桶的排序结果和桶内数据的排序结果，整理出最后的排序数列。
具体步骤：
- 设置一个定量的数组作为空桶
- 遍历待排序数据，并依次放入桶中
- 对每个非空桶内的数据进行排序
- 从非空桶内把数据依次连接起来
代码实现
算法效率
桶排序也利用了收集排序的思想，桶排序利用了函数的映射关系，因此效率的高低取决于该映射关系是否恰当。桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
基数排序
基本思想
基数排序按照低位先排序，然后收集；然后高位再排序，再收集，直到最高位。这是因为考虑到有些时候属性是有高低优先级的，例如整数排序中高位的优先级更高、姓名排序时姓的优先级更高等等。最后排序和收集的属性，优先级就更高。
具体步骤：
- 从待排序数列中找到最大数，并取得位数
- 从最低位开始，取每个位组成radix数组
- 对radix进行计数排序（利用了计数排序适用于小范围数的特点）
代码实现
算法效率
基数排序是分别排序、分别收集的，所以是稳定的。基数排序的复杂度与待排序的数据有关：
最好时间 | 最坏时间 | 平均时间 | 空间复杂度 |
O(d*(n+r)) | O(d*(n+r)) | O(d*(n+r)) | O(n+r) |
其中，d为最大数的位数，r为基数，n为元素个数。在基数排序中，没有比较操作，所以最好时间和最坏时间是一致的。
基数排序适用于对时间、字符串等权重未知的数据进行排序。
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- 基数排序：根据键值的每位数字来分配桶
- 计数排序：每个桶只存储单一键值
- 桶排序：每个桶存储一定范围的数值
总结
排序算法 | 最好时间 | 最坏时间 | 平均时间 | 空间复杂度 | 稳定性 |
冒泡排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
快速排序 | O(nlogn) | O(n2) | O(nlogn) | O(1) | 不稳定 |
直接插入排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
希尔排序 | O(n) | O(ns)(1<s<2) | O(nlogn) | O(1) | 不稳定 |
直接选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
桶排序 | O(n) | O(n2) | O(n+k) | O(n+k) | 稳定 |
基数排序 | O(d*(n+r)) | O(d*(n+r)) | O(d*(n+r)) | O(n+r) | 稳定 |
参考：十大经典排序算法（动图演示）
Loading...