排序算法 | Java 知识体系

# 排序算法

“快选希堆”是不稳定的，其他稳定

数据结构可视化：链接 (opens new window)
*八大排序：链接 (opens new window)
*leetcode排序解析：链接 (opens new window)

# JDK排序算法

JDK排序 (opens new window)

这里写图片描述

# 冒泡排序

# 算法效率

稳定算法

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n2)	O(n)	O(n2)	O(1)

# 快排(重点)

# 基本思想

快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，基本思路是：

每次选择一个数，将所有小于该数的元素放到该数的前面，大于的放到其后面。（每次都确定一个元素的位置）
递归实现

JDK的Arrays.sort采用了双轴快速排序

快排的实现方式：

基本快排
双指针快排
三指针快排

基本快排和双指针快排的区别：[2, 1, 3, 1, 3, 1]，对于普通快排，需要swap三次，对于双指针快排，需要swap一次

# 代码实现

只记住第一种和第二种写法就行，不要记零的写法，所以整个过程中涉及到的对象间的调整都是swap，记住！

写法零：填坑法(双指针)

public static void sort(int arr[], int low, int high) {
    if (arr == null || arr.length <= 0) {
      return;
    }
    if (low >= high) {
      return;
    }

    int left = low;
    int right = high;
    int temp = arr[left]; //挖坑1：保存基准的值

    while (left < right) {
      while (left < right && arr[right] >= temp) {
        right--;
      }
      arr[left] = arr[right]; //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
      while (left < right && arr[left] <= temp) {
        left ++;
      }
      arr[right] = arr[left]; //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
    }
    arr[left] = temp; //基准值填补到坑3中，准备分治递归快排
    sort(arr, low, left-1);
    sort(arr, left + 1, high);
}

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

写法一：基本快速排序
- partition方法：找到基准下标，该基准左边都是小于基准的值，右边都是大于基准的值

public int[] sortArray(int[] nums) {

    quickSort(nums, 0, nums.length - 1);
    return nums;
}

private void quickSort(int[] nums, int left, int right){
    if(left >= right){
        return;
    }

    int pIndex = partition(nums, left, right);
    quickSort(nums, left, pIndex - 1);
    quickSort(nums, pIndex + 1, right);
}

private int partition(int[] nums, int left, int right){

    int pivot = nums[left];
  	int lt = left;

    for(int i = left + 1;i <= right;i ++){
      if(nums[i] <= pivot){
        lt ++;
        swap(nums, i, lt);
      }
    }
    swap(nums, lt, left);

    return lt;
}

private void swap(int[] nums, int left, int right){
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
}

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

写法二：双指针（指针对撞）快速排序

public int[] sortArray(int[] nums) {

    quickSort(nums, 0, nums.length - 1);
    return nums;
}

private void quickSort(int[] nums, int left, int right){
    if(left >= right){
        return;
    }

    int pIndex = partition(nums, left, right);
    quickSort(nums, left, pIndex - 1);
    quickSort(nums, pIndex + 1, right);
}

private int partition(int[] nums, int left, int right){

    int pivot = nums[left];
  
  	// lt从left开始，lt在开始移动后代表第一个从左往右 > povit的元素，没有移动时停留在 <= pivot的元素上（swap需要），如果从left + 1开始，没有 <= pivot的数时会被强制swap，导致出错
    int lt = left;
    // gt移动后表示第一个 < povit的元素，不care不移动时候的指向元素
    int gt = right;

    while(lt < gt){
        // lt从left开始，得先遍历gt的，这样即使遇到1，2，3，4这种已经有序的，也可以保证lt没有移动，因为如果是lt先遍历，无论如何都会往下走一位，这样left和lt会被强制替换导致出问题
        while(lt < gt && nums[gt] >= pivot){
            gt --;
        }

        while(lt < gt && nums[lt] <= pivot){
            lt ++;
        }

        swap(nums, lt, gt);
    }

    swap(nums, left, lt);
    
    return lt;
}

private void swap(int[] nums, int left, int right){
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
}

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

# 算法效率

不稳定
最坏情况：数组有序（正序或倒序），这样每次partition后都分为一个为空、一个为（n-1）个数的数组，最终O(n^2)
最好情况：每次都能平均分割，O(nlogn)
平均情况：O(n*logn)
空间复杂度：主要由递归而产生的对栈空间的影响
- 最好：O(logn)：pivot为中间值，树平衡
- 最坏:O(n)：数组基本有序，取第一个数作为pivot会导致生成树不平衡，数高度=数组长度
- 平均：O(logn)

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(nlogn)	O(nlogn)	O(n2)	O(logn)

# 插入排序

# 算法思路

# 算法实现

if (a == null || a.length == 0) {
    return;
}

for (int i = 1; i < a.length; i++) {
    int j = i - 1;
    int temp = a[i]; // 先取出待插入数据保存，因为向后移位过程中会把覆盖掉待插入数
    while (j >= 0 && a[j] > temp) { // 如果待是比待插入数据大，就后移
        a[j+1] = a[j];
        j--;
    }
    a[j+1] = temp; // 找到比待插入数据小的位置，将待插入数据插入
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 算法效率

稳定

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n2)	O(n)	O(n2)	O(1)

# 希尔排序

# 算法效率

不稳定

# 选择排序

# 算法思路

两层循环

第一层左边代表已经排好序的，右边还未排序

第二层找出第一层未排序的元素中最小元素的下标，并与当前元素交换

# 算法实现

public int[] sortArray(int[] nums) {
    
    for(int i = 0;i < nums.length;i ++){
        int min = i;
        for(int j = i + 1;j < nums.length;j ++){
            if(nums[min] > nums[j]){
                min = j;
            }
        }

        swap(nums, min, i);
    }

    return nums;
}

private void swap(int[] nums, int left ,int right){
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 算法效率

不稳定（涉及到swap，例如{5,5,2}）

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n2)	O(n2)	O(n2)	O(1)

# 归并排序（重点）

# 代码实现

private int[] partition(int[] nums){
    if(nums.length <= 1){
        return nums;
    }
    int len = nums.length;
    int[] left = Arrays.copyOfRange(nums, 0, len / 2);
    int[] right = Arrays.copyOfRange(nums, len / 2, len);

    return merge(partition(left), partition(right));
}

private int[] merge(int[] left, int[] right){

    int l = 0;
    int r = 0;
    int len1 = left.length;
    int len2 = right.length;
    int[] res = new int[len1 + len2];
    int i = 0;

    while(l < len1 && r < len2){
        if(left[l] < right[r]){
            res[i ++] = left[l ++];
        }else {
            res[i ++] = right[r ++];
        }    
    }

    while(l < len1){
        res[i ++] = left[l ++];
    }

    while(r < len2){
        res[i ++] = right[r ++];
    }

    return res;
}

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

# 算法效率

稳定

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(nlogn)	O(nlogn)	O(nlogn)	O(n)

# 基数排序

# 算法思路

如下图所示，依次对从高位到低位上的元素进行排序（桶思想）。

适用场景：

数据范围较小，建议在小于1000

每个数值都要大于等于0

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶

计数排序：每个桶只存储单一键值

桶排序：每个桶存储一定范围的数值

# 算法效率

稳定

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(d*(n+r))	O(d*(n+r))	O(d*(n+r))	O(n+r)

# 堆排序（重点）

堆排序动画 (opens new window)

# 基本思想

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
将堆顶节点与最后一个节点进行swap，并剔除出堆
调整替换后的堆，让堆顶重回最大元素

# 代码实现

public int[] sortArray(int[] nums) {

    int len = nums.length;

    // 构建大根堆，从最后一个非叶子结点开始
    for(int i = (len - 1) / 2;i >= 0;i --){
        adjustHeap(nums, i, len - 1);
    }

    // 替换根顶和末尾的元素，并重新调整，大根堆保证每个节点都大于其左右节点（即子树的根节点是最大的值）
    for(int i = len - 1;i >= 0;i --){
        swap(nums, i, 0);
        adjustHeap(nums,0, i - 1);
    }

    return nums;
}


public void adjustHeap(int[] nums, int k,int end){
    // 左叶子结点
    while(2 * k + 1 <= end){
        // 比较左右叶子节点大小，选取最大的那个叶子
        int j = 2 * k + 1;
        if(j + 1 <= end && nums[j + 1] > nums[j]){
            j ++;
        }
        if(nums[j] > nums[k]){
          swap(nums, j, k);
          // 该子树被调整了，需要重新构建
          k = j;
        }else {
          // 已经为最大值
          break;
        }
    }
}


private void swap(int[] nums, int left, int right){
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
}

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

# 算法效率

不稳定

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(nlogn)	O(nlogn)	O(nlogn)	O(1)

← leetcode100 算法框架学习 →