文档章节

Android常用算法

Magic_锋
 Magic_锋
发布于 07/29 17:03
字数 1434
阅读 5
收藏 0

最近准备研究下Android的算法,以下的内容算作是个笔记吧,如果有不对的地方,还请各方大神给与指出.....

1.插入排序

    插入排序思路: 首先默认数组中第一个( [0] )是排好序的,从第二位( [1] )开始进行判断,如果第二位大于第一位的话,就插入到第二位,不大于的话,就将第一位往后移动一位,变成第二位,原先的第二位插入到第一位,但是随着数值的增多,时间复杂度增加O(n²) ,平方阶排序的一种

   代码如下

/**
     * 插入排序
     * @param array 没有排序的数组
     * @return 从小到大排好序的数组
     */
    public int[] sortInsert(int[] array){
        for(int i=1;i<array.length;i++){
            int temp = array[i];
            int j;
            for(j=i-1;j >= 0 && temp< array[j]; j--){
                array[j + 1] = array[j];
            }
            array[j + 1] = temp;//插入进数组
        }
        return array;
    }

 

2.选择排序

选择排序的思路是先从未排序的数组中找到最小数值的元素,放到新数组第一位上,然后从数组中剩下未排序部分的元素中再选择最小值的元素,并将此值放到新数组的结束位上,以此类推,,但是随着数值的增多,时间复杂度增加O(n²) ,平方阶排序的一种

代码如下

/**
     * 选择排序
     * @param arr 没有排序的数组
     * @return 从小到大排好序的数组
     */
public int[] sortSelect(int[] arr){
        for (int i=0;i<arr.length;i++){ //循环轮数
            int min = i; //假设最小数值对应的角标
            for (int j=i+1;j< arr.length;j++){ //每轮循环次数
                if (arr[j] < arr[min]){
                    min = j;
                }
            }

            //找出最小值后,进行交换
            if (arr[i] > arr[min]){
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
        return arr;
    }

 

3.冒泡排序

冒泡排序的思路是:从左往右两两进行比较,较大的值靠右边放,以此类推,直到结束,,但是随着数值的增多,时间复杂度增加O(n²) ,控件复杂度为O(n)平方阶排序的一种

代码如下

/**
     * 冒泡排序
     * @param arr 没有排序的数组
     * @return 从小到大排好序的数组
     */
    public int[] sortBubble(int[] arr){
        for (int i=0;i<arr.length - 1;i++){
            for (int j=0;j<arr.length- 1 - i;j++){
                if (arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }

 

4.快速排序

快速排序的思路:

        是冒泡排序的进化版,随便选个基准数,一般取数组的第一位即可,然后将一组未排序的数组按照基准数分成两部分,第一部分中的数值都比基准数要小,第二部分中的数值都比基准数要大,基准数放在两部分中间位置,然后同样的方法再对两部分分别进行排序,使用递归,平均时间复杂度O(nlogn),最差时间复杂度为O(n²),最优时间复杂度为O(nlogn),空间复杂度最优为O(logn),最差为O(n),也就是退化冒泡排序

/**
     * 快速排序
     * @param arr 未排序的数组
     * @param start 起始位置
     * @param end 结束位置
     */
    public void sortQuick(int[] arr,int start,int end){
        if (start>end)return;
        int i,j,temp,t;
        i = start; //起始位 , 0
        j = end; //结束位,数组长度-1
        temp =arr[start]; // 选择数组第一位作为基准
        while(i<j){
            while(i<j && temp<=arr[j]){ //先从数组最后往前检查,当基准数小于时,j--,继续往前走,一旦大于了,就停下,执行下一个while循环
                j--;
            }

            while(i<j && temp>=arr[i]){ //从数组开始位,往后检查,当基准数大于时,i++,接着往前走,直到基准小于时候,停下, 然后执行下面交换逻辑
                i++;
            }

            //两个while循环执行完,交换两个循环停下位置的数值,交换完毕后,再接着走最外侧的大while循环,直到i>j时,跳转整个while循环,执行下面基准位的赋值逻辑
            if (i<j){
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        //将基准位的数值赋值给中间i和j相遇的位置
        arr[start] = arr[i];
        arr[i] = temp;
        //以上是第一轮检查,并将基准位确定出来,此时,基准位左侧都比基准数值小,右侧都比基准数大

        //递归遍历基准位置左侧的数组
        sortQuick(arr,start,j-1);
        //递归遍历基准位置右侧的数组
        sortQuick(arr,i+1,end);
    }

 

5.堆排序

       在说堆之前,先说下几个基础的知识点,树,二叉树,完全二叉树,完美二叉树

          

上图就是树

树指的是n个节点的集合,当n=0时,称为空树,有图可见是一对一或者一对多的关系

二叉树指每个节点上的最多有两个子树的树

完全二叉树指深度为k层的树,上图的深度为4,1至k-1层的子树都是满的,也就是每个1至k-1层的每个节点都有两个子树,而k层可以不是满的,但是集中在最左侧

完美二叉树指k层的树的每个节点都有两个子树

而堆就是一种完全二叉树,堆分为大顶堆和小顶堆

大顶堆指: 父节点的值都比子节点的值要大,反之是小顶堆

 

待续...

© 著作权归作者所有

Magic_锋
粉丝 0
博文 58
码字总数 35503
作品 0
东城
程序员
私信 提问
Android知识图谱:我们到底需要学习哪些Android知识?

前言 如果你也学习Android,那么你大概率会看过我的文章。经常有读者给我留言:“该怎么学习Android?”、“日常学习Android的方法是什么”。 所以,今天,我将献上一份《Android知识图谱》,...

Carson_Ho
04/22
0
0
北京目标猎头代招知名手机游戏公司 安卓人员

岗位要求: 1、 精通java,熟悉jdk、多线程、io以及常用的算法和数据结构等。 2、 熟练掌握android的api,理解android的体系结构,掌握android中界面绘制,后台运行,数据存储等的原理。 3、...

targethr
2012/03/22
644
26
17年本科应届生Android方向在上海这样的一线城市薪资多少合适?

各位好,我是一名即将毕业的普通二本应届生,想从事Android开发方向的工作,没有实习经历,大学期间基本上玩了两年,从大三开始自学到现在,期间看了很多网络相关、数据结构与算法相关、操作...

zcczzz
2016/12/21
7.6K
44
招聘Android/iOS开发工程师 (其他岗位看文末)

金三银四招聘季节来了,在广州和深圳的小伙伴们,想换工作不妨考虑下。 BIGO 地点:广州 Android开发工程师 岗位职责 参与公司移动产品的迭代开发工作,能高质量的完成产品需求的方案设计和开...

D_clock爱吃葱花
03/04
0
0
步步高教育电子招聘2019届Android开发实习生 - 知乎

步步高教育电子招聘2019届Android开发实习生。 坐标广东 东莞,简历投递时间:5月8号到5月18号。 零、快来吧~ 简历投递地址:zmywly8866@gmail.com,投递格式如下: 标题:应聘19届Android开...

张明云的知识共享
10/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Nebula 架构剖析系列(二)图数据库的查询引擎设计

摘要 上文(存储篇)说到数据库重要的两部分为存储和计算,本篇内容为你解读图数据库 Nebula 在查询引擎 Query Engine 方面的设计实践。 在 Nebula 中,Query Engine 是用来处理 Nebula 查询...

NebulaGraph
26分钟前
8
0
表示数值的字符串

Garphy
28分钟前
4
0
将.docx文件转化为.pdf文件

将.docx文件转化为.pdf文件 在需要转化.docx为.pdf的文件夹中打开powershell然后运行该程序,可以将文件夹下所有.docx文件转化为.pdf文件。 from win32com.client import Dispatch, constant...

davidwbnu
31分钟前
6
0
技术沙龙|原来落地AI应用是这么回事儿!

目前人工智能已经迈入应用落地之年,作为备受关注的话题,在重磅政策的加持下市场规模迅速扩大并渗透到各行各业的形势越发鲜明。在此背景下,作为国内不容忽视的创新企业之一,京东AI依托于N...

京东云技术新知
33分钟前
6
0
linux交互界面颜色配置

PS1="\[\e[37;40m\][\[\e[32;40m\]\u\[\e[37;40m\]@\h\[\e[35;40m\]\W\[\e[0m\]]\\$ " export PROMPT_COMMAND='{ msg=$(history 1 | { read x y; echo $y; });user=$(whoami); echo $(date "......

SibylY
33分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部