文档章节

java基础的几个算法

noob_fly
 noob_fly
发布于 02/17 21:31
字数 3454
阅读 17
收藏 0

一般对于排序算法我们通常考虑: 是否稳定(相同值的两个数相对位置在修改前后是否会变) 和 时间复杂度(算法执行次数的规模量级)。至于说空间复杂度(算法在运行过程中临时占用存储空间大小的量度)其实对于每种算法具体实现代码风格迥异。

从实现上如何处理稳定

一般而言:
稳定的排序算法有:冒泡排序、插入排序、归并排序和基数排序;
不稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。
个人感觉在代码实现各种算法时,是否稳定取决于在处理相同值的两个不同数据下标是否swap。比如说:

  • 冒泡: 处理等值时,取下标大的就不用swap可以达到稳定,但是取下标小的得swap则不稳定。(取小下标 多做一次swap)
  •  插入: 处理等值时, 前插处理则不稳定, 跳过则稳定。(从后往前做前插直到第一次小于的位置上都得依次swap)
  • 选择: 选择一个最大的值置于队尾。在判定最大值时,如果等值取下标大的可以达到稳定,取小标小的则不稳定。(取大下标 多做一次swap)

等等诸如此类在实现的处理细节决定是否可以做成稳定, 但是同样的带来执行的次数会多。 而对于实际上我们只需要知道排序后的结果数组,当然执行规模越少,效率越快 越好喽。

快排就没办法达到稳定了, 因为是队首与队尾双边查找,然后置换。 相同的值先查到就先置换,后查到就更靠近中间位置。

如何区分时间复杂度

冒泡、选择、插入:  平方阶(O(N2))排序

经过实际代码可以发现,这些都是在从前往后的轮询数组,只是边界在慢慢变小,边界每变化一次就轮询一次。 (冒泡与选择相同都在于轮询数组比较值取大小;不同在于冒泡是每次比较后都swap,而选择只是记录需要的数据下标,最后才将下标与队尾swap)

快速、堆和归并:  线性对数阶(O(nlog2n))排序

经过实际代码可以发现, 都类似于将排序数组切分成2部分递归处理。

基数: 线性阶(O(n))排序

核心实现

全部代码见:https://github.com/noobFly/sort-algorithm.git。

个人感觉需要控制好轮询边界和等值时如何处理问题。可以相应提高计算效率。

冒泡排序

相邻的两个值比较,将最大/小的值逐步换至队尾/首。

需要注意的是: 1> 如果本次轮询中都没有swap,则说明整个数组都已经有序,不用再往下执行了。 2> 每次轮询完一次后,下一次的轮询边界应该相应缩小。

public class BubbleSort extends AbstractSort {

    @Override
    public int[] sort(int[] param) {
        int count = 0; //已经排序过的次数
        int max_count = param.length - 1;//最大的排序次数
        while (count <= max_count) {
            boolean is_swap = false; // 判定本轮是否swap了,没有则说明数组已经有序, break
            for (int i = 1; i <= max_count - count; i++) { // 控制好边界
                if (param[i - 1] > param[i]) {
                    swap(param, i, i - 1);
                    is_swap = true;
                }
            }
            count++;
            if (!is_swap) {
                break;
            }
        }
        System.out.println(String.format("总量:%s, 轮询次数: %s", param.length, count));
        return param;
    }

    public static void main(String[] args) {
        int[] param = new BubbleSort().sort(new int[] { 1, 2, 3, 5, 8, 6, 4, 9, 7 });
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < param.length; i++) {
            str.append(param[i]);
            if (i != param.length - 1) {
                str.append(" ");
            }
        }
        System.out.println(str.toString());

    }
}

结果:

选择排序

选中最大/小值置于已经排序队列的队尾,在未排序队列中递推执行。
与冒泡的异同在于: 都是轮询比较值的大小,只是冒泡是每次比对后都可能做swap,而选择是记录下下标,与本次轮询数组的边界的队首/队尾一次swap,当然如果下标就是队首/队尾就不用swap。

public class SelectionSort extends AbstractSort {

    @Override
    public int[] sort(int[] param) {
        for (int i = 0; i < param.length; i++) { // 此处因是升序排序,所以i的值就是边界
            int min_index = getMinIndex(param, i);
            swap(param, i, min_index);
        }
        return param;
    }

    /**
     * 在指定起始位置之后队列中查找最小值的下标
     *
     * @param param
     * @param start
     * @return
     */
    private int getMinIndex(int[] param, int start) {
        int min_index = start;
        for (int j = start + 1; j < param.length; j++) {
            if (param[j] < param[min_index]) {
                min_index = j;
            }
        }
        return min_index;
    }

}

插入排序

将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列,将扫描到的当前元素依次与已排序序列从后往前递推比较,如果当前元素小,则swap,  直到边界。

/**
 * 稳定 插入排序 1)将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
 * <p/>
 * 2)从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面
 * 。) Created by bear on 2016/2/29.
 */
public class InsertionSort extends AbstractSort {

    /**
     * 假定前面都是已从小至大排序的队列:如果当前下标的值小于前一下标的值,交换位置,并在已排序队列中从后向前递推再判断;
     *
     * @param param
     * @return
     */
    public int[] sort(int[] param) {
        for (int i = 1; i < param.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (param[j] > param[j + 1]) {
                    swap(param, j, j + 1);
                } else {
                    break; // 如果后面的要不小于,则break; 边界
                }
            }

        }

        return param;
    }

    public static void main(String[] args) {
        int[] param = new InsertionSort().sort(new int[] { 4, 5, 3, 5, 8, 6, 4, 9, 7 });
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < param.length; i++) {
            str.append(param[i]);
            if (i != param.length - 1) {
                str.append(" ");
            }
        }
        System.out.println(str.toString());

    }
}

结果: 

希尔排序

按步长分组并插入排序,递减步长至0。步长的起始值可以按需定义。

//todo

快排

选择一个基准元素,通常选择第一个元素或者最后一个元素, 通过一趟扫描,将待排序列分成两部分, 前比基准元素小,后大于等于基准元素, 此时基准元素在其排好序后的正确位置,  然后再用同样的方法递归地排序划分的两部分。

实现的细节: 本例以第一个元素作为基准数。(细节在于:前部分大于等于基准数的都置换到后半部分,最后留基准数与重合指针位置比对确定好边界)

  1.   有2个指针, high从队尾找到第一个不比基准数大的,low从队首找到第一个比其大的数,边界分别是队尾,队首。 操作指针的时候切记一次只能操作一个,保证 low 一定 <= high !! (如果同时操作,可能就交叉了!)
  2.  快排思想:后面部分是大于等于基准数的,所以 队尾指针的数值相等也左移, 队首则不移动。即:
    1. while (param[high] >= radix && low < high)   : 跳出循环一定是  param[high] < radix ||  low == high (没可能low<high在一个++或--就直接 low> high 了)
    2. while (param[low] < radix && low < high) : 跳出循环一定是   param[low] >= radix  ||  low == high
  3. 轮询查找过程中 low 一定 <= high 。  当 low < high 跳出【步骤2】循环时, 一定是 param[low] >= radix >  param[high] ; 进行swap,再继续轮询。
  4. 退出大轮询while (low < high) 循环一定是  low ==high ! 只有相同时才能停止比较。
  5. 再用这个low/high小标的值与基准数比较:   基准数大, 则边界就是这个low; 如果基准数小, 则边界是low-1. 并swap. 
package com.noob.sort;

/**
 * 不稳定(判断时,若相等,则出现不稳定状况) 快速排序:关键值排序
 * (1)基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,
 * 此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
 * <p>
 * Created by bear on 2016/3/2.
 */
public class QuickSort extends AbstractSort {
    @Override
    public int[] sort(int[] param) {
        return sort_core(param, 0, param.length - 1);
    }

    /**
     * 左边 < 关键值 <= 右边
     *
     * @param param
     * @param start 开始下标
     * @param end 结束下标
     * @return
     */

    private int[] sort_core(int[] param, int start, int end) {
        int radix = param[start]; //选开始位置为基准数
        int low = start + 1; // 队首指针开始位置为除基准数后下标
        int high = end; // 队尾指针开始位置

        while (low < high) {// 确保两个指针不交叉!! 快排思想:后面部分是大于等于基准数的,所以 队尾指针的数值相等也左移,队首则不移动
            /**
             * 跳出循环时的状态: param[high] < radix || low == high
             */
            while (param[high] >= radix && low < high) {
                //队尾指针的值 >= 基准值  & 队首指针下标 < 队尾首指针下标
                high--; //队尾指针前移
            }
            /**
             * 跳出循环时的状态: param[low] >= radix || low == high
             */
            while (param[low] < radix && low < high) {
                //队首指针的值 < 基准值   & 队首指针下标  <  于队尾首指针下标
                low++; //队首指针后移
            }

            if (low >= high) {
                // low 一定 <= high
                if (low > high) {
                    System.out.println(String.format("error test: low %s > high %s : %s", low, high, low > high));
                }
                break;
            } else {
                if (param[low] == param[high]) {
                    //一定是param[low] > param[high]
                    System.out.println("error1");
                    break;
                }
                swap(param, low, high); // 换好之后 param[high] 一定  > param[low] 
            }

        }
        if (low == high) {
            // 基准数大, 则边界就是这个low; 如果基准数小, 则边界是low-1. 并swap. 
            Integer limit = radix > param[low] ? low : low - 1;
            swap(param, start, limit);
            //分割成左右2部分
            if (limit - 1 > start) {
                sort_core(param, start, limit - 1); //左部分
            }
            if (limit + 1 < end) {
                sort_core(param, limit + 1, end); // 右部分
            }

        } else {
            System.out.println(String.format("error test: low %s != high %s ", low, high));

        }
        //System.out.println(toString(param));
        return param;

    }

    public static void main(String[] args) {
        int[] param = new int[] { 5, 4, 3, 2, 1, 0, 2, 5, 6, 4, 9, 5 };
        System.out.println(toString(new QuickSort().sort(param)));

    }

}

运行结果:

没有打印出任何 low > high 的日志;证明了: low和high严格控制在 low<=high的情况!!

归并排序

归并排序: 采用分治法,递归将数组分割成两部分成两个已排序队列,再合并至新的数组中。

两个数组都有一个从队首开始扫描的指针,依次对领一个数组指针值比较,小的先写入新的store数组中,指针后移: ++,再循环比较。

//TODO

堆排序

先了解三个概念:

  1. 完美二叉树: 一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树
  2. 完满二叉树: 完全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐
  3. 满二叉树: 所有非叶子结点的度都是2。( 只要你有孩子,你就必然是有两个孩子.)

堆排序利用的是二叉树的特性。每一次的排序完成,都将剩下的数组值当作新的一颗数。

2*root + 1 与 2*root + 2  是root节点的2个子节点。

    /**
     * @param param
     * @param lastIndex 最后一个值的下标
     */

    private void createMaxHeap(int[] param, int lastIndex) {
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {//获取根节点的下标
            int root = i;
            int bigger_index = 2 * root + 1;//左右子节点中值最大的下标
            if (bigger_index < lastIndex) {
                // 若左节点的下标小于最大的坐标,说明有右节点
                if (param[bigger_index] < param[bigger_index + 1]) {
                    bigger_index++;
                }
            }

            if (param[root] < param[bigger_index]) {
                swap(param, root, bigger_index);
            }
        }
    }

基数排序

定义的radix与max_position都与数组的最大值有关系; 桶的数量是10, 因为阿拉伯数是0-9。

从个位开始, 扔进桶内确定好位置,再交由下一位的桶排序。

package com.noob.sort;

/**
 * 按个位、十位、百位...排序 -----> 当前版本对负值无效
 * <p/>
 * 稳定排序 基数排序 Created by bear on 2016/3/6.
 */
public class RadixSort extends AbstractSort {
    private int[] radix        = new int[] { 1, 1, 10, 100, 1000 }; // 与数组的最大值的量级有关
    private int   max_index    = 10;                               //桶的数量 因为阿拉伯数是0-9
    private int   max_position = 3;                                //数组最大值的位数

    public int[] sort(int[] param) {
        for (int position = 0; position < max_position; position++) {
            sort_core(param, position);
        }
        return param;
    }

    /**
     * 按指定位上的数值排序
     *
     * @param param
     * @param end_index
     * @param position
     */
    private void sort_core(int[] param, int position) {
        int cap = param.length - 1;

        int[] count = new int[max_index];//记录每个桶统计个数
        int[] store = new int[cap + 1]; // 桶的容量

        // 置空各个桶的数据统计
        for (int i = 0; i < max_index; i++) {
            count[i] = 0;
        }

        // 指定位的值与桶的编号一一对应。统计对应桶有多少数量
        for (int i = 0; i <= cap; i++) {
            count[getDigit(param[i], position)]++;
        }

        for (int i = 1; i < max_index; i++) {
            count[i] = count[i] + count[i - 1]; // 通过累加可以确定每个指定位的值在store桶上的边界。
        }
        // 这里要从右向左扫描,保证排序稳定性
        for (int i = cap; i >= 0; i--) {
            int digit = getDigit(param[i], position);
            store[count[digit] - 1] = param[i]; //放入对应的桶中,count[j]-1是第j个桶的右边界索引
            count[digit]--; // 对应桶的装入数据索引减一
        }

        // 将已分配好的桶中数据再倒出来,此时已是对应当前位数有序的表
        for (int i = 0, j = 0; i <= cap; i++, j++) {
            param[i] = store[j];
        }
    }

    /**
     * 获取指定位上的数值
     */
    private int getDigit(int param, int digit) {
        return (param / radix[digit]) % 10;
    }

}

 

          

 

 

 

© 著作权归作者所有

共有 人打赏支持
上一篇: redis实现的锁
下一篇: mybatis(7) - 分页
noob_fly
粉丝 8
博文 101
码字总数 119913
作品 0
广州
程序员
私信 提问
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础,在BAT的初面中,会涉及到比较多的java基础知识,所以比较重要,下面我介绍的书籍内容是由浅到深。 1.Thinking in java:这本书被称为Java的三大圣经之一,虽然书比...

android自学
2018/07/25
0
0
java语言编写的小程序怎么编译成 windows直接运行的EXE程序?

在eclipse上编写的java文件 只能用JVM运行吗? java编写的程序能不能像C语言一样编译后 能生成.exe运行程序的,或者借助其他编译插件实现,自己用C语言写过几个小的算法类程序,可以找到.exe文件...

NewBeeJack
2016/08/20
2.6K
4
Java程序员必读书单,家族又添新成员

点击关注异步图书,置顶公众号 每天与你分享IT好书 技术干货 职场知识 参与文末话题讨论,每日赠送异步图书。 ——异步小编 有些革命出其不意地吸引了全世界的眼球。Twitter、Linux操作系统和...

异步社区
2018/05/09
0
0
请问大数据运维转开发需要补充哪些知识?

之前做了差不多三年的大数据运维开发,包括hadoop和spark集群等,工作中会使用python,shell写一些运维脚本,比较少会用到java。现在想应聘大数据开发的岗位。我上网搜了下大数据开发的岗位要...

雪地烟斗
2017/09/05
1K
5
如果你想学习Java,那么就来看这篇文章

一、前言 我是从大二开始学习的Java,当时的目标是Java Web开发,当时并不想考研,所以当时的学习是以就业为主,现在我大三了,学习Java Web开发已经一年了,因为种种原因,决定要考研,所以...

Jivanmoon
2018/08/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如果让你写一个消息队列,该如何进行架构设计?

面试题 如果让你写一个消息队列,该如何进行架构设计?说一下你的思路。 面试官心理分析 其实聊到这个问题,一般面试官要考察两块: 你有没有对某一个消息队列做过较为深入的原理的了解,或者...

李红欧巴
今天
4
0
错题

无知的小狼
今天
2
0
PowerShell因为在此系统中禁止执行脚本的解决方法

参考:window系统包管理工具--chocolatey 报错提示: & : 无法加载文件 C:\Users\liuzidong\AppData\Local\Temp\chocolatey\chocInstall\tools\chocolateyInstall.ps1,因为在此系统上禁止运...

近在咫尺远在天涯
今天
3
0
TP5 跨域请求处理

https://blog.csdn.net/a593706205/article/details/81774987 https://blog.csdn.net/wyk9916/article/details/82315700...

15834278076
今天
3
0
深入理解java虚拟机-Java内存区域与内存溢出异常

深入理解java虚拟机 Java内存区域与内存溢出异常 运行时数据区域 程序计数器 线程私有,内存小,是当前线程执行的字节码行号指示器,字节码解释器通过改变这个计数器的值来选取下一条需要执行...

须臾之余
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部