八种排序算法的总结及性能分析

1.排序基础

①基础知识

  • 稳定性:任意两个相等的数据,排序前后的相对位置不发生改变。
  • 内排序:在排序期间数据对象全部存放在内存中的排序。
  • 原地排序:在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
  • 非原地排序:需要利用额外的空间来辅助排序。
  • 逆序对:对于下标 i < j,如果 A[i] > A[j],则称 (i, j) 是一对逆序对。
    • 交换 2 个相邻元素正好可以消去 1 个逆序对。
  • 讨论规则:
    • 只讨论升序的整数排序
    • 只讨论基于比较的排序
    • 只讨论内部排序
  • 排序算法一览(图片来源于网络):

Alt text

②自定义辅助函数

  • 排序接口(所有排序类都会实现这个接口)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package sort;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 排序接口
*/
public interface Sort {

/**
* 功能描述: 对长度为n的数组中的元素进行升序排序
*
* @param: [arr, n]
* @return: void
* @auther: wjy
* @date: 2020/2/12 20:24
*/
void ascendSort(int[] arr, int n);
}
  • 构造待排序的数组
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
package sort.util;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 构造待排序的数组
*/
public class RandomArray {

/**
* 功能描述: 生成长度为n的数组,并且数组元素的范围在rangeL~rangeR之间。
*
* @param: [n, rangeL, rangeR]
* @return: int[]
* @auther: wjy
* @date: 2020/2/12 20:27
*/
public static int[] generateRandomArray(int n, int rangeL, int rangeR) {
int[] arr = new int[n];
if (rangeL <= rangeR) {
for (int i = 0; i < n; i++) {
arr[i] = (int) (Math.random() * (rangeR - rangeL + 1) + rangeL);
}
}
else {
System.out.println("rangeL > rangeR");
}
return arr;
}

/**
* 功能描述: 生成近乎有序的长度为n的数组,并且可以自定义逆序对个数。
*
* @param: [n, swapTimes]
* @return: int[]
* @auther: wjy
* @date: 2020/2/12 20:28
*/
public static int[] generateNearlyRandomArray(int n, int swapTimes) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i;
}
for (int i = 0; i < swapTimes; i++) {
int x = (int) (Math.random() * n);
int y = (int) (Math.random() * n);
SortHelper.swap(arr, x, y);
}
return arr;
}
}
  • 排序辅助函数
    • 方法一:验证数组是否有序(升序)
    • 方法二:打印数组
    • 方法三:交换数组中的元素
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
package sort.util;

/**
* @author: wjy
* @date: 2020/2/12
* @description: 排序辅助函数
*/
public class SortHelper {

/**
* 功能描述: 验证数组是否有序(升序)
*
* @param: [arr, n]
* @return: boolean
* @auther: wjy
* @date: 2020/2/12 22:31
*/
public static boolean isAscendingOrder(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
return false;
}
}
return true;
}

/**
* 功能描述: 打印数组
*
* @param: [arr, n]
* @return: void
* @auther: wjy
* @date: 2020/2/12 22:30
*/
public static void printArray(int[] arr, int n) {
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

/**
* 功能描述: 交换数组中的元素
*
* @param: [arr, i, j]
* @return: void
* @auther: wjy
* @date: 2020/2/12 22:31
*/
public static void swap(int[] arr, int i, int j) {
if (i != j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = 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
package sort;

import sort.util.SortHelper;

import java.time.Instant;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 测试排序算法的性能
*/
public class TestSort {

/**
* 功能描述: 测试排序算法的性能,打印执行用时及排序的正确性。
*
* @param: [name, sort, arr, n]
* @return: void
* @auther: wjy
* @date: 2020/2/12 20:41
*/
public static void testSort(String name, Sort sort, int[] arr, int n) {
long start = Instant.now().toEpochMilli();
sort.ascendSort(arr, n);
long end = Instant.now().toEpochMilli();
System.out.println(name + "用时: " + (end - start) + "ms");
System.out.println("排序后数组是否升序: " + SortHelper.isAscendingOrder(arr, n));
}
}

③为什么要学习 O(n^2) 的排序算法?

O(n^2) 的排序算法:所消耗的时间和数据之间成平方关系。

  1. 基础。先用最简单的方法解决问题,能加深对问题本身的理解,进而优化或者衍生出更复杂的解法(希尔排序就是通过插入排序的思想进行优化衍生而来的)。
  2. 并不是所有场合都需要写 O(n*logn) 复杂度的排序算法。O(n^2) 复杂度的排序算法编码简单,易于实现,是一些简单情景的首选。
  3. 在一些特殊情况下,简单的排序算法更有效。
  4. 作为子过程,可以改进更复杂的排序算法。

2.交换排序类 — 简单交换排序

①排序思路

  • 方法:每一个位置的关键字与其后的所有关键字依次做比较,大则交换。
  • 结果:执行第 i 次外层 for 循环后,第 i - 1 个位置上的关键字一定小于其后的所有关键字,并且其后的其他关键字还保持着未排序前的相对顺序。
  • 缺点:每执行一次外层 for 循环,虽然进行了很多次的交换操作,但是只能消除一个逆序对。

②代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package sort.swapsort;

import sort.Sort;
import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 交换排序类-简单交换排序
*/
public class SimpleSwapSort implements Sort {

@Override
public void ascendSort(int[] arr, int n) {
for (int i = 0; i < n - 1; i++) {
// 将索引i处的元素与其后的元素依次比较,若大于其后的元素就交换位置。
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
SortHelper.swap(arr, i, j);
}
}
}
}
}

③性能分析

  • 稳定性:不稳定
  • 是否是原地排序:是
  • 平均时间复杂度:O(n^2)
  • 最好的情况:O(n^2)(顺序)
  • 最坏的情况:O(n^2)(逆序)
  • 空间复杂度:O(1)

3.交换排序类 — 冒泡排序

①排序思路

  • 方法:(从后向前)依次比较两个相邻的元素,前一个元素大则交换位置,这样较小的元素就如同气泡般慢慢浮到上面,所以称之为冒泡排序法。
  • 传统的冒泡排序
    • 方法:依次两两比较(从后向前)并交换位置后,arr[i] 变为 [i, n-1] 区间里的最小值。若某次循环全程无交换,表明数组已经有序,提前退出循环。
  • 改进的冒泡排序
    • 方法: 记录最后一次的交换位置,在此之前的元素(已经有序)在下一轮扫描中均不考虑。
  • 优点:排序链表较为方便

②代码演示

  • 传统的冒泡排序
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
package sort.swapsort;

import sort.Sort;
import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 交换排序类-传统的冒泡排序
*/
public class BubbleSort implements Sort {

@Override
public void ascendSort(int[] arr, int n) {
for (int i = 0; i < n; i++) {
int flag = 0;
// 依次两两比较并交换位置后,arr[i]变为[i, n-1]区间里的最小值。
for (int j = n - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
SortHelper.swap(arr, j, j - 1);
// 标识一趟冒泡排序中发生了交换。
flag = 1;
}
}
// 全程无交换,表明数组已经有序。
if (flag == 0) {
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
package sort.swapsort;

import sort.Sort;
import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 交换排序类-改进的冒泡排序
*/
public class AdvancedBubbleSort implements Sort {

@Override
public void ascendSort(int[] arr, int n) {
int index = -1;
for (int i = index + 1; i < n; i++) {
// 依次两两比较并交换位置后,arr[i]变为[i, n-1]区间里的最小值。
for (int j = n - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
SortHelper.swap(arr, j, j - 1);
// 记录最后一次的交换位置,在此之前的元素(已经有序)在下一轮扫描中均不考虑。
index = j - 1;
}
}
}
}
}

③性能分析

  • 稳定性:稳定
  • 是否是原地排序:是
  • 平均时间复杂度:O(n^2)
  • 最好情况:O(n)(顺序)
  • 最坏情况:O(n^2)(逆序)
  • 空间复杂度:O(1)
  • 冒泡排序在各种情况下的性能都没有插入排序好

4.选择排序类 — 简单选择排序

①排序思路

  • 方法:首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后再从剩余未排序序列中继续寻找最小元素,放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
  • 优点:所需移动元素的次数比较少
  • 可以看做是简单交换排序的优化(每次找到最小值再交换)

②代码演示

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
package sort.selectsort;

import sort.Sort;
import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 选择排序类-简单选择排序
*/
public class SimpleSelectSort implements Sort {

@Override
public void ascendSort(int[] arr, int n) {
for (int i = 0; i < n; i++) {
// 寻找[i, n)区间里的最小值,其索引为minIndex。
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
SortHelper.swap(arr, i, minIndex);
}
}
}

③性能分析

  • 稳定性:不稳定
  • 是否是原地排序:是
  • 平均时间复杂度:O(n^2)
  • 最好情况:O(n^2)(顺序)
  • 最坏情况:O(n^2)(逆序)
  • 空间复杂度:O(1)

5.插入排序类 — 直接插入排序

①排序思路

  • 方法:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。(类比整理扑克牌的思想)。
  • 特点:
    • 在数组基本有序的情况下性能会非常高,远远优于选择排序,甚至比 O(n*logn) 级别的排序算法还要快,有重要的实际意义。
    • 可以在更加复杂的排序算法中作为子过程来进行优化
  • 插入排序和选择排序的最大区别:对于内层循环,当找到插入位置时,插入排序可以提前结束。
  • 插入排序和冒泡排序都需要消除逆序对,交换次数是一样的。

②代码演示

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
package sort.insertsort;

import sort.Sort;

/**
* @author: wjy
* @date: 2020/2/12
* @description: 插入排序类-直接插入排序
*/
public class DirectInsertSort implements Sort {

@Override
public void ascendSort(int[] arr, int n) {
// 第1个元素(索引为0)默认有序
for (int i = 1; i < n; i++) {
// 寻找元素e合适的插入位置
int e = arr[i], j = i;
for (; j > 0 && arr[j - 1] > e; j--) {
// 向后移出空位
arr[j] = arr[j - 1];
}
// 找到了合适的插入位置
arr[j] = e;
}
}
}

③性能分析

  • 稳定性:稳定
  • 是否是原地排序:是
  • 平均时间复杂度:O(n^2)
  • 最好情况:O(n)(顺序)
  • 最坏情况:O(n^2)(逆序)
  • 空间复杂度:O(1)

6.插入排序类 — 希尔排序

①排序思路

  • 定理 1:任意 n 个不同元素组成的序列平均具有 n * (n - 1) / 4 个逆序对。
  • 定理 2:任何仅以交换相邻两个元素进行排序的算法(每次只能消去一个逆序对),其平均时间复杂度都为 O(n^2)
  • 这意味着想要提高排序算法的效率,我们每次必须消去不止一个逆序对,所以我们需要每次交换相隔较远的两个元素,此时就可以一次消去多个逆序对(希尔排序的思想)。
  • 方法:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。
  • 步骤:
    1. 定义增量序列(递减到 1)
    2. 对每个增量进行增量间隔的直接插入排序
  • 注意:
    • "Dk-间隔" 有序的序列,在执行 "Dk-1-间隔" 排序后,其 "Dk-间隔" 仍然是有序的。
    • 为了保证结果有序,最后必须进行一次 1 间隔的排序(在进行 1 间隔的排序前,整个数组已经基本有序)。
  • Hibbard 增量:Dk = 2 ^ k - 1
    • 增量元素不互质,则小增量可能根本不起作用。
    • 递推公式为:D1 = 1、D2 = 3、D3 = 7、Dk = 2 * D(k − 1) + 1、D (k - 1) = (Dk - 1) / 2
  • 特点:
    • 是插入排序的改进版本,克服了插入排序每次只交换相邻两个元素的缺点。
    • 实现起来比 O(n*logn) 级别的排序算法简单

②代码演示

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
package sort.insertsort;

import sort.Sort;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 插入排序类-希尔排序
*/
public class ShellSort implements Sort {

@Override
public void ascendSort(int[] arr, int n) {
// Hibbard增量: Dk=2^k-1
// 递推公式为: D1=1、D2=3、D3=7、Dk=2D(k−1)+1、D(k-1)=(Dk-1)/2
// k 1 2 3 5 6
// Dk(d) 1 3 7 15 31
int d = 1;
while (d < n / 3) {
// D(k-1)->D(k)
d = d * 2 + 1;
}
while (d >= 1) {
// d间隔的插入排序
// 第1个元素(索引为0)默认有序
for (int i = d; i < n; i++) {
// 寻找元素e合适的插入位置
int e = arr[i], j = i;
for (; j >= d && arr[j - d] > e; j -= d) {
// 向后移出空位
arr[j] = arr[j - d];
}
// 找到了合适的插入位置
arr[j] = e;
}
// D(k)->D(k-1)
d = (d - 1) / 2;
}
}
}

③性能分析

  • 稳定性:不稳定
  • 是否是原地排序:是
  • 平均时间复杂度:O(n^5/4)
  • 最好情况:O(n^5/4)(顺序)
  • 最坏情况:O(n^3/2)(逆序)
  • 空间复杂度:O(1)

7.归并排序类 — 归并排序

①排序思路

  • 方法:

Alt text
Alt text

  • 归并排序(递归)
    • 归并层数:logn 层(二分法),每层要处理的元素个数是一样的。
    • 每层的归并过程的时间复杂度为 O(n)
  • 改进的归并排序(递归)
    • 优化 1:当 n 小到一定程度的时候,插入排序比归并排序快,此时用插入排序代替归并排序(元素很少时,数组近乎有序的可能性变大,插入排序有优势,排序的高级算法都可如此优化)。
    • 优化 2:如果两部分各自有序,就不需要继续归并了。
  • 自底向上的归并排序(迭代)
  • 改进的自底向上的归并排序(迭代)
    • 优化方法同 改进的归并排序(递归)
  • 优点:
    • 适用于排序链表
    • 优化后的归并排序在排序近乎有序的数组时,速度也很快。
  • 缺点:空间复杂度为 O(n)
    • 现代计算机中时间效率比空间效率重要的多,设计算法优先考虑时间复杂度,除非数据存储的空间是算法的重要瓶颈。

②代码演示

  • 归并排序
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
62
63
64
65
66
67
68
69
70
package sort.mergesort;

import sort.Sort;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 归并排序
*/
public class MergeSort implements Sort {

/**
* 功能描述: 归并两个有序部分(arr[l...mid]和arr[mid+1...r])
*
* @param: [arr, l, mid, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 3:10
*/
public static void merge(int[] arr, int l, int mid, int r) {
// 使用临时空间辅助我们完成归并过程
int[] aux = new int[r - l + 1];
for (int i = l; i <= r; i++) {
aux[i - l] = arr[i];
}
// i和j分别指向两个有序部分的元素,k指向两个元素比较后小的那个元素的存储位置。
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
// 第一个有序部分已经遍历完成
if (i > mid) {
arr[k] = aux[j++ - l];
}
// 第二个有序部分已经遍历完成
else if (j > r) {
arr[k] = aux[i++ - l];
}
else if (aux[i - l] > aux[j - l]) {
arr[k] = aux[j++ - l];
}
else {
arr[k] = aux[i++ - l];
}
}
}

/**
* 功能描述: 对arr[l...r]部分进行归并排序
*
* @param: [arr, l, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 3:10
*/
public void recursion(int[] arr, int l, int r) {
if (l >= r) {
return;
}
// 避免发生溢出,使用位运算。
int mid = (l + r) >>> 1;
recursion(arr, l, mid);
recursion(arr, mid + 1, r);
// 归并两个有序部分(arr[l...mid]和arr[mid+1...r])
merge(arr, l, mid, r);
}

@Override
public void ascendSort(int[] arr, int n) {
recursion(arr, 0, n - 1);
}
}
  • 改进的归并排序
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package sort.mergesort;

import sort.Sort;

/**
* @author: wjy
* @date: 2020/2/12
* @description: 归并排序-改进的归并排序
*/
public class AdvancedMergeSort implements Sort {

/**
* 功能描述: 对arr[l...r]部分进行插入排序
*
* @param: [arr, l, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 0:10
*/
public static void sort(int[] arr, int l, int r) {
// 第1个元素(索引为l)默认有序
for (int i = l + 1; i <= r; i++) {
// 寻找元素e合适的插入位置
int e = arr[i], j = i;
for (; j > l && arr[j - 1] > e; j--) {
// 向后移出空位
arr[j] = arr[j - 1];
}
// 找到了合适的插入位置
arr[j] = e;
}
}

/**
* 功能描述: 归并两个有序部分(arr[l...mid]和arr[mid+1...r])
*
* @param: [arr, l, mid, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 3:10
*/
public static void merge(int[] arr, int l, int mid, int r) {
// 使用临时空间辅助我们完成归并过程
int[] aux = new int[r - l + 1];
for (int i = l; i <= r; i++) {
aux[i - l] = arr[i];
}
// i和j分别指向两个有序部分的元素,k指向两个元素比较后小的那个元素的存储位置。
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
// 第一个有序部分已经遍历完成
if (i > mid) {
arr[k] = aux[j++ - l];
}
// 第二个有序部分已经遍历完成
else if (j > r) {
arr[k] = aux[i++ - l];
}
else if (aux[i - l] > aux[j - l]) {
arr[k] = aux[j++ - l];
}
else {
arr[k] = aux[i++ - l];
}
}
}

/**
* 功能描述: 对arr[l...r]部分进行归并排序
*
* @param: [arr, l, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 10:16
*/
public void recursion(int[] arr, int l, int r) {
if (l >= r) {
return;
}
// 优化1: 当n小到一定程度时,插入排序比归并排序快,此时用插入排序代替归并排序。
if (r - l <= 15) {
sort(arr, l, r);
}
// 避免发生溢出,使用位运算。
int mid = (l + r) >>> 1;
recursion(arr, l, mid);
recursion(arr, mid + 1, r);
// 优化2: 如果两部分各自有序,就不需要继续归并了。
if (arr[mid + 1] < arr[mid]) {
merge(arr, l, mid, r);
}
}

@Override
public void ascendSort(int[] arr, int n) {
recursion(arr, 0, n - 1);
}
}
  • 自底向上的归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package sort.mergesort;

import sort.Sort;

/**
* @author: wjy
* @date: 2020/2/13
* @description: 归并排序-自底向上的归并排序
*/
public class IterationMergeSort implements Sort {

@Override
public void ascendSort(int[] arr, int n) {
// i: 1、2、4、8...
for (int i = 1; i <= n; i += i) {
for (int j = 0; j + i < n; j += i + i) {
// 对arr[j...j+i-1]和arr[j+i...j+i+i-1]进行归并
AdvancedMergeSort.merge(arr, j, j + i - 1, Math.min(j + i + i - 1, n - 1));
}
}
}
}
  • 改进的自底向上的归并排序
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
package sort.mergesort;

import sort.Sort;

/**
* @author: wjy
* @date: 2020/3/13
* @description: 归并排序-改进的自底向上的归并排序
*/
public class AdvancedIterationMergeSort implements Sort {

/**
* 功能描述: 对arr[l...r]部分进行插入排序
*
* @param: [arr, l, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 0:10
*/
public static void sort(int[] arr, int l, int r) {
// 第1个元素(索引为l)默认有序
for (int i = l + 1; i <= r; i++) {
// 寻找元素e合适的插入位置
int e = arr[i], j = i;
for (; j > l && arr[j - 1] > e; j--) {
// 向后移出空位
arr[j] = arr[j - 1];
}
// 找到了合适的插入位置
arr[j] = e;
}
}

@Override
public void ascendSort(int[] arr, int n) {
// 优化1: 当n小到一定程度时,插入排序比归并排序快,此时用插入排序代替归并排序。
for (int i = 0; i < n; i += 16) {
sort(arr, i, Math.min(i + 15, n - 1));
}
// i: 16、32、64...
for (int i = 16; i <= n; i += i) {
for (int j = 0; j + i < n; j += i + i) {
// 优化2: 如果两部分各自有序,就不需要继续归并了。
if (arr[j + i - 1] > arr[j + i]) {
AdvancedMergeSort.merge(arr, j, j + i - 1, Math.min(j + i + i - 1, n - 1));
}
}
}
}
}

③性能分析

  • 稳定性:稳定
  • 是否是原地排序:否
  • 平均时间复杂度:O(n*logn)
  • 最好情况:O(n*logn)(顺序)
  • 最坏情况:O(n*logn)(逆序)
  • 空间复杂度:O(n)

④衍生问题 — 求一个数组中逆序对的数量

  • 我们再来复习一下什么是逆序对:对于下标 i < j,如果 A[i] > A[j],则称 (i, j) 是一个逆序对。
  • 数组中逆序对的数量可以衡量一个数组的有序程度。
  • 方法一(O(n^2)):使用双重循环考察每一个数对,暴力解法。
  • 方法二(O(n*logn)):归并排序的思路求逆序对的个数。
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package sort.derivedquestion;

import sort.util.RandomArray;

/**
* @author: wjy
* @date: 2020/2/13
* @description: 归并排序的思路求逆序对的个数
*/
public class ReversePairsNumber {

/**
* 功能描述: 求出在arr[l...mid]和arr[mid+1...r]有序的基础上,arr[l...r]的逆序数对个数。
*
* @param: [arr, l, mid, r]
* @return: long
* @auther: wjy
* @date: 2020/2/13 11:42
*/
public long merge(int[] arr, int l, int mid, int r) {
// 初始化逆序对个数
long number = 0;
// 使用临时空间辅助我们完成归并过程
int[] aux = new int[r - l + 1];
for (int i = l; i <= r; i++) {
aux[i - l] = arr[i];
}
// i和j分别指向两个有序部分的元素,k指向两个元素比较后小的那个元素的存储位置。
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
// 第一个有序部分已经遍历完成
if (i > mid) {
arr[k] = aux[j++ - l];
}
// 第二个有序部分已经遍历完成
else if (j > r) {
arr[k] = aux[i++ - l];
}
else if (aux[i - l] > aux[j - l]) {
// aux[j-l]<aux[i-l],说明aux[i-l...mid]之间的所有元素都与aux[j-1]构成了逆序对。
arr[k] = aux[j++ - l];
number += (long) (mid - i + 1);
}
else {
arr[k] = aux[i++ - l];
}
}
return number;
}

/**
* 功能描述: 对arr[l...r]部分进行归并排序
*
* @param: [arr, l, r]
* @return: long
* @auther: wjy
* @date: 2020/2/13 11:14
*/
public long recursion(int[] arr, int l, int r) {
if (l >= r) {
return 0L;
}
// 避免发生溢出,使用位运算。
int mid = (l + r) >>> 1;
long number1 = recursion(arr, l, mid);
long number2 = recursion(arr, mid + 1, r);
return number1 + number2 + merge(arr, l, mid, r);
}

public long ascendSort(int[] arr, int n) {
return recursion(arr, 0, n - 1);
}

public static void main(String[] args) {
int n = 1000;

// 1.测试完全有序的数组
int[] arr = RandomArray.generateNearlyRandomArray(n, 0);
System.out.println("测试完全有序的数组: " + new ReversePairsNumber().ascendSort(arr, n));

// 2.测试逆序的数组(正确答案: n*(n-1)/2)
for (int i = 0; i < n; i++) {
arr[n - i - 1] = i;
}
System.out.println("测试逆序的数组: " + new ReversePairsNumber().ascendSort(arr, n));

// 3.测试随机数组
arr = RandomArray.generateNearlyRandomArray(n, 10);
System.out.println("测试随机数组: " + new ReversePairsNumber().ascendSort(arr, n));
}
}

Alt text


8.交换排序类 — 快速排序

①排序思路

  • 快速排序
    • 20 世纪对世界影响最大的算法之一
    • 方法:

Alt text

  • 普通快速排序
    • 所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的元素可以放到任何一边)
    • 基准值如何选取:选择数列中的第一个元素
    • 未优化的快速排序在排序随机数组时就已经快于归并排序,但是在排序近乎有序的数组时会非常慢。

Alt text

  • 改进的快速排序
    • 优化 1:当 n 小到一定程度时,插入排序比快速排序快,此时用插入排序代替快速排序。
    • 优化 2:每次随机选择数列中的一个元素作为基准。此时快速排序的最坏情况的时间复杂度依然是 O(n^2) ,但是退化到 O(n^2) 的概率极低。优化后,针对数字范围很小的数组,依然会非常慢(递归树不平衡,当数组有大量重复键值时,很大概率会将数组分成极不平衡的两部分)。
  • 双路快速排序
    • 方法:将与基准值相等的元素分散到左右两部分
    • 优化后在排序近乎有序的数组时也会比归并排序快

Alt text

  • 三路快速排序
    • 方法:将与基准值相等的元素放在中间,下次递归时直接不用处理等于基准值的元素(它们已经在正确的位置上了)。
    • 在存在大量重复键值的情况下,远远快于其他排序,其他情况稍微慢于二路快速排序。

Alt text

  • 归并排序与快速排序的比较
    • 都使用了分治算法的基本思想(分治算法:顾名思义,分而治之,就是将原问题分割成同等结构的子问题,再将子问题逐一解决后,原问题也就得到了解决。)
    • 归并排序的重点在于治,快速排序的重点在于分。
    • 归并排序可以保证每次都将数组平均一分为二,快速排序则无法保证。所以快速排序调用递归的过程所生成的递归树比归并排序的差,且不能完全保证递归树的高度是 logn,最坏情况下递归树的高度是 O(n)(当数组近乎有序时)。
    • nlogn 级别的排序算法也有常数上的差异,快速排序相对占优。
  • 归并排序与快速排序的选择
    • 一般系统级别的排序,都是使用快速排序实现的。
    • 如果一个系统对空间相对敏感,归并排序就不适合。
    • 在系统级别的类库中,若想实现稳定的排序,通常选择的是归并排序。但是也可以通过自定义比较函数,使排序算法不存在稳定性的问题。
  • 缺点:空间复杂度为 O(logn),有 logn 层栈空间来保存每一层递归过程中的临时变量,以供递归返回时调用。

②代码演示

  • 快速排序
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
package sort.swapsort;

import sort.Sort;
import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 交换排序类-快速排序
*/
public class QuickSort implements Sort {

/**
* 功能描述: 对arr[l...r]部分进行partition操作
* 返回index,使得arr[l...index-1] < arr[index]、arr[index+1...r] >= arr[index]。
*
* @param: [arr, l, r]
* @return: int
* @auther: wjy
* @date: 2020/2/13 11:10
*/
public int partition(int[] arr, int l, int r) {
// 使用数组的第一个元素作为分界的标志点
int value = arr[l], j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i] < value) {
SortHelper.swap(arr, i, ++j);
}
}
// 将value移到分界处
SortHelper.swap(arr, l, j);
return j;
}

/**
* 功能描述: 对arr[l...r]部分进行快速排序
*
* @param: [arr, l, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 11:10
*/
public void recursion(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int index = partition(arr, l, r);
recursion(arr, l, index - 1);
recursion(arr, index + 1, r);
}

@Override
public void ascendSort(int[] arr, int n) {
recursion(arr, 0, n - 1);
}
}
  • 改进的快速排序
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package sort.swapsort;

import sort.Sort;
import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/13
* @description: 交换排序类-改进的快速排序
*/
public class AdvancedQuickSort implements Sort {

/**
* 功能描述: 对arr[l...r]部分进行插入排序
*
* @param: [arr, l, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 0:10
*/
public static void sort(int[] arr, int l, int r) {
// 第1个元素(索引为l)默认有序
for (int i = l + 1; i <= r; i++) {
// 寻找元素e合适的插入位置
int e = arr[i], j = i;
for (; j > l && arr[j - 1] > e; j--) {
// 向后移出空位
arr[j] = arr[j - 1];
}
// 找到了合适的插入位置
arr[j] = e;
}
}

/**
* 功能描述: 对arr[l...r]部分进行partition操作
* 返回index,使得arr[l...index-1] < arr[index]、arr[index+1...r] >= arr[index]。
* @param: [arr, l, r]
* @return: int
* @auther: wjy
* @date: 2020/2/13 11:05
*/
public int partition(int[] arr, int l, int r) {
// 优化2: 使用数组中的随机元素作为分界的标志点
SortHelper.swap(arr, l, (int) (Math.random() * (r - l + 1) + l));
int value = arr[l], j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i] < value) {
SortHelper.swap(arr, i, ++j);
}
}
// 将value移到分界处
SortHelper.swap(arr, l, j);
return j;
}

/**
* 功能描述: 对arr[l...r]部分进行快速排序
*
* @param: [arr, l, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 11:04
*/
public void recursion(int[] arr, int l, int r) {
if (l >= r) {
return;
}
// 优化1: 当n小到一定程度时,插入排序比快速排序快,此时用插入排序代替快速排序。
if (r - l <= 15) {
sort(arr, l, r);
}
int index = partition(arr, l, r);
recursion(arr, l, index - 1);
recursion(arr, index + 1, r);
}

@Override
public void ascendSort(int[] arr, int n) {
recursion(arr, 0, n - 1);
}
}
  • 双路快速排序
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package sort.swapsort;

import sort.Sort;
import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/13
* @description: 交换排序类-双路快速排序
*/
public class QuickSort2Ways implements Sort {

/**
* 功能描述: 对arr[l...r]部分进行插入排序
*
* @param: [arr, l, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 0:10
*/
public static void sort(int[] arr, int l, int r) {
// 第1个元素(索引为l)默认有序
for (int i = l + 1; i <= r; i++) {
// 寻找元素e合适的插入位置
int e = arr[i], j = i;
for (; j > l && arr[j - 1] > e; j--) {
// 向后移出空位
arr[j] = arr[j - 1];
}
// 找到了合适的插入位置
arr[j] = e;
}
}

/**
* 功能描述: 返回index,使得arr[l...index-1] <= arr[index]、arr[index+1...r] >= arr[index]。
*
* @param: [arr, l, r]
* @return: int
* @auther: wjy
* @date: 2020/2/13 22:34
*/
public int partition(int[] arr, int l, int r) {
SortHelper.swap(arr, l, (int) (Math.random() * (r - l + 1) + l));
int value = arr[l];
// arr[l...i) <= v、arr[j...r] >= v
int i = l + 1, j = r;
while (true) {
while (i <= r && arr[i] < value) {
i++;
}
while (j > l && arr[j] > value) {
j--;
}
if (i > j) {
break;
}
else {
// 此时arr[i] > value && arr[j] < value,所以直接交换它们的位置。
SortHelper.swap(arr, i++, j--);
}
}
// 将value移到分界处
SortHelper.swap(arr, l, j);
return j;
}

/**
* 功能描述: 对arr[l...r]部分进行双路快速排序
*
* @param: [arr, l, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 11:08
*/
public void recursion(int[] arr, int l, int r) {
if (r - l <= 15) {
sort(arr, l, r);
return;
}
int index = partition(arr, l, r);
recursion(arr, l, index - 1);
recursion(arr, index + 1, r);
}

@Override
public void ascendSort(int[] arr, int n) {
recursion(arr, 0, n - 1);
}
}
  • 三路快速排序
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package sort.swapsort;

import sort.Sort;
import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/13
* @description: 交换排序类-三路快速排序
*/
public class QuickSort3Ways implements Sort {

/**
* 功能描述: 对arr[l...r]部分进行插入排序
*
* @param: [arr, l, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 0:10
*/
public static void sort(int[] arr, int l, int r) {
// 第1个元素(索引为l)默认有序
for (int i = l + 1; i <= r; i++) {
// 寻找元素e合适的插入位置
int e = arr[i], j = i;
for (; j > l && arr[j - 1] > e; j--) {
// 向后移出空位
arr[j] = arr[j - 1];
}
// 找到了合适的插入位置
arr[j] = e;
}
}

/**
* 功能描述: 对arr[l...r]部分进行三路快速排序
* 将arr[l...r]分为 < value、== value、> value 三部分。
* @param: [arr, l, r]
* @return: void
* @auther: wjy
* @date: 2020/2/13 11:09
*/
public void recursion(int[] arr, int l, int r) {
if (r - l <= 15) {
sort(arr, l, r);
return;
}
// partition
SortHelper.swap(arr, l, (int) (Math.random() * (r - l + 1) + l));
// arr[l+1...lt] < v、arr[lt+1...gt-1] == v、arr[gt...r] > v。
int value = arr[l], lt = l, gt = r + 1, i = l + 1;
while (i < gt) {
if (arr[i] < value) {
// 交换过来的arr[++lt]已经处理过,需要i++。
SortHelper.swap(arr, i++, ++lt);
}
else if (arr[i] > value) {
// 交换过来的arr[--gt]没有处理过,不需要i++。
SortHelper.swap(arr, i, --gt);
}
else {
i++;
}
}
// 将value移到分界处
SortHelper.swap(arr, l, lt);
recursion(arr, l, lt - 1);
recursion(arr, gt, r);
}

@Override
public void ascendSort(int[] arr, int n) {
recursion(arr, 0, n - 1);
}
}

③性能分析

  • 稳定性:不稳定
  • 是否是原地排序:否
  • 平均时间复杂度:O(n*logn)
  • 最好情况:O(n*logn)(顺序)
  • 最坏情况:O(n^2)(逆序)
  • 空间复杂度:O(logn)(递归)

④衍生问题 — 取数组中第 N 小的元素

方法一(O(n^2)):排序后求解
方法二(O(n*logn)):快速排序的思路求解数组中第 N 小的元素

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
62
63
64
65
package sort.derivedquestion;

import sort.util.RandomArray;
import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/13
* @description: 求解数组中第N小的元素
*/
public class TopNByQuickSort {

/**
* 功能描述: 对arr[l...r]部分进行partition操作
*
* @param: [arr, l, r]
* @return: int
* @auther: wjy
* @date: 2020/2/13 23:30
*/
public static int partition(int[] arr, int l, int r) {
SortHelper.swap(arr, l, (int) (Math.random() * (r - l + 1) + l));
int value = arr[l], j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i] < value) {
SortHelper.swap(arr, i, ++j);
}
}
// 将value移到分界处
SortHelper.swap(arr, l, j);
return j;
}

/**
* 功能描述: 对arr[l...r]部分进行快速排序,并寻找数组中第N小的元素。
*
* @param: [arr, l, r, N]
* @return: int
* @auther: wjy
* @date: 2020/2/13 23:31
*/
public static int recursion(int[] arr, int l, int r, int N) {
if (l >= r) {
return 0;
}
int index = partition(arr, l, r), number = 0;
if (index == N) {
number = arr[index];
}
else if (index > N) {
number = recursion(arr, l, index - 1, N);
}
else {
number = recursion(arr, index + 1, r, N);
}
return number;
}

public static void main(String[] args) {
int n = 5, N = (int) (Math.random() * n) + 1;
int[] arr = RandomArray.generateRandomArray(n, 0, n);
SortHelper.printArray(arr, n);
System.out.println("数组中第" + N + "小的元素是: " + recursion(arr, 0, n - 1, N - 1));
}
}

Alt text
Alt text
Alt text


9.选择排序类 — 堆排序

  • 基础的最大堆的构建和使用
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package heap;

import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/14
* @description: 最大堆(arr[1]处存储最大堆的第一个元素)
*/
public class MaxHeap {

private int[] arr;
private int count;
private int capacity;

public MaxHeap(int n) {
arr = new int[n + 1];
count = 0;
this.capacity = n;
}

/**
* 功能描述: 向上调整最大堆(入队时调用)
*
* @param: [index]
* @return: void
* @auther: wjy
* @date: 2020/2/14 7:44
*/
public void shiftUp(int index) {
// 防止越界
while (index > 1 && arr[index / 2] < arr[index]) {
SortHelper.swap(arr, index / 2, index);
index /= 2;
}
}

/**
* 功能描述: 向下调整最大堆(出队时调用)
*
* @param: [index]
* @return: void
* @auther: wjy
* @date: 2020/2/14 7:44
*/
public void shiftDown(int index) {
// 判断是否有左孩子
while (index * 2 <= count) {
// 哪个孩子大,就和哪个孩子交换。
int lc = index * 2, rc = lc + 1, res = lc;
if (rc <= count && arr[rc] > arr[lc]) {
res = rc;
}
if (arr[index] >= arr[res]) {
break;
}
SortHelper.swap(arr, index, res);
index = res;
}
}

/**
* 功能描述: 判断最大堆是否为空
*
* @param: []
* @return: boolean
* @auther: wjy
* @date: 2020/2/14 7:49
*/
public boolean isEmpty() {
return count == 0;
}

/**
* 功能描述: 打印最大堆
*
* @param: []
* @return: void
* @auther: wjy
* @date: 2020/2/14 7:50
*/
public void printArr() {
for (int i = 1; i <= count; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

/**
* 功能描述: 入队
*
* @param: [e]
* @return: void
* @auther: wjy
* @date: 2020/2/14 10:14
*/
public void insert(int e) {
if (count + 1 > capacity) {
return;
}
arr[++count] = e;
shiftUp(count);
}

/**
* 功能描述: 出队
* 最大堆中只能取出根节点
* 为了维持完全二叉树的性质,将堆中最后一个元素移到根节点的位置,然后向下调整最大堆。
*
* @param: []
* @return: int
* @auther: wjy
* @date: 2020/2/14 7:44
*/
public int removeMax() {
if (count < 1 ) {
return 0;
}
// 取出根节点
int e = arr[1];
// 将堆中最后一个元素移到根节点的位置
SortHelper.swap(arr, 1, count--);
shiftDown(1);
return e;
}
}
  • 改进的最大堆的构建和使用 1
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
package heap;

import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/14
* @description: 改进的最大堆1(arr[1]处存储最大堆的第一个元素)
*/
public class AdvancedMaxHeap1 {

private int[] arr;
private int count;
private int capacity;

public AdvancedMaxHeap1(int n) {
arr = new int[n + 1];
count = 0;
this.capacity = n;
}

/**
* 功能描述: 向上调整最大堆(入队时调用)
*
* @param: [index]
* @return: void
* @auther: wjy
* @date: 2020/2/14 7:44
*/
public void shiftUp(int index) {
int e = arr[index];
// 防止越界
while (index > 1 && arr[index / 2] < e) {
// 优化1: 使用赋值操作代替交换操作
arr[index] = arr[index / 2];
index /= 2;
}
arr[index] = e;
}

/**
* 功能描述: 向下调整最大堆(出队时调用)
*
* @param: [index]
* @return: void
* @auther: wjy
* @date: 2020/2/14 7:44
*/
public void shiftDown(int index) {
int e = arr[index];
// 判断是否有左孩子
while (index * 2 <= count) {
// 哪个孩子大,就和哪个孩子交换。
int lc = index * 2, rc = lc + 1, res = lc;
if (rc <= count && arr[rc] > arr[lc]) {
res = rc;
}
if (e >= arr[res]) {
break;
}
// 优化1: 使用赋值操作代替交换操作
arr[index] = arr[res];
index = res;
}
arr[index] = e;
}

/**
* 功能描述: 判断最大堆是否为空
*
* @param: []
* @return: boolean
* @auther: wjy
* @date: 2020/2/14 7:49
*/
public boolean isEmpty() {
return count == 0;
}

/**
* 功能描述: 打印最大堆
*
* @param: []
* @return: void
* @auther: wjy
* @date: 2020/2/14 7:50
*/
public void printArr() {
for (int i = 1; i <= count; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

/**
* 功能描述: 入队
*
* @param: [e]
* @return: void
* @auther: wjy
* @date: 2020/2/14 10:14
*/
public void insert(int e) {
if (count + 1 > capacity) {
return;
}
arr[++count] = e;
shiftUp(count);
}

/**
* 功能描述: 出队
* 最大堆中只能取出根节点
* 为了维持完全二叉树的性质,将堆中最后一个元素移到根节点的位置,然后向下调整最大堆。
*
* @param: []
* @return: int
* @auther: wjy
* @date: 2020/2/14 7:44
*/
public int removeMax() {
if (count < 1 ) {
return 0;
}
// 取出根节点
int e = arr[1];
// 将堆中最后一个元素移到根节点的位置
SortHelper.swap(arr, 1, count--);
shiftDown(1);
return e;
}
}
  • 改进的最大堆的构建和使用 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
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package heap;

import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/14
* @description: 改进的最大堆2(arr[1]处存储最大堆的第一个元素)
*/
public class AdvancedMaxHeap2 {

private int[] arr;
private int count;

// 优化2: 修改构造函数,直接向下调整最大堆。
public AdvancedMaxHeap2(int[] data, int n) {
arr = new int[n + 1];
for (int i = 0; i < n; i++) {
arr[i + 1] = data[i];
}
count = n;
// heapify: 将数组原地构建成最大堆
// 所有的叶子节点本身就是一个最大堆,所以我们从第一个不是叶子节点的节点开始调整堆。
// 对于一颗完全二叉树来说,第一个非叶子节点的索引: count/2。
for (int i = count / 2; i > 0; i--) {
shiftDown(i);
}
}

/**
* 功能描述: 向下调整最大堆(出队时调用)
*
* @param: [index]
* @return: void
* @auther: wjy
* @date: 2020/2/14 7:44
*/
public void shiftDown(int index) {
int e = arr[index];
// 判断是否有左孩子
while (index * 2 <= count) {
// 哪个孩子大,就和哪个孩子交换。
int lc = index * 2, rc = lc + 1, res = lc;
if (rc <= count && arr[rc] > arr[lc]) {
res = rc;
}
if (e >= arr[res]) {
break;
}
// 优化1: 使用赋值操作代替交换操作
arr[index] = arr[res];
index = res;
}
arr[index] = e;
}

/**
* 功能描述: 判断最大堆是否为空
*
* @param: []
* @return: boolean
* @auther: wjy
* @date: 2020/2/14 7:49
*/
public boolean isEmpty() {
return count == 0;
}

/**
* 功能描述: 打印最大堆
*
* @param: []
* @return: void
* @auther: wjy
* @date: 2020/2/14 7:50
*/
public void printArr() {
for (int i = 1; i <= count; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

/**
* 功能描述: 出队
* 最大堆中只能取出根节点
* 为了维持完全二叉树的性质,将堆中最后一个元素移到根节点的位置,然后向下调整最大堆。
*
* @param: []
* @return: int
* @auther: wjy
* @date: 2020/2/14 7:44
*/
public int removeMax() {
if (count < 1 ) {
return 0;
}
// 取出根节点
int e = arr[1];
// 将堆中最后一个元素移到根节点的位置
SortHelper.swap(arr, 1, count--);
shiftDown(1);
return e;
}
}
  • 测试最大堆的构建和使用
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
package heap;

/**
* @author: wjy
* @date: 2020/2/14
* @description: 测试最大堆的构建和使用
*/
public class TestMaxHeap {

public static void main(String[] args) {
int n = 10;
System.out.println("----------测试MaxHeap类----------");
MaxHeap maxHeap = new MaxHeap(n);
for (int i = 0; i < n; i++) {
maxHeap.insert((int) (Math.random() * 20));
}
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.removeMax() + " ");
}
System.out.println();

System.out.println("----------测试AdvancedMaxHeap1类----------");
AdvancedMaxHeap1 advancedMaxHeap1 = new AdvancedMaxHeap1(n);
for (int i = 0; i < n; i++) {
advancedMaxHeap1.insert((int) (Math.random() * 20));
}
while (!advancedMaxHeap1.isEmpty()) {
System.out.print(advancedMaxHeap1.removeMax() + " ");
}
System.out.println();

System.out.println("----------测试AdvancedMaxHeap2类----------");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = ((int) (Math.random() * 20));
}
AdvancedMaxHeap2 advancedMaxHeap2 = new AdvancedMaxHeap2(arr, n);
while (!advancedMaxHeap2.isEmpty()) {
System.out.print(advancedMaxHeap2.removeMax() + " ");
}
System.out.println();
}
}

Alt text

①排序思路

  • 堆最重要的应用是对动态数据的维护
  • 方法:

Alt text
Alt text

  • 堆排序:
    • 方法:将 n 个元素逐个插入到一个空堆(最大堆,arr[1] 处存储最大堆的第一个元素)中,算法的时间复杂度是 O(n*logn),然后将堆中的元素逐个移出,使用额外的空间从后向前存放取出的元素。
    • 未优化的堆排序慢于快速排序和归并排序
    • 缺点:空间复杂度为 O(n)

Alt text

  • 改进的堆排序 1:
    • 优化 1:使用赋值操作代替交换操作
    • 优化 2:将数组原地构建成最大堆(只需要处理 n / 2 个元素)
    • 优化建堆的堆排序整体速度慢于快速排序和归并排序。
  • 改进的堆排序 2:
    • 原地堆排序,arr[0] 处存储最大堆的第一个元素。
    • 不占用额外空间的堆排序比占用额外空间的堆排序快一点

Alt text

②代码演示

  • 堆排序
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
package sort.selectsort;

import heap.AdvancedMaxHeap1;
import sort.Sort;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 选择排序类-堆排序
*/
public class HeapSort implements Sort {

@Override
public void ascendSort(int[] arr, int n) {
AdvancedMaxHeap1 advancedMaxHeap1 = new AdvancedMaxHeap1(n);
// 构建最大堆
for (int i = 0; i < n; i++) {
advancedMaxHeap1.insert(arr[i]);
}
// 堆排序
for (int i = n - 1; i >= 0; i--) {
arr[i] = advancedMaxHeap1.removeMax();
}
}
}
  • 改进的堆排序 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package sort.selectsort;

import heap.AdvancedMaxHeap2;
import sort.Sort;

/**
* @author: wjy
* @date: 2020/2/14
* @description: 选择排序类-改进的堆排序1
*/
public class AdvancedHeapSort1 implements Sort {

@Override
public void ascendSort(int[] arr, int n) {
AdvancedMaxHeap2 advancedMaxHeap2 = new AdvancedMaxHeap2(arr, n);
for (int i = n - 1; i >= 0; i--) {
arr[i] = advancedMaxHeap2.removeMax();
}
}
}
  • 改进的堆排序 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
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
package sort.selectsort;

import sort.Sort;
import sort.util.SortHelper;

/**
* @author: wjy
* @date: 2020/2/14
* @description: 选择排序类-改进的堆排序2(原地堆排序、arr[0]处存储最大堆的第一个元素)
*/
public class AdvancedHeapSort2 implements Sort {

/**
* 功能描述: 向下调整最大堆(出队时调用)
*
* @param: [arr, n, index]
* @return: void
* @auther: wjy
* @date: 2020/2/14 11:17
*/
public void shiftDown(int[] arr, int n, int index) {
int e = arr[index];
// 判断是否有左孩子
while (index * 2 + 1 < n) {
// 哪个孩子大,就和哪个孩子交换。
int lc = index * 2 + 1, rc = lc + 1, res = lc;
if (rc < n && arr[rc] > arr[lc]) {
res = rc;
}
if (e >= arr[res]) {
break;
}
arr[index] = arr[res];
index = res;
}
arr[index] = e;
}

@Override
public void ascendSort(int[] arr, int n) {
// heapify: 将数组原地构建成最大堆
// 最后一个非叶子节点的索引计算: (最后一个元素索引值-1)/2
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
shiftDown(arr, n, i);
}
// 最大堆中第一个元素即是数组中的最大值,每次将堆中第一个元素与数组末尾的元素交换,再动态维护堆(数组长度-1)。
for (int i = n - 1; i > 0; i--) {
// 将当前最大堆中的最大值移到数组末尾
SortHelper.swap(arr, 0, i);
// 重新构建最大堆
shiftDown(arr, i, 0);
}
}
}

③性能分析

  • 稳定性:不稳定
  • 是否是原地排序:是
  • 平均时间复杂度:O(n*logn)
  • 最好的情况:O(n*logn)(顺序)
  • 最坏的情况:O(n*logn)(逆序)
  • 空间复杂度:O(1)

10.性能比较

①排序随机数组

  • 测试各个排序算法针对随机数组的排序性能
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
62
63
64
65
66
67
68
69
70
package sort;

import sort.insertsort.DirectInsertSort;
import sort.insertsort.ShellSort;
import sort.mergesort.AdvancedIterationMergeSort;
import sort.mergesort.AdvancedMergeSort;
import sort.mergesort.IterationMergeSort;
import sort.mergesort.MergeSort;
import sort.selectsort.AdvancedHeapSort1;
import sort.selectsort.AdvancedHeapSort2;
import sort.selectsort.HeapSort;
import sort.selectsort.SimpleSelectSort;
import sort.swapsort.*;
import sort.util.RandomArray;

import java.util.Arrays;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 测试各个排序算法针对随机数组的排序性能
*/
public class TestRandomArray {

public static void main(String[] args) {
System.out.println("----------随机数组的长度是1000,范围是0~1000。----------");
int n = 1000;
// 随机数组的长度是1000,范围是0~1000。
int[] arr = RandomArray.generateRandomArray(n, 0, 1000);
TestSort.testSort("简单交换排序", new SimpleSwapSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("传统的冒泡排序", new BubbleSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的冒泡排序", new AdvancedBubbleSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("简单选择排序", new SimpleSelectSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("直接插入排序", new DirectInsertSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("希尔排序", new ShellSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("归并排序", new MergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的归并排序", new AdvancedMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("自底向上的归并排序", new IterationMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的自底向上的归并排序", new AdvancedIterationMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("快速排序", new QuickSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的快速排序", new AdvancedQuickSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("双路快速排序", new QuickSort2Ways(), Arrays.copyOf(arr, n), n);
TestSort.testSort("三路快速排序", new QuickSort3Ways(), Arrays.copyOf(arr, n), n);
TestSort.testSort("堆排序", new HeapSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的堆排序1", new AdvancedHeapSort1(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的堆排序2", new AdvancedHeapSort2(), Arrays.copyOf(arr, n), n);

System.out.println("----------随机数组的长度是100000,范围是0~100000。----------");
n = 100000;
// 随机数组的长度是100000,范围是0~100000。
arr = RandomArray.generateRandomArray(n, 0, 100000);
TestSort.testSort("简单交换排序", new SimpleSwapSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("传统的冒泡排序", new BubbleSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的冒泡排序", new AdvancedBubbleSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("简单选择排序", new SimpleSelectSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("直接插入排序", new DirectInsertSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("希尔排序", new ShellSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("归并排序", new MergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的归并排序", new AdvancedMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("自底向上的归并排序", new IterationMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的自底向上的归并排序", new AdvancedIterationMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("快速排序", new QuickSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的快速排序", new AdvancedQuickSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("双路快速排序", new QuickSort2Ways(), Arrays.copyOf(arr, n), n);
TestSort.testSort("三路快速排序", new QuickSort3Ways(), Arrays.copyOf(arr, n), n);
TestSort.testSort("堆排序", new HeapSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的堆排序1", new AdvancedHeapSort1(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的堆排序2", new AdvancedHeapSort2(), Arrays.copyOf(arr, n), n);
}
}

Alt text
Alt text
Alt text

②排序近乎有序的数组

  • 测试各个排序算法针对近乎有序的数组的排序性能
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
62
63
64
65
66
67
68
69
70
package sort;

import sort.insertsort.DirectInsertSort;
import sort.insertsort.ShellSort;
import sort.mergesort.AdvancedIterationMergeSort;
import sort.mergesort.AdvancedMergeSort;
import sort.mergesort.IterationMergeSort;
import sort.mergesort.MergeSort;
import sort.selectsort.AdvancedHeapSort1;
import sort.selectsort.AdvancedHeapSort2;
import sort.selectsort.HeapSort;
import sort.selectsort.SimpleSelectSort;
import sort.swapsort.*;
import sort.util.RandomArray;

import java.util.Arrays;

/**
* @author: wjy
* @date: 2020/2/11
* @description: 测试各个排序算法针对近乎有序的数组的排序性能
*/
public class TestNearlyRandomArray {

public static void main(String[] args) {
System.out.println("----------随机数组的长度是1000,并且定义逆序对个数为10。----------");
int n = 1000;
// 随机数组的长度是1000,并且定义逆序对个数为10。
int[] arr = RandomArray.generateNearlyRandomArray(n, 10);
TestSort.testSort("简单交换排序", new SimpleSwapSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("传统的冒泡排序", new BubbleSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的冒泡排序", new AdvancedBubbleSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("简单选择排序", new SimpleSelectSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("直接插入排序", new DirectInsertSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("希尔排序", new ShellSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("归并排序", new MergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的归并排序", new AdvancedMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("自底向上的归并排序", new IterationMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的自底向上的归并排序", new AdvancedIterationMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("快速排序", new QuickSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的快速排序", new AdvancedQuickSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("双路快速排序", new QuickSort2Ways(), Arrays.copyOf(arr, n), n);
TestSort.testSort("三路快速排序", new QuickSort3Ways(), Arrays.copyOf(arr, n), n);
TestSort.testSort("堆排序", new HeapSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的堆排序1", new AdvancedHeapSort1(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的堆排序2", new AdvancedHeapSort2(), Arrays.copyOf(arr, n), n);

System.out.println("----------随机数组的长度是100000,并且定义逆序对个数为1000。----------");
n = 100000;
// 随机数组的长度是100000,并且定义逆序对个数为1000。
arr = RandomArray.generateNearlyRandomArray(n, 1000);
TestSort.testSort("简单交换排序", new SimpleSwapSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("传统的冒泡排序", new BubbleSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的冒泡排序", new AdvancedBubbleSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("简单选择排序", new SimpleSelectSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("直接插入排序", new DirectInsertSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("希尔排序", new ShellSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("归并排序", new MergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的归并排序", new AdvancedMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("自底向上的归并排序", new IterationMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的自底向上的归并排序", new AdvancedIterationMergeSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("快速排序", new QuickSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的快速排序", new AdvancedQuickSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("双路快速排序", new QuickSort2Ways(), Arrays.copyOf(arr, n), n);
TestSort.testSort("三路快速排序", new QuickSort3Ways(), Arrays.copyOf(arr, n), n);
TestSort.testSort("堆排序", new HeapSort(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的堆排序1", new AdvancedHeapSort1(), Arrays.copyOf(arr, n), n);
TestSort.testSort("改进的堆排序2", new AdvancedHeapSort2(), Arrays.copyOf(arr, n), n);
}
}

Alt text
Alt text
Alt text

③总结

  • 每一种排序算法都有它存在的理由,没有一种排序算法在任何情况下的表现都是最好的,排序算法的具体性能依赖于待排数据的特点。
  • 排序算法对比(图片来源于网络):

Alt text
Alt text

  • 排序算法的应用场景(图片来源于网络):

Alt text


附录

0%