下载文档原格式
本文介绍了7种最经典、最常用的排序算法，分别是：冒泡排序、插入排序、选择排序、归并排序、快速排序、桶排序、计数排序、基数排序。对应的时间复杂度如下所示：
整篇文章的主要知识提纲如图所示：
1. 排序算法分析
学习排序算法除了学习它的算法原理、代码实现之外，最重要的是学会如何评价、分析一个排序算法。分析一个排序算法通常从以下几点出发。
1.1. 执行效率
而对执行效率的分析，一般从这几个方面来衡量：
•最好情况、最坏情况、平均情况
除了需要给出这三种情况下的时间复杂度还要给出对应的要排序的原始数据是怎么样的。
•时间复杂度的系数、常数、低阶
大O时间复杂度反应的是算法时间随n的一个增长趋势，比如O(n^2)表示算法时间随n的增加，呈现的是平方的增长趋势。这种情况下往往会忽略掉系数、常数、低阶等。但是实际开发过程中，排序的数据往往是10个、100个、1000个这样规模很小的数据，所以在比较同阶复杂度的排序算法时，这些系
数、常数、低阶不能省略。
•比较次数和交换（或移动）次数
在基于比较的算法中，会涉及到元素比较和元素交换等操作。所以分析的时候，还需要对比较次数和交换次数进行分析。
1.2. 内存消耗
内存消耗其实就是空间复杂度。针对排序算法来说，如果该排序算法的空间复杂度为O(1)，那么这个排序算法又称为原地排序。
1.3. 稳定性是什么
稳定性是指待排序的序列中存在值相等的元素。
在排序之后，相等元素的前后顺序跟排序之前的是一样的。
为什么
我们将排序的原理和实现排序时用的大部分都是整数，但是实际开发过程中要排序的往往是一组对
象，而我们只是按照对象中的某个k e y来进行排序。
比如一个对象有两个属性，下单时间和订单金额。在存入到数据库的时候，这些对象已经按照时间先后的顺序存入了。但是我们现在要以订单金额为主k e y，在订单金额相同的时候，以下单时间为k e y。那么在采用稳定的算法之后，只需要按照订单金额进行一次排序即可。比如有这么三个数据，第一个数据是下单时间、第二数据是订单金额：（20200515、
20）、（20200516、10）、（20200517、30）、
（20200518、20）。在采用稳定的算法之后，排序的
情况如下：（20200516、10）、(20200515、20)、（20200518、20）、（20200517、30）可以发现在订
单金额相同的情况下是按订单时间进行排序的。
2. 经典的常用排序算法
2.1. 冒泡排序
冒泡排序就是依次对两个相邻的元素进行比较，
然后在不满足大小条件的情况下进行元素交换。一趟
冒泡排序下来至少会让一个元素排好序（元素排序好
的区域相当于有序区，因此冒泡排序中相当于待排序
数组分成了两个已排序区间和未排序区间）。因此为
了将n个元素排好序，需要n-1趟冒泡排序（第n 趟的时候就不需要）。
下面用冒泡排序对这么一组数据4、5、6、3、2、1，从小到大进行排序。第一次排序情况如下：
可以看出，经过一次冒泡操作之后，6这个元素已经存储在正确的位置上了，要想完成有所有数据的排
序，我们其实只需要5次这样的冒泡排序就行了。图中给出的是带第6次了的，但是第6次其实没必要。
2.1.1. 优化
使用冒泡排序的过程中，如果有一趟冒泡过程中元素之间没有发生交换，那么就说明已经排序好了，可以直接退出不再继续执行后续的冒泡操作了。
2.1.2. 实现
下面的冒泡排序实现是优化之后的：
/**
* 冒泡排序：
* 以升序为例，就是比较相邻两个数，如果逆序就交换，类似于冒泡；
* 一次冒泡确定一个数的位置，因为要确定 n-1 个数，因此需要 n-1
* 次冒泡；
* 冒泡排序时，其实相当于把整个待排序序列分为未排序区和已排序区
*/
public void bubbleSort(int[] arr, int len) {
// len-1 趟
for (int j = 0; j < len-1; j++) {
int sortedFlag = 0;
// 一趟冒泡
for (int i = 0; i < len-1-j; i++) {
if (arr[i] > arr[i+1]) {
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
sortedFlag = 1;
}
}
// 该趟排序中没有发生，表示已经有序
if (0 == sortedFlag) {
break;
}
}
}
2.1.
3. 算法分析
•冒泡排序是原地排序。因为冒泡过程中只涉及到相邻数据的交换，相当于只需要开辟一个内存空间用来完成相邻的数据交换即可。
•在元素大小相等的时候，不进行交换，那么冒泡排序就是稳定的排序算法。
•冒泡排序的时间复杂度。
▪当元素已经是排序好了的，那么最好情况的时间复杂度是O(n)。因为只需要跑一趟，然后发现已经排好序了，那么就可以退出了。
▪当元素正好是倒序排列的，那么需要进行n-1趟排序，最坏情况复杂度为O(n^2)。
▪一般情况下，平均时间复杂度是O(n^2)。使用有序度和逆序度的方法来求时间复杂度，冒泡排序过程中主要是两个操作：比较和交换。每交换一次，有序度就增加一，因此有序度增加的次数就是交换的次数。又因为有序度需要增加的次数等于逆序度，所以交换的次数其实就等于逆序度。
因此当要对包含n个数据的数组进行冒泡排序时。最坏情况下，有序度为0，那么需要进行
n*(n-1)/2次交换；最好情况下，不需要进行交换。
我们取中间值n*(n-1)/4，来表示初始有序度不是很高也不是很低的平均情况。由于平均情况下需要进行n*(n-1)/4次交换，比较操作肯定比交换操作要多。
但是时间复杂度的上限是O(n^2)，所以平均情况下的时间复杂度就是O(n^2)。
