前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >当初为什么不好好学习算法?

当初为什么不好好学习算法?

作者头像
行百里er
发布2020-12-02 14:55:46
3760
发布2020-12-02 14:55:46
举报
文章被收录于专栏:JavaJourneyJavaJourney

上学期间,最不用功的一门课就是数据结构与算法,现在后悔了! 数据结构和算法这个东西,如果你不去学,可能真的这辈子都用不到,也感受不到它的好。但是一旦掌握,你就会常常被它的强大威力所折服。之前你可能需要费很大劲儿来优化的代码,需要花很多心思来设计的架构,用了数据结构和算法之后,很容易就可以解决了。 我准备开一个“数据结构与算法”的话题,来补上学时的遗憾!先从排序算法开始!

排序是一个非常经典的问题,它以一定的顺序对一个数组(或一个列表)中的项进行重新排序(可以进行比较的,例如整数,浮点数,字符串等)。

有许多不同的排序算法,每个都有其自身的优点和局限性。

基于比较的排序算法:

它们比较数组的元素并决定是否交换它们

  • BUB - 冒泡排序,
  • SEL - 选择排序,
  • INS - 插入排序,
  • MER - 归并排序 (递归实现),
  • QUI - 快速排序 (递归实现),
  • R-Q - 随机快速排序 (递归实现).

不基于比较的排序算法:

  • COU - 计数排序,
  • RAD - 基数排序.

我们来逐一破解这些排序算法。

本文分析冒泡排序、选择排序和插入排序。

冒泡排序

假设数组arr长度为N,冒泡排序的过程为:

在arr[0~N-1]范围上:

  • arr[0]和arr[1],谁大谁来到1位置;
  • arr[1]和arr[2],谁大谁来到2位置
  • [N-2]和arr[N-1],谁大谁来到N-1位置

在arr[0~N-2]范围上,重复上面的过程,但最后一步是arr[N-3]和arr[N-2],谁大谁来到N-2位置

在arr[0~N-3]范围上,重复上面的过程,但最后一步是arr[N-4]和arr[N-3],谁大谁来到N-3位置

最后在arr[0~1]范围上,重复上面的过程,但最后一步是arr[0]和arr[1],谁大谁来到1位置

整个过程将最大的元素移动到最右侧,也就是最大的元素浮动到最右边,像冒泡一样。

如图所示:

冒泡排序

如图展示了第1趟排序的过程。

自己会动的才是好图:

冒泡排序动画演示

代码实现:

代码语言:javascript
复制
public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
        sort(arr);
    }

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //想要让0~i位置上有序,i一开始在数组的最大索引位置上,每比完1次,减1
        for (int i = arr.length - 1; i > 0; i--) {
            //0~i
            //0~(i-1)
            //0~(i-2)...
            //0~1
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("0~" + i + "位置比较结果:" + Arrays.toString(arr));
        }
    }
}

执行结果:

代码语言:javascript
复制
第0趟比较结果:[15, 13, 17, 6, 18, 15, 9, 20]
第1趟比较结果:[13, 15, 6, 17, 15, 9, 18, 20]
第2趟比较结果:[13, 6, 15, 15, 9, 17, 18, 20]
第3趟比较结果:[6, 13, 15, 9, 15, 17, 18, 20]
第4趟比较结果:[6, 13, 9, 15, 15, 17, 18, 20]
第5趟比较结果:[6, 9, 13, 15, 15, 17, 18, 20]
第6趟比较结果:[6, 9, 13, 15, 15, 17, 18, 20]
第7趟比较结果:[6, 9, 13, 15, 15, 17, 18, 20]

时间复杂度的计算:

比较和交换需要一个以常量为界的时间,我们称之为c。

Bubble Sort中有两个嵌套循环。

外循环正好运行N次迭代。但内部循环运行变得越来越短:

当 i = 0,(N-1)次迭代(比较和可能交换)时。

当 i = 1,(N-2)次迭代时,...

当 i =(N-2)时,1次迭代,

当 i=(N-1),0迭代.

因此,总迭代次数=(N-1)+(N-2)+ ... + 1 + 0 = N ×(N-1)/ 2

总时间= c × N ×(N-1)/ 2 = O(N²)。

选择排序

给定 N 个元素和 L = 0 的数组,选择排序过程为:

  1. 在 [L ... N-1] 范围内找出最小项目 X 的位置,
  2. 用第 L 项交换X,
  3. 将下限 L 增加1并重复步骤1直到 L = N-2。

手绘选择排序过程:

手绘选择排序过程

动画演示:

选择排序动画演示

代码实现:

代码语言:javascript
复制
public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
        sort(arr);
    }

    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            //目的:找到最小值的位置,并将该位置的数与i位置的数交换
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] > arr[minIndex] ? minIndex : j;
            }
            //找到最小值后,与i位置的数交换
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
            System.out.println("第" + i + "~" + (arr.length - 1) + "位置上的最小值索引为" + minIndex + ",最小值为:" + arr[minIndex] + ",本次排序结果:" + Arrays.toString(arr
            ));
        }
    }
}

运行结果:

代码语言:javascript
复制
第0~7位置上的最小值索引为4,最小值为:18,本次排序结果:[6, 15, 13, 17, 18, 20, 15, 9]
第1~7位置上的最小值索引为7,最小值为:15,本次排序结果:[6, 9, 13, 17, 18, 20, 15, 15]
第2~7位置上的最小值索引为2,最小值为:13,本次排序结果:[6, 9, 13, 17, 18, 20, 15, 15]
第3~7位置上的最小值索引为7,最小值为:17,本次排序结果:[6, 9, 13, 15, 18, 20, 15, 17]
第4~7位置上的最小值索引为6,最小值为:18,本次排序结果:[6, 9, 13, 15, 15, 20, 18, 17]
第5~7位置上的最小值索引为7,最小值为:20,本次排序结果:[6, 9, 13, 15, 15, 17, 18, 20]
第6~7位置上的最小值索引为6,最小值为:18,本次排序结果:[6, 9, 13, 15, 15, 17, 18, 20]

总结一下选择排序的过程:

arr[0~N-1]范围上,找到最小值所在的位置,然后把最小值交换到0位置。

arr[1~N-1]范围上,找到最小值所在的位置,然后把最小值交换到1位置。

arr[2~N-1]范围上,找到最小值所在的位置,然后把最小值交换到2位置。

arr[N-1~N-1]范围上,找到最小值位置,然后把最小值交换到N-1位置。

估算:很明显,如果arr长度为N,每一步常数操作的数量,如等差数列一般,所以,总的常数操作数量 = a*(N²) + b*N + c (a、b、c都是常数)

所以选择排序的时间复杂度为O(N²)。

插入排序

这个算法比较好理解,想像一下平时打扑克牌,我们很自然的就会把一张牌和手里的牌挨个比较一下,并把它插入到合适的位置。

扑克牌插入排序

过程:

  1. 想让arr[0~0]上有序,这个范围只有一个数,当然是有序的;
  2. 想让arr[0~1]上有序,所以从arr[1]开始往前看,如果arr[1]<arr[0],就交换。否则什么也不做;

  1. 想让arr[0~i]上有序,所以从arr[i]开始往前看,arr[i]这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动;
  2. 最后一步,想让arr[0~N-1]上有序,arr[N-1]这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动。

估算时发现这个算法流程的复杂程度,会因为数据状况的不同而不同。

如果某个算法流程的复杂程度会根据数据状况的不同而不同,那么必须要按照最差情况来估计。

很明显,在最差情况下,如果arr长度为N,插入排序的每一步常数操作的数量,还是如等差数列一般。

所以,总的常数操作数量 = a*(N²) + b*N + c (a、b、c都是常数)

所以插入排序排序的时间复杂度为O(N²)。

代码实现:

代码语言:javascript
复制
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
        sort(arr);
    }

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //想让0~i位置上有序,从i位置往前看,一直到左边的数不比自己大了,停止往左看
        for (int i = 1; i < arr.length; i++) {
            //j=i表示从i位置开始,j--表示往前看
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println("从" + i + "位置往前看,直到左边的数不比自己大,本次结果:" + Arrays.toString(arr));
        }
    }
}

运行结果:

代码语言:javascript
复制
从1位置往前看,直到左边的数不比自己大,本次结果:[15, 18, 13, 17, 6, 20, 15, 9]
从2位置往前看,直到左边的数不比自己大,本次结果:[13, 15, 18, 17, 6, 20, 15, 9]
从3位置往前看,直到左边的数不比自己大,本次结果:[13, 15, 17, 18, 6, 20, 15, 9]
从4位置往前看,直到左边的数不比自己大,本次结果:[6, 13, 15, 17, 18, 20, 15, 9]
从5位置往前看,直到左边的数不比自己大,本次结果:[6, 13, 15, 17, 18, 20, 15, 9]
从6位置往前看,直到左边的数不比自己大,本次结果:[6, 13, 15, 15, 17, 18, 20, 9]
从7位置往前看,直到左边的数不比自己大,本次结果:[6, 9, 13, 15, 15, 17, 18, 20]

欢迎阅读我的其他Java基础文章

看完点赞,养成习惯。 举手之劳,赞有余香。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-09-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 行百里er 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 冒泡排序
  • 选择排序
  • 插入排序
  • 欢迎阅读我的其他Java基础文章
相关产品与服务
云数据库 Redis
腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档