不同的排序算法源于不同的思想。虽然目标是一样的,却有不同的效率,各自的稳定性、是否是原址排序也是有所不同。这里做一个总结,并且附上java实现的代码。具体如下:
- 基本概念
- 插入排序
- 冒泡排序
- 选择排序
- 归并排序
- 堆排序
- 快速排序
完整代码(包括测试用例): (https://github.com/FergusChen/AlgoCode)
包路径:main.sort
先说一些概念型的东西,用于描述排序算法:
原址排序:直接在原数组中排序,只需要常数个额外空间。
稳定排序:如果一个排序算法是稳定的,则序列中相同的元素原来有怎样的前后次序,排序后仍然是这样的前后次序。具体来说,对于序列[1,3,5,3,4]
, 排序后序列为[1,3,3,4,5]
,其中,原来在前面的3
仍然在前面,保证两个3
的前后次序,这样的排序算法就是稳定的。
插入排序
听到插入排序就想起来左手一副扑克牌,扑克牌的左半部分是已经排好序的,然后逐个抽取右半部分的牌,插入到左半部分的合适位置,直到整副牌都是排好序的。
插入排序就是这样的思想。初始化时左半部分只有1
个元素,当然是排好序的啦。然后从右半部分的第1
个元素开始,与左半部分已排好序的元素逐个比较,直到找到合适位置(插入后仍使左半部分有序),将该元素插入到此位置就可。
当然,插入的时候就涉及到元素的右移
,即把待插入的位置右边的元素(直到待插入的元素)逐个右移,腾出1
个元素空间,以存放待插入的元素。特别是当原数组是倒序的,则会有(n-1)!
次元素右移,这样的话效率就会比较低。
由上可知,插入排序是原址排序,其最坏运行时间是O(n^2)
。并且插入排序是稳定的,因为相等的元素并不右移,所以元素插入后仍然保证前后次序。当待排序数组元素较少,插入排序还是很好的选择。
下面以整型数组为例来实现插入排序,只是演示排序思想。对于自定义对象等的排序,常常可以实现comparable接口,从compareTo方法比较,思想都是一样的。
|
|
冒泡排序
冒泡排序的名字就很形象:就好像从水底开始,相邻两个气泡互相比较,如果下面的比上面的大,就把两个气泡交换,直到最终把整个序列中最大的气泡换到顶部。接下来从下面开始,一步步把次大的气泡换到顶部…… 直到最后,就是一个升序的序列。
冒泡排序也是一种原址排序算法。冒泡排序是稳定的,因为冒泡排序是相邻两个元素交换次序,就算两个元素相等而且判断的条件是if(array[j] >= array[j+1])
,那么该相同元素也会交换两次(动手试试就知道了)。但是通常比较时“>
”的时候再交换位置。 冒泡排序是时间复杂度是O(n^2)
|
|
选择排序
选择排序的思想也很简单,就是从序列中选出最小的元素,与序列第1个元素交换位置,然后从剩余元素中选出最小的,与序列第2个元素交换位置……直到序列就剩1个元素了,即是一个排好序的序列。
选择排序也是原址排序,但选择排序是不稳定的。这里可以举个例子说明,如序列[3,6,5,3,1],在第一趟选择将第1个3
和结尾的1
交换位置,这样就破坏了两个3
的前后次序。选择排序的时间复杂度是O(n^2)
|
|
归并排序
归并排序的思想是“分治、合并”,其关键步骤是把两个有序的序列合并成1个有序序列。那么,有序的序列怎么形成呢?归并排序采用分治的策略,先对序列进行划分(递归),直到划分子序列只有1个元素,1个元素的序列当然是有序的啦,然后就可以将两个只含有1个元素的序列合并成1个含有两个元素的有序序列。总之,就是先划分,再回溯合并,这整个过程就是一个递归的过程。
归并排序的时间复杂度是O(nlgn)
,是一种稳定排序。归并排序需要将元素复制到临时数组,临时数组的长度为high - low + 1
,因此,归并排序并不是原址排序。
|
|
堆排序
堆排序涉及到一种比较有意思的数据结构——堆,对于其性质,可以回顾《算法导论》。简单来说,堆就是用数组实现的一颗近似的完全二叉树。最大堆可以保证每一个父结点都大于或等于其子结点。这样最大堆的根节点就是该数组的最大值。
堆排序使用最大堆,需要首先建堆,并且在交换根结点和最后一个结点之后,反复对堆维护。听起来很麻烦,但是因为每次维护堆的时间复杂度是O(lgn)
,建堆的时间复杂度是O(nlgn)
,则堆排序的时间复杂度仍然是O(nlgn)
。堆排序是原址排序,但堆排序是不稳定的。
|
|
快速排序
快速排序也是使用“分治”的思想,但与归并排序不同的是,快速排序在分治的过程中进行处理次序,具体来说,对于数组A[low ... high]
,被划分为两个(可能为空)的子数组A[low ... p-1]
和A[p+1 ... high]
,使得A[low ... p-1]
的元素都小于或等于A[p]
,A[p+1 ... high]
的元素都大于A[p]
。 然后再递归地划分A[low ... p-1]
和A[p+1 ... high]
。当左右子序列划分都递归到1个元素时,整个序列都是有序的啦。
快速排序的平均时间复杂度为O(nlgn)
,最坏时间复杂度是O(n^2)
。快速排序的实际性能是几个O(nlgn)
中最好的,而且还是原址排序。但是快速排序并不是稳定的排序算法。因为会涉及到元素与主元的交换。举个例子,对于序列[2,3,4,6,6,7,9,5],以5
为主元,当划分之后,元素5
需要与第1个6
交换位置,这样,就打破了两个6
的前后次序。
|
|