常见的排序算法

一、冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

image-20230211215024466

优化：当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

空间复杂度：O(1)

时间复杂度：最好：O(n)，最坏：O(n^2^)，平均：O(n^2^)

稳定的排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void bubbleSort(int[] arr, int n) {
    if (n <= 1) {
        return;
    }
    // 循环 n-1 次
    for (int i = 0; i < n - 1; i++) {
        boolean flag = true;
        // 终点为 n-i-1
        for (int j = 0; j < n - i - 1; j++) {
            // 比较相邻的数大小，将大的数往后移
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = false;
            }
        }
        // 本次循环未交换元素则退出
        if (flag) {
            break;
        }
    }
}

二、插入排序

将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，排序结束。

image-20230211215645215

空间复杂度：O(1)

时间复杂度：最好：O(n)，最坏：O(n^2^)，平均：O(n^2^)

稳定的排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void insertionSort(int[] arr, int n) {
    if (n <= 1) {
        return;
    }
    for (int i = 1; i < n; i++) {
        // 未排序数组中第一个值
        int value = arr[i];
        int j = i - 1;
        for (; j >= 0; j--) {
            // 比较值的大小
            if (value < arr[j]) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        arr[j + 1] = value;
    }
}

三、选择排序

选择排序也分为已排序区间和未排序区间，每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

image-20230211221127129

空间复杂度：O(1)

时间复杂度：最好：O(n^2^)，最坏：O(n^2^)，平均：O(n^2^)

不稳定的排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void selectSort(int[] arr, int n) {
    if (n <= 1) {
        return;
    }
    for (int i = 0; i < n; i++) {
        int index = i;
        for (int j = i + 1; j < n; j++) {
            //寻找最小元素的下标
            if (arr[index] > arr[j]) {
                index = j;
            }
        }
        //进行交换
        int temp = arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
    }
}

小总结

以上这三种排序算法（时间复杂度都为 O(n^2^) ），实现代码都非常简单，对于小规模数据的排序，用起来非常高效。但是在大规模数据排序的时候，这个时间复杂度还是稍微有点高。

四、归并排序

归并排序的核心思想：如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序使用的就是分治思想（分治是一种解决问题的处理思想，递归是一种编程技巧）。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

image-20230211222528403

空间复杂度：O(n)

时间复杂度：最好：O(nlogn)，最坏：O(nlogn)，平均：O(nlogn)

稳定的排序算法

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
//归并排序
public void merge_sort(int[] arr, int n) {
    merge_sort_c(arr, 0, n - 1);
}

public void merge_sort_c(int[] arr, int l, int r) {
    //判断左右边界
    if (l >= r) {
        return;
    }
    //取中点
    int mid = l + ((r - l) >> 1);
    //分治
    merge_sort_c(arr, l, mid);
    merge_sort_c(arr, mid + 1, r);
    //当左右数组变为有序后再合并
    merge(arr, l, mid, r);
}

public void merge(int[] arr, int l, int mid, int r) {
    //定义一个数组
    int[] temp = new int[r - l + 1];
    int i = l;
    int j = mid + 1;
    int k = 0;
    //左右数组比较大小，将元素添加到temp数组中
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    //将剩余的元素添加到temp数组中
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= r) {
        temp[k++] = arr[j++];
    }
    //再将已排序的元素赋值给原数组
    for (k = 0; k < temp.length; k++) {
        arr[l + k] = temp[k];
    }
}

五、快速排序

快排的思想：

  1. 如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r之间的任意一个数据作为 pivot（分区点）。

  2. 我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。

  3. 根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

image-20230214202037253

空间复杂度：O(1)

时间复杂度：最好：O(nlogn)，最坏：O(n^2^)，平均：O(nlogn)

不稳定的排序算法

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
//快排
public static void quickSort(int[] arr, int n) {
    quickSortInternally(arr, 0, n - 1);
}


public static void quickSortInternally(int[] arr, int l, int r) {
    if (l >= r) {
        return;
    }
    int i = l;
    int j = r;
    //基准位
    int temp = arr[i];
    while (i < j) {
        //左边大于基准位
        while (j > i && arr[j] >= temp) {
            j--;
        }
        //右边小于等于基准位
        while (i < j && arr[i] <= temp) {
            i++;
        }
        if (i < j) {
            //将左右不符合条件的数交换
            swap(arr, i, j);
        }
    }
    //将基准数移到 i 和 j 相等的位置
    arr[l] = arr[i];
    arr[i] = temp;
    //排序右数组
    quickSortInternally(arr, l, i - 1);
    //排序左数组
    quickSortInternally(arr, i + 1, r);
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

六、堆排

堆排序是一种原地的、时间复杂度为O(nlogn)的排序算法。

堆的要求：

  • 堆必须是一个完全二叉树。（完全二叉树即除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列）

  • 堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。

大顶堆：每个节点的值都大于等于子树中每个节点值的堆

小顶堆：每个节点的值都小于等于子树中每个节点值的堆

堆中插入元素、删除元素的时间复杂度：O(logn)

堆排序的实现：

  1. 建堆（时间复杂度O(n)）
    • 添加元素，从下往上堆化
    • 用已有数组，从上往下建化
  2. 排序
    • 建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。
    • 数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。
    • 当堆顶元素移除之后，我们把原下标为 n 的元素放到堆顶，然后再通过堆化的方法，将剩下的 n-1 个元素重新构建成堆。
    • 堆化完成之后，我们再取堆顶的元素，放到下标是 n-1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了。（类似删除堆顶元素）

image-20230219100931963

使用数组存储表示完全二叉树时，从数组下标为 1 开始存储数据，数组下标为 i 的节点，左子节点为 2i , 右子节点为 2i + 1 。
从数组下标为 0 开始存储数据，如果节点的下标是 i，那左子节点的下标就是 2 ∗ i + 1，右子节点的下标就是 2 ∗ i + 2，父节点的下标就是 (i-1)/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
/**
 * 堆排
 */
public static void headSort(int[] arr, int n) {
    if (n < 1) {
        return;
    }
    //建堆
    builderHead(arr);
    //排序
    int length = arr.length - 1;
    while (length > 0) {
        // 将堆顶元素与最后一个元素交换位置
        swap(arr, 0, length);
        // 剩下元素重新堆化，将堆顶元素变成最大元素
        heapify(arr, --length, 0);
    }

}

/**
 * 建堆
 */
public static void builderHead(int[] arr) {
    // (arr.length - 1) / 2 为最后一个叶子节点的父节点
    // 也就是最后一个非叶子节点，依次堆化直到根节点
    for (int i = (arr.length - 1) / 2; i >= 0; i--) {
        heapify(arr, arr.length - 1, i);
    }
}


/**
 * 堆化
 */
public static void heapify(int[] arr, int n, int i) {
    while (true) {
        int maxPos = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        //与左子节点比较，获取最大值位置
        if (left <= n && arr[maxPos] < arr[left]) {
            maxPos = left;
        }
        //与右子节点比较，获取最大值位置
        if (right <= n && arr[maxPos] < arr[right]) {
            maxPos = right;
        }
        // 如果最大值为当前节点，则结束
        if (maxPos == i) {
            break;
        }
        swap(arr, maxPos, i);
        i = maxPos;
    }
}


public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

为什么快排比堆排序性能要好？

  1. 堆排序数据访问的方式没有快排友好：堆排序不是局部顺序访问，对CPU缓存不太友好
  2. 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序
    • 快排基于比较和交换，其交换次数不会多于逆序度
    • 堆排开始是建堆，其会打乱数据的原有顺序，导致数据的有序度降低

七、桶排序

桶排序的核心思想：将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的。

image-20230219145709309

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中

时间复杂度：O(n)

空间复杂度：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
/**
 * 桶排序
 */
public static void bucketSort(int[] arr, int bucketSize) {
    if (arr.length <= 1) {
        return;
    }
    //获取数组的最小值
    int max = arr[0];
    //获取数组的最大值
    int min = arr[0];
    for (int i : arr) {
        max = Math.max(max, i);
        min = Math.min(min, i);
    }
    //桶的个数
    int bucketCount = (max - min) / bucketSize + 1;
    //创建 bucketCount 个桶
    List<Integer>[] buckets = new List[bucketCount];
    // 将值分配到每个桶中
    for (int i = 0; i < arr.length; i++) {
        int bucketIndex = (arr[i] - min) / bucketSize;
        if (buckets[bucketIndex] == null) {
            buckets[bucketIndex] = new ArrayList<>();
        }
        buckets[bucketIndex].add(arr[i]);
    }
    // 对每个桶进行排序后再将值拷贝到原数组中
    int k = 0;
    for (int i = 0; i < bucketCount; i++) {
        if (buckets[i] == null) {
            continue;
        }
        Collections.sort(buckets[i]);
        for (int j = 0; j < buckets[i].size(); j++) {
            arr[k++] = buckets[i].get(j);
        }
    }
}

在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了

八、计数排序

计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

缺点：

  1. 只能用在数据范围不大的场景中，如果数据范围 k(最大值) 比要排序的数据 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
/**
 * 计数排序
 */
public static void countingSort(int[] arr, int n) {
    if (n <= 1) {
        return;
    }
    //获取数据的范围
    int max = arr[0];
    for (int i = 0; i < n; i++) {
        max = Math.max(arr[i], max);
    }
    //申请一个计数数组，下标范围 [0,max+1]
    int[] c = new int[max + 1];
    //计算每个元素的个数放入数组C中
    for (int i = 0; i < n; i++) {
        c[arr[i]]++;
    }
    //依次累加
    for (int i = 1; i < c.length; i++) {
        c[i] += c[i - 1];
    }
    //临时数组r，存储排序之后的结果
    int[] r = new int[n];
    //原数组中元素的在临时数组中的位置
    for (int i = n - 1; i >= 0; i--) {
        //找到该元素的下标
        int index = c[arr[i]] - 1;
        //赋值
        r[index] = arr[i];
        c[arr[i]]--;
    }
    //将排序后的结构拷贝给原数组
    for (int i = 0; i < n; i++) {
        arr[i] = r[i];
    }
}

为什么计数后还要开临时数组，为什么不直接通过计数直接赋值？

如果是单纯的数据排序可以，但是如果有对应的信息则不行，因为要清楚对应的分数所对应的信息。(如：成绩信息，小红 95，小李 95，那么第一个 95 对应的是那位同学需要通过后续的操作进行确定)

九、基数排序

基数排序对要排序的数据是有要求的，需要可以分割出独立的 “位” 来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

时间复杂度：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
/**
 * 基数排序
 */
public static void radixSort(int[] arr) {
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(arr[i], max);
    }
    for (int exp = 1; max / exp > 0; exp *= 10) {
        radixCountingSort(arr, exp);
    }
}

/**
 * 计数排序
 */
public static void radixCountingSort(int[] arr, int exp) {
    if (arr.length <= 1) {
        return;
    }
    // 计算每个元素的个数
    int[] c = new int[10];
    for (int i = 0; i < arr.length; i++) {
        c[(arr[i] / exp) % 10]++;
    }
    //累加元素
    for (int i = 1; i < arr.length; i++) {
        c[i] += c[i - 1];
    }
    //计算排序后的位置
    int[] r = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        int index = c[(arr[i] / exp) % 10] - 1;
        r[index] = arr[i];
        c[(arr[i] / exp) % 10]--;
    }
    // 拷贝数组
    for (int i = 0; i < arr.length; i++) {
        arr[i] = r[i];
    }
}
数据结构和算法
#排序算法 #算法
常见的排序算法
https://pursuemilk.github.io/2023/02/19/排序算法/
作者
PursueMilk
发布于
2023年2月19日
许可协议