​
​

活动地址：CSDN21天学习挑战赛

怕什么真理无穷，进一步有一份的欢喜。

【21天学习挑战赛】KMP模式匹配算法

✌我为什么参与挑战赛

1，机缘

读到研一了，暑假假期打开私信发现这个挑战赛就鼓起勇气参加了。

2，期待的收获

A, 本人在华南理工大学攻读专硕，目前研究方向是图像恢复，从事深度学习相关工作，目标是从事Java后端开发。
B, 期待您的反馈，如果有什么不对的地方，欢迎指正！
C, 期待认识志同道合的领域同行或技术交流。
如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

🍉交换排序是什么？

交换排序的核心思想是，每次将元素两两比较，如果不满足正确的相对序列（如：较小的应该在前）则进行交换。不断的根据某个规律进行比较和交换，直到全部满足为止，此时也就得到了一个有序的序列。

💬冒泡排序的定义

也称气泡排序，是经典的交换排序方法。整个过程就是在无序区中对相邻元素进行两两比较，将不满足相对顺序的一对儿元素进行交换，再进行下一对儿元素的比较。每一趟冒泡后，就会送一个最小的元素达到最上端。在无序区中重复这个过程，直到所有的元素有序。

✨冒泡排序的优劣

优势

算法在执行过程中只需要定义的几个临时变量，所以空间复杂度为常数级：O(1)。复现简单。

劣势

冒泡排序的时间复杂度为O(n^2)，效率不高

🍵冒泡排序的步骤

排序时会（在无序区中）的一端开始元素的扫描，先以最后一个元素为基准，与前一个元素进行比较，如果较小，则交换。如果遇到一个更小的，则不交换，继续向前进行两个相邻元素的比较。按照这样的过程执行后，无序区中最小的元素一定会被交换至最前，被划入有序区，也就排好了一个元素。
不断的在无序区中执行该步骤，如果在某一次比较的过程中没有发生元素的交换，则证明元素都已经有序，可以提前结束整个算法。或者直到无序区中的元素减少到一个时，整个算法结束，此时整个序列应有序。

✍️ 算法实现

public class BubbleSort {

    public static void main(String[] args) {
        // input data
        int[] a = {11,34,20,10,12,35,41,32,43,14};
        // 调用冒泡排序
        sort(a);
        // 查看排序结果
        for (int data : a){
            System.out.print(data + "\t");
        }
    }

    private static void sort(int[] a){
        // 外层循环：控制排序的总趟数
        for(int i = 0;i < a.length - 1;i++){
            // 定义变量记录是否发生交换
            int change = 0;
            // 内层循环用于元素的两两比较和交换
            for (int j = a.length - 1;j > i;j--){
                // 如果后面的元素较小，则交换
                if (a[j] < a[j-1]){
                    // 两个元素进行交换
                    int tmp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = tmp;
                    // 记录发生了交换
                    change = 1;
                }
            }
            // 如果一次比较中没有发生交换则提前结束
            if (change == 0){
                return;
            }
        }
    }

}

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

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
⭐️ 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！