java五大排序算法之冒泡排序

发表于 2019-11-27

一.冒泡排序介绍

冒泡排序是我们得最多的排序方式之一，原因是简单易实现，且原理易懂。顾名思义，冒泡排序，它的排序过程就像水中的气泡一样，一个一个上浮到水面。

二.冒泡排序原理分析

三.冒泡排序代码实现

/**
 * @Author {LearnAndGet}
 * @Time 2019年1月8日
 * @Discription:
 */
package com.sort;

import java.util.Arrays;

public class MaopaoSort {
    
    static int[] array = {3,2,4,1,5,0};
    
    public static void maopaoSort(int[] a) 
    {
        //外层循环，是需要进行比较的轮数，一共进行5次即可
        for(int i=0;i<a.length-1;i++) 
        {
            //内存循环，是每一轮中进行的两两比较
            for(int j=0;j<a.length-1;j++) 
            {
                if(a[j] > a[j+1]) 
                {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp; 
                }
            }
            System.out.println("第"+(i+1)+"轮排序后的数组为: "+Arrays.toString(a));
        }
    }
    
    public static void main(String[] args) {
        maopaoSort(array);
    }
}

输出结果

第1轮排序后的数组为: [2, 3, 1, 4, 0, 5]
第2轮排序后的数组为: [2, 1, 3, 0, 4, 5]
第3轮排序后的数组为: [1, 2, 0, 3, 4, 5]
第4轮排序后的数组为: [1, 0, 2, 3, 4, 5]
第5轮排序后的数组为: [0, 1, 2, 3, 4, 5]

四.冒泡排序的优化

1 .观察上述代码和运行结果，我们可以发现，当第一轮结束后，最后一个数字一定是数组中最大的元素，那么我们在进行第二趟的两两比较时，实际上是没有必要再对第5个和第6个进行比较的。那么我们可以修改代码如下：

public static void maopaoSort(int[] a) 
{
    //外层循环，是需要进行比较的轮数，一共进行5次即可
    for(int i=0;i<a.length-1;i++) 
    {
        //内存循环，是每一轮中进行的两两比较
        //并且每一轮结束后，下一次的两两比较中可以少比较一次
        for(int j=0;j<a.length-i-1;j++) 
        {
            if(a[j] > a[j+1]) 
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp; 
            }
        }
        System.out.println("第"+(i+1)+"轮排序后的数组为: "+Arrays.toString(a));
    }
}

继续运行后，可以发现运行结果是一样的。

2 .当我们用数组：{1,2,0,3,5,4}来测试上述冒泡排序时，运行结果如下：

第1轮排序后的数组为: [1, 0, 2, 3, 4, 5]
第2轮排序后的数组为: [0, 1, 2, 3, 4, 5]
第3轮排序后的数组为: [0, 1, 2, 3, 4, 5]
第4轮排序后的数组为: [0, 1, 2, 3, 4, 5]
第5轮排序后的数组为: [0, 1, 2, 3, 4, 5]

可以看到，在第2轮排序完成后，其实我们就已经的到了排好序的数组，但是我们的程序并不知道，仍然进行了后续的无用工作。那么，我们如何来让程序知道已经完成好排序了呢？

这里可以想到，当某一轮的两两比较中，如果都没有发生数组元素的互换，那么其实排序工作已经完成了，所以我们可以考虑在程序中加入一个flag，默认为false，含义是该轮比较中是否发生了元素互换，当程序中执行到元素互换时，将该flag置为true，当该轮比较结束时，若flag为flase，则说明该轮比较未发生元素互换，那么排序完成，若flag为true，说明本轮比较仍然有元素互换，需要继续进行下轮排序。代码实现如下：

/**
 * @Author {LearnAndGet}
 * @Time 2019年1月8日
 * @Discription:
 */
package com.sort;

import java.util.Arrays;

public class MaopaoSort {
    
    static int[] array = {1,2,0,3,5,4};
    
    public static void maopaoSort(int[] a) 
    {
        //外层循环，是需要进行比较的轮数，一共进行5次即可
        for(int i=0;i<a.length-1;i++) 
        {
            boolean flag = false;
            //内存循环，是每一轮中进行的两两比较
            for(int j=0;j<a.length-i-1;j++) 
            {
                if(a[j] > a[j+1]) 
                {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                    flag = true;
                }
            }
            System.out.println("第"+(i+1)+"轮排序后的数组为: "+Arrays.toString(a));
            if(flag == false)
            {
                System.out.println("本轮中的两两比较未发生元素互换，排序已经完成啦");
                return;
            }
        }
    }
    
    public static void main(String[] args) {
        maopaoSort(array);
    }
}

运行结果：

第1轮排序后的数组为: [1, 0, 2, 3, 4, 5]
第2轮排序后的数组为: [0, 1, 2, 3, 4, 5]
第3轮排序后的数组为: [0, 1, 2, 3, 4, 5]
本轮中的两两比较未发生元素互换，排序已经完成啦

五.冒泡排序的时间复杂度

冒泡排序是一种用时间换空间的排序方法，最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序。在这种情况下，每一次比较都需要进行交换运算。举个例子来说，一个数列 5 4 3 2 1 进行冒泡升序排列

第一轮的两两比较，需要比较4次；得到 4 3 2 1 5
第二轮的两两比较，需要比较3次；得到 3 2 1 4 5
第三轮的两两比较，需要比较2次；得到 2 1 3 4 5
第四轮的两两比较，需要比较1次；得到 1 2 3 4 5

所以总的比较次数为 4 + 3 + 2 + 1 = 10次
对于n位的数列则有比较次数为 (n-1) + (n-2) + … + 1 = n * (n - 1) / 2，这就得到了最大的比较次数。
而O(N^2)表示的是复杂度的数量级。举个例子来说，如果n = 10000，那么 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2，相对10^8来说，10000小的可以忽略不计了，所以总计算次数约为0.5 * N^2。用O(N^2)就表示了其数量级（忽略前面系数0.5）。

综上所述，冒泡排序的时间复杂度为：O(n²)

本帖附件

点击下载

乱码三千 – 点滴积累 ,欢迎来到乱码三千技术博客站

Android面试题之事件分发机制一次性记忆

发表于 2019-11-26

本帖附件

点击下载

乱码三千 – 点滴积累 ,欢迎来到乱码三千技术博客站

Android面试题之Activity的四种启动模式一次性记忆

发表于 2019-11-26

每当我们换工作面试之前,总是会不由自主的刷起面试题,大部分题我们反反复复不知道刷了多少遍,但是今天记住了,等下一次面试的时候又刷着相同的面试题,我就想问在座的各位,Activity的生命周期,你们到底刷过多少遍 [哭笑] 作为一名程序员把时间浪费在重复性劳动上是极其不能忍受的因此为了让自己省去不必要的脑力开销我给自己总结了一份面试相关的记忆技巧,在这里分享给大家记忆不是目的把知识变成自己的才最关键

哪四种启动模式

standard:默认启动模式,每开启一个activity就在任务栈中创建一个新的实例
singleTop:任务栈顶部有就复用,没有就重新创建,
singleTask:任务栈中有就将实例上方所有的实例全部销毁使其显示在最顶端,没有就重新创建一个新的实例在搜索界面比较常用按下主页其余网页全部被关闭
singleInstance:重新为新创建activity(实例)开启一个单独的任务栈,且该任务栈中有且仅有一个实例该模式特点如下图:

如果快速记忆

其实只要将它们的英文名称单词反过来就好理解了

singleTop—>Top single 顶部只有一个不允许存在两个相同的Activity
singleTask—>Task single 任务栈中只有它这一个Activity 那么一旦调用它任务栈除它以外的所有Activity都会被销毁
singleInstance—>Instance single 实例被孤立了进了小黑屋被单独的一个任务栈给关着
standard—>正常模式这个应该好记忆

本帖附件

点击下载

乱码三千 – 点滴积累 ,欢迎来到乱码三千技术博客站

Android面试题之四大组件一次性记忆

发表于 2019-11-26

每当我们换工作面试之前,总是会不由自主的刷起面试题,大部分题我们反反复复不知道刷了多少遍,但是今天记住了,等下一次面试的时候又刷着相同的面试题,我就想问在座的各位,Activity的生命周期,你们到底刷过多少遍 [哭笑] 作为一名程序员把时间浪费在重复性劳动上是极其不能忍受的因此为了让自己省去不必要的脑力开销我给自己总结了一份面试相关的记忆技巧,在这里分享给大家记忆不是目的把知识变成自己的才最关键

四大组件是什么？

Activity【活动】：用于页面展示和交互。
Service【服务】：后台运行服务，不提供界面呈现。
BroadcastReceiver【广播接收器】：用来接收广播。
Content Provider【内容提供商】：支持在多个应用中存储和读取数据，相当于数据库。

如何一次性记忆四大组件

如果让你去设计一款操作系统,你会怎么设计?

针对具有交互性的操作系统而言,需要具备以下几种基础功能 :

首先程序的界面的展示是必不可少的这是其一　（Activity）
其二程序中也许不止一个界面多个界面之间需要进行通信和数据传递 (BroadcastReceiver)
第三多个程序之间需要进行通信和数据传递 (Content Provider)
第四　程序界面未显示的时也能随时响应用户操作　可后台运行 (Service)

*当你理解了设计者的用意后确实能很好的理解四大组件的含义, 但是并不意味着你能很好的记忆住他们在面试过程中你必须要有较快的反应速度 *

在这里我抛出几种右脑记忆思路:

取四大组件英文首字母得到 ABCS 当对方问你四大组件都有哪些时你能立马联想到英文字母ABC
这四大组件能让你联想到什么画面?

到这里有些人可能会说了四大组件这么好记还用得着这么费劲记忆?

我想说的是如果你在工作中经常使用这些知识那么它们对你来讲是非常熟悉的但是针对初学者或者很长时间没有使用的开发者而言一套合理的记忆技巧是非常有帮助的我想若干年后你也许忘了四大组件都有哪些了但是你依然记得文本所说的ABC 这个时候回忆起来也只是一念之间的事儿

本帖附件

点击下载

乱码三千 – 点滴积累 ,欢迎来到乱码三千技术博客站

大脑开发之右脑开发

发表于 2019-11-26

前言

工欲善其事必先利其器,大脑是我们每个人最为珍贵的宝藏,它的潜能是无穷无尽的,强大到令人可怕,

但是普通人对于大脑的了解和使用是即为匮乏的作为一名现代人如果你想跑得比别人快站得比别人高那么就必须学会如何开发我们的大脑, 让大脑更好的为我们服务

左脑和右脑分工

左右脑检测

如果你看见这个跳舞女孩是顺时针转，说明你用的是右脑；

如果是逆时针转，说明你用的左脑。

耶鲁大学耗时5年的研究成果。据说，14%的美国人可以两个方向都能看见。顺时针转的话，属於是用右脑较多的类型。逆时针转属於使用左脑较多的类型。大部分人的眼里里是逆时针方向转动，但也有人看来是顺时针方向转动的。

为什么要开发右脑

左脑刺激机会相对比右脑多大部分人左脑发达

人类左脑主管语言、逻辑、书写及右侧肢体运动，而右脑主管色彩、空间感、节奏和左侧肢体运动。在频繁使用语言的过程中，特别是国内的应试教育，侧重偏向于逻辑、记忆为主，人的左脑得到更多刺激，使左脑相对发达于右脑

右脑的存储量是左脑的100万倍反应时间要快于左脑
右脑记忆更容易转化为长期记忆极大缩短知识的记忆时间

右脑记忆的主要方式

图像记忆
声音记忆
感觉记忆

如何训练和开发

养成将知识转成图像声音或者感觉的形式进行记忆的习惯
养成听音频的习惯
养成画图的习惯
养成闭目空间想象回忆的习惯

本帖附件

点击下载

乱码三千 – 点滴积累 ,欢迎来到乱码三千技术博客站

右脑记忆法之图像记忆

发表于 2019-11-26

本帖附件

点击下载

乱码三千 – 点滴积累 ,欢迎来到乱码三千技术博客站

右脑记忆法之联想记忆

发表于 2019-11-26

严格来说联想记忆不属于单独的右脑记忆法,由于在联想的过程中,涉及到图像声音甚至是感觉,

因此联想记忆更像是一种记忆检测和整理的手段通过画思维图并且利用联想的手段联想出脑袋中所有的知识这些知识的载体多种多样有可能是一幅幅图像也有可能是一段声音,或者是一阵刺骨的疼痛

联想有检测右脑知识的功能当然他也有记忆的功能, 通过联想手段记忆知识的特点是:

用已知的知识去联想新的知识,或者说将新知识关联到熟悉的知识上

这也是为什么懂得越多,学得越快

联想记忆重要分为两大种

相似联想
对比联想

相似联想

新事物和脑海中已知事物(图像声音等等)相似或者接近,类似举一反三

对比联想

新事物和脑海中已知事物刚好是两个极端,例如水和火

总结

联想记忆有

总结复习和检测右脑知识的功能
快速记忆新知识的功能 (将信息联想于已知事物,可能是相似也可能是对比)

本帖附件

点击下载

乱码三千 – 点滴积累 ,欢迎来到乱码三千技术博客站

Android面试题之Activity和Fragment生命周期一次性记忆

发表于 2019-11-26

每当我们换工作面试之前,总是会不由自主的刷起面试题,大部分题我们反反复复不知道刷了多少遍,但是今天记住了,等下一次面试的时候又刷着相同的面试题,我就想问在座的各位,Activity的生命周期,你们到底刷过多少遍 [哭笑] 作为一名程序员把时间浪费在重复性劳动上是极其不能忍受的因此为了让自己省去不必要的脑力开销我给自己总结了一份面试相关的记忆技巧,在这里分享给大家记忆不是目的把知识变成自己的才最关键

前提

需要熟悉Activity的生命周期通过Activity的周期去对比理解和记忆Fragment生命周期

Activity的生命周期

假设你已经非常熟悉Activity的生命周期了,那么接下来咱们看Fragment的生命周期图

Fragment的生命周期

找出他和Activity的相同之处

这部分完全和Activity一模一样可以不用记忆它,咱们来看不同的地方

其实这部分才是人们最容易搞混和记不住的地方那咱们来分析一下:

Fragment比Activity多了几个生命周期的回调方法

onAttach(Activity) 当Fragment与Activity发生关联的时候调用
onCreateView(LayoutInflater, ViewGroup, Bundle) 创建该F
onActivityCreated(Bundle)当Activity的onCreated方法返回时调用
onDestroyView() 与onCreateView方法相对应，当该Fragment的视图被移除时调用
onDetach() 与onAttach方法相对应，当Fragment与Activity取消关联时调用
PS：注意：除了onCreateView，其他的所有方法如果你重写了，必须调用父类对于该方法的实现

这些方法理解起来并不费劲但是要完美记在脑子里还是需要花上一番功夫的

那咱们一个一个来先从创建开始:

1.首先 onAttach方法: 和Activity进行关联的时候调用这个放在第一个应该好理解

2.我们知道 Activity在onCreate方法中需要调用setContentVIew()进行布局的加载,那么在Fragment中onCreateView就相当于Activity中的setContentVIew

3.onActivityCreate是一个额外的方法为了告诉Fragment当前Activity的创建执行情况方便Fragment的后续操作

先后顺序

已知Fragment是依赖Activity而存在的它们都有着相同的生命周期方法那么先调用Activity的还是Fragment的呢? 这里分两种情况

如果是创建那么先创建Activity 后创建Fragment
如果是销毁那么先销毁Fragment 后销毁Activity

网上有很多文章说Activity的onCreate方法在Fragment的onCreateView之后执行,这是不正确的 Fragment一般都是在Activity的onCreate()中创建要么通过布局加载的方式要么通过new创建Fragment对象的方式如果没有Activity的onCreate 哪来的Fragment