排序算法

偷得浮生半日闲。想了之前面试的一些经历,虽然没有涉及到算法,但是想起自己掌握一个东西,还真得反复斟酌和深入思考,一时的理解总敌不过岁月的擦抹。总结和理解下当前的一些主要排序算法。

算法与复杂度

稳定性及复杂度概述

排序算法 是否稳定 最坏时间复杂度 平均时间复杂度 最好时间复杂度 空间复杂度
直接插入 稳定 O(n^2) O(n^2) O(n) O(1)
二分插入 稳定 O(n^2) O(n^2) O(nlog2(n)) O(1)
希尔排序 不稳定 O(n^2) O(n^1.3) O(n)) O(1)
冒泡排序 稳定 O(n^2) O(n^2) O(n) O(1)
选择排序 不稳定 O(n^2) O(n^2) O(n^2) O(1)
堆排序 不稳定 O(nlog2(n)) O(nlog2(n)) O(nlog2(n)) O(1)
快速排序 不稳定 O(n^2) O(nlog2(n)) O(nlog2(n)) O(1)
归并排序 稳定 O(nlog2(n)) O(nlog2(n)) O(nlog2(n)) O(n)
计数排序 稳定 O(n) O(n) O(n) O(n)
桶排序 稳定 O(n) O(N+C) O(n) O(N+M)

算法的优化点与解析

  • 直接插入法处理的待排数组是有序数组时:
    • 当处理顺序与有序数组的顺序表现一致时,时间复杂度为O(n);
    • 当处理顺序与有序数组的顺序表现相反时,为最坏场景。  
  • 二分插入在直接插入法取得0(n)时间复杂度时,其最好表现也是O(nlog2(n))。但是当n很大时,其搜索插入点时比较的次数会比直接插入法少得多,但是由于找到插入点,两个算法都需要对后续部分元素进行挪动,故时间复杂度一样为O(n^2)。=。=二分插入大喊我不服!  
  • 希尔排序对比与直接插入法,当待排数组元素个数n值很大时,增量m(数据项的距离)也很大,数据项每一趟排序需要的个数很少;当n值减小时每一趟需要和动的数据增多,但已经接近于排序后的最终位置。这使得希尔排序效率比插入排序高很多。但是对于n很大时,我们会选择更好的算法,如快排等!需要注意的是,希尔的最坏时间复杂度会收增量算法的影响。
  • 当在某一趟冒泡排序中没有出现过元素交换,则认为剩余的元素都是有序状态,可以直接停止!
  • 选择排序实际上我是不推荐使用,在任何场景下都会默认走一遍比较,就是那么辣鸡!
  • 快排优化方案
    • 三平均分区法,选择待排数组的第一个数作为中轴,而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。
    • 当快排处理大数据过程中,当数据集被递归到较小时,改用堆排序(Instrosirt)来克服在处理小规模数据中复杂的中轴选择;或者在规模达到一定小的情况下,改用插入排序,这时几乎是线性处理效果。
    • 当块排分区的所有元素都一样时会出现选轴糟糕状态,可以把分区分成三部分,小于等于大于中轴值;或当发现最左和最右两个值相等时采用其他排序算法。         
  • 快速排序过程中,每次划分分区为1和n-1为最坏情况,此时为时间复杂度为O(n^2);而最好的情况出现在每次划分的分区都为n/2。   
  • 上述表格中,快速排序的空间复杂度O(1)为辅助变量空间;但是对于递归空间来说,当出现最坏情况,其会被退化为冒泡排序,且空间复杂度为O(n);当在最有情况下,其空间复杂度为O(log2(n))。
  • 归并排序中,所使用的空间为临时空间n加上递归使用的空间log2(n),故空间复杂度为O(n)。
  • 对于桶排序,如N个待排数据,M个桶,平均每个桶[N/M]个数据的桶排序平均时间复杂度为:
    O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-NlogM)
    当N=M时,即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
    总结:桶排序的平均时间复杂度为线性的O(N+C),其中C=N
    (logN-logM),如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。

算法实现

考虑到java编程中,除了基础类型的比较之外经常涉及到对象之间的比较。意味着,特定类实现 Comparable 接口即可在逻辑上给定对象之间的比较逻辑。下面算法的实现大部分都是基于 Comparable 实例展开。

直接插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 插入排序 - 直接插入(稳定)
* 基本思想:从待排数组第二位到尾部最后一位元素,依次向元素的前方比较插入;后一趟开始插入时,默认前面的元素是有序的。
*
* @param types
* @param <SortType>
*/
public static <SortType extends Comparable<? super SortType>> void insertionSort(SortType[] types) {

if(types == null || types.length == 0){
return;
}
int length = types.length;
//插入排序默认n-1是已排序的
for (int i = 1; i < length; i++) {
SortType temp = types[i];
//从temp的前一位开始比较
int j = i - 1;
while (j >= 0 && temp.compareTo(types[j]) < 0) {
//如果比较数比temp大,则把比较数赋值给其后面的一个数
//赋值完之后“j这个位置的值暂时不确定”
types[j + 1] = types[j];
j--;
}
//赋值时机出现在:
//1. 如果“前一个数”的下标已经是0,即意味着插入的数是目前所有比较数中最小的,插在头部
//2. 如果“前一个数”比temp小时,则上述“暂时不确定值的位置”插入temp。
types[j + 1] = temp;
}
}

二分插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* 插入排序 - 二分插入(稳定)
* 基本思想:基于直接插入的过程中“后一趟开始插入是,默认前面的元素是有序的”的前提,可以选择对前面的元素进行二分查找后
* 找到小于“当前想要插入元素”的最大元素,把元素的后面所有元素(但在当前想要插入元素之前)往后挪一位,再把想要插入的元
* 素插入留空未知。
*
* @param types
* @param <SortType>
*/
public static <SortType extends Comparable<? super SortType>> void bInsertSort(SortType[] types) {

if(types == null || types.length == 0){
return;
}
int length = types.length;
//插入排序默认n-1是已排序的
for (int i = 1; i < length; i++) {
SortType temp = types[i];
int start = 0;
int end = i - 1;
//跳出循环时必定,end为小于temp的最大元素,start为大于temp的最小元素
while (start <= end) {
int mid = (start + end) / 2;
if (types[mid].compareTo(temp) < 0) {
start = mid + 1;
} else {
end = mid - 1;
}
}
int j = i;
while (j > end && j > 0) {
types[j] = types[j - 1];
j--;
}
types[end + 1] = temp;
}
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* 插入排序 - 希尔排序(不稳定)
* 基本思想:高级版的插入排序,制定增量规则进行分组插入,逐步让增量变小直到为1完成排序
*
* @param types
* @param <SortType>
*/
public static <SortType extends Comparable<? super SortType>> void shellSort(SortType[] types) {

if(types == null || types.length == 0){
return;
}
int length = types.length;
int increment = length / 2;
//增量递减
while (increment > 0) {
//在增量区间内进行插入排序,保证所有数都能被处理
for (int i = 0; i < increment; i++) {
//插入排序
for (int j = i + increment; j < length; j += increment) {
SortType temp = types[j];
int k = j - increment;
while (k >= 0 && types[k].compareTo(temp) > 0) {
types[k + increment] = types[k];
k -= increment;
}
types[k + increment] = temp;
}
}
increment /= 2;
}
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* 冒泡排序(稳定)
* 基本思想:第一次从头部开始向尾部冒泡,第一次过后最大的数出现在尾部;第二次也是从头部开始,不过只需要处理到倒数第二位...依次处理
*
* @param types
* @param <SortType>
*/
public static <SortType extends Comparable<? super SortType>> void bubbleSort(SortType[] types) {

if(types == null || types.length == 0){
return;
}
int lenght = types.length;
boolean exchange;
for (int i = 0; i < lenght - 1; i++) {
exchange = false;
for (int j = 0; j < lenght - i - 1; j++) {
if (types[j].compareTo(types[j + 1]) > 0) {
SortType temp = types[j];
types[j] = types[j + 1];
types[j + 1] = temp;
exchange = true;
}
}
if(!exchange){
break;
}
}
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* 选择排序(不稳定)
* 基本思想:其实类似与冒泡排序,区别在于不直接交换且每一趟只比较当“前趟的最后一位元素”。
* 从头部到“尾部往前一位”找出最大的值,并放到尾部
*
* @param types
* @param <SortType>
*/
public static <SortType extends Comparable<? super SortType>> void selectSort(SortType[] types) {

if(types == null || types.length == 0){
return;
}
int length = types.length;
for (int i = 0; i < length - 1; i++) {
//默认当前末尾最大
int max = length - 1 - i;
for (int j = 0; j < length - 1 - i; j++) {
if (types[j].compareTo(types[max]) > 0) {
max = j;
}
}
if (max != length - 1 - i) {
SortType temp = types[max];
types[max] = types[length - 1 - i];
types[length - 1 - i] = temp;
}
}
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* 堆排序(不稳定)
* 整个堆排序过程分为:
* 1. 初始化大/小根堆
* 2. 交换极值重新调整堆{@link #headAdjust}
*
* @param types
* @param <SortTpye>
*/
public static <SortTpye extends Comparable<? super SortTpye>> void heapSort(SortTpye[] types) {

if(types == null || types.length == 0){
return;
}
int length = types.length;
//从下往上建堆,且保证从非叶子结点开始建堆
for (int i = length / 2 - 1; i >= 0; i--) {
headAdjust(types, i, length - 1);
}
//交换堆顶之后重新调整
for (int i = length - 1; i >= 0; i--) {
SortTpye temp = types[i];
types[i] = types[0];
types[0] = temp;
headAdjust(types, 0, i - 1);
}
}

/**
* 从数组按照下标展开构建完全二叉树时,若非结点结点下边为n,则左孩子为2n+1,右孩子为2n+2;
*
* @param types
* @param start
* @param end
* @param <SortTpye>
*/
public static <SortTpye extends Comparable<? super SortTpye>> void headAdjust(SortTpye[] types, int start, int end) {
int lChild = 2 * start + 1;
int rChild = 2 * start + 2;
//假设当前父节点最大
int max = start;
//保证从非叶子结点开始检索,若一个孩子为偶数结点,则按照“右孩子为2n+2”的规则/2-1;
int flag = (end % 2 == 0 ? end / 2 - 1 : end / 2);
if (start <= flag) {
//如果左结点不超过end且比父亲结点大
if (lChild <= end && types[lChild].compareTo(types[max]) > 0) {
max = lChild;
}
//如果右结点不超过end且比父亲结点大
if (rChild <= end && types[rChild].compareTo(types[max]) > 0) {
max = rChild;
}
//如果发生交换,则交换后递归调整
if (max != start) {
SortTpye temp = types[max];
types[max] = types[start];
types[start] = temp;
headAdjust(types, max, end);
}
}
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* 快速排序(不稳定)
* 基本思想:每一趟排序都会把待排的数据分割成独立的两部分,其中一部分的所有数据会比另一部分的所有数据都要小。
* 递归处理
*
* @param types
* @param <SortTpye>
*/
public static <SortTpye extends Comparable<? super SortTpye>> void quickSort(SortTpye[] types, int start, int end){
if(types == null || types.length == 0){
return;
}
if(start < end){
int position = getPosition(types, start, end);
quickSort(types, start, position-1);
quickSort(types, position+1, end);
}
}

/**
* 获取临街值
* @param types
* @param start
* @param end
* @param <SortTpye>
* @return
*/
public static <SortTpye extends Comparable<? super SortTpye>> int getPosition(SortTpye[] types, int start, int end){
SortTpye flag = types[start];
while(start < end){
//从尾部往前一直找,如果找到比flag小,则与第一个数交换
while(start < end && types[end].compareTo(flag) >= 0){
end --;
}
types[start] = types[end];
//从头部往后一直找,如果找到比flag大,则
while (start < end && types[start].compareTo(flag) <= 0){
start++;
}
types[end] = types[start];
}
types[start] = flag;
return start;
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
* 归并排序(稳定)
* 基本思想:分而治之,递归处理。
*
* @param types
* @param start
* @param end
* @param <SortTpye>
*/
public static <SortTpye extends Comparable<? super SortTpye>> void mergeSort(SortTpye[] types, int start, int end){
if(types == null || types.length == 0){
return;
}
int mid = (start + end)/2;
if(start < end){
mergeSort(types,start,mid);
mergeSort(types,mid+1,end);
merge(types,start,mid,end);
}
}

/**
* 合并两个元素数组
*
* @param types
* @param start
* @param mid
* @param end
* @param <SortTpye>
*/
public static <SortTpye extends Comparable<? super SortTpye>> void merge(SortTpye[] types,int start, int mid, int end){
SortTpye[] temp = (SortTpye[]) new Comparable[end-start+1];
int i = start;//左侧数组头部
int j = mid + 1; //右侧数组头部
int index = 0;
//存放到临时区,直到其中一个数组全部填入
while(i <= mid && j <= end){
if(types[i].compareTo(types[j]) < 0){
temp[index++] = types[i++];
}else{
temp[index++] = types[j++];
}
}
//左侧数组是否剩余
while(i <= mid){
temp[index++] = types[i++];
}
//右侧数据是否剩余
while(j <= end){
temp[index++] = types[j++];
}

for(index = 0; index < temp.length; index++){
types[start+index] = temp[index];
temp[index] = null;
}
temp = null;
}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* 计数排序
* 基本思想:对于待排数组中的某一个元素types[n],确定小于types[n]的元素个数
* 需要借助的空间,假如待排数组中最小对象的值为10,最大对象的值为100,则需要一个(100-10+1)的辅助空间,
* 适合的场景:数据值比较集中的待排数集
*
* @param nums
*/
public static void countSort(Integer[] nums){

if(nums == null || nums.length == 0){
return;
}
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int length = nums.length;
for(int i = 0; i < nums.length; i++){
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}

int tLength = max-min+1;
int[] temp = new int[tLength];

//在temp空间中存放每个数字出现的次数
for(int i = 0; i < length; i++){
temp[nums[i]-min]++;
}


int index = 0;
for(int i = 0; i < tLength; i++){
//某个位置的个数不为0
while(temp[i]-- > 0){
nums[index++] = i + min;
}
}
}

桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* 桶排序
* 基本思想:先确定数值范围(这部分和技术排序相同),再按照一定的规则初始化桶
* 初始化完桶之后里面的元素为排序,可选择任意一种方式进行排序。
*
* @param nums
*/
public static void bucketSort(Integer[] nums){

if(nums == null || nums.length == 0){
return;
}
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int length = nums.length;
for(int i = 0; i < length; i++){
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}

//初始化桶
//可以看出,如果max、min区间特别大但是数组个数特别小,则会有很多桶分布
int bucketNum = (max - min) / length + 1;
ArrayList<ArrayList<Integer>> bucketArry = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++){
bucketArry.add(new ArrayList<>());
}

//入桶
for(int i = 0; i < length; i++){
int index = (nums[i]-min) / length;
bucketArry.get(index).add(nums[i]);
}

//对每个桶进行排序,这里借用java api直接排序
for(int i = 0; i < bucketArry.size(); i++){
Collections.sort(bucketArry.get(i));
}
}

10W随机数测试

直接上测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    public static void main(String[] args){
int num = 100000;
Integer[] types = new Integer[num];
Random random = new Random();
for(int i = 0; i <num; i++){
types[i] = random.nextInt(num);
}
long time1 = System.currentTimeMillis();
// Sort.insertionSort(types);
// Sort.bInsertSort(types);
// Sort.shellSort(types);
// Sort.bubbleSort(types);
// Sort.selectSort(types);
// Sort.heapSort(types);
// Sort.quickSort(types,0,num-1);
// Sort.mergeSort(types,0,num-1);
// Sort.countSort(types);
// Sort.bucketSort(types);
long time2 = System.currentTimeMillis();
System.out.print(time2-time1 + "ms");
}

由于每次测试花费时间都是重新产生数组,可能会导致排序的难度场景不太相同,但是对于整体验证复杂度还是可以比较直观体验。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
测试机器:
cpu: 4核 Intel(R) Core(TM) i5-6300HQ CPU @ 2.30GHz
内存:8G
测试结果:
直接插入:11782ms
二分插入:8464ms
希尔排序:65ms
冒泡排序:56564ms
选择排序:14697ms
堆排序:72ms
快速排序:61ms
归并排序:115ms
计数排序:11ms
桶排序:62ms

忽略测试数据的随机性,大致参考总结为:

  • 计数和桶排序都非常快,但是消耗了更多的额外空间,具体场景具体取舍
  • 堆排序/快排序/归并排序表现差不多,这三者大部分场景下都优于希尔排序
  • 数据量大适合快速排序和归并排序,数据量小可考虑堆排序,且堆排序稳定性最高

作者水平有限,本文仅供参考学习,如有错误遗漏,望慷慨指出!