排序概述 排序是一种将给定的一些元素按照一定的规则进行重排列的动作。 下面介绍的为常见的8大排序算法及Java.Util包Arrays类中自带的排序算法sort的使用。 介于Arrays类中已经实现了效率非常高的Daul-Pivot QuickSort,在日常的开发中,若需要使用排序功能的话,可以直接使用该轮子。 排序算法的实现及测试 package cn.young22.dsa.ch08; import java.util.ArrayList; import java.util.List; /** * 一个用于给数组从小到大排序得到类 * * @author Young * */ public class SortArray { /** * bubbleSort * * @description 排序思想. * 外层: 循环进行数组长度次数 * 内层: 依次比较相邻两个元素的值,若前一个元素比后一个元素大, * 交换两个元素的位置,直至最后一个元素,下一趟遍历则遍历值倒数第二个元素为止,依次类推 * 冒泡排序的时间复杂度为O(n^2) * @param a 待排序数组 */ public static <… Continue Reading 05数据结构与抽象 排序

1栈的简介 package cn.young22.dsa.ch05; import cn.young22.dsa.ch06.ArrayStack; import cn.young22.dsa.ch06.LinkedStack; import cn.young22.dsa.ch06.VectorStack; /** 测试所实现的 * LinkedStack * VectorStack * ArrayStack * */ public class StackDemo1 { public static void main(String[] args){ // 初始化stringStacks // StackInterface stringStack = new LinkedStack(); // 测试ArrayStack // StackInterface stringStack = new ArrayStack(); // 测试 VectorStack StackInterface stringStack =… Continue Reading 03数据结构与抽象 栈(Stack)

1引例 package cn.young22.dsa.ch04; /** 这个类使用来说明用不同的算法来做同一件事的效率的差别 * 使用三个算法来计算从1加到一个很大的整数这个式子 1 + 2 + 3 + … + A_LARGE_NUMBER * * 算法1使用一个循环,让计数器counter从1加到A_LARGE_NUMBER * 算法2使用双重循环,在外层由A_LARGE_NUMBER控制循环的总次数, * 在内层有index来控制循环的次数,内层循环执行的是算出当前要加的整数 * 算法3使用高斯算法直接计算出结果 counter = (1 + A_LARGE_NUMBER) * A_LARGE_NUMBER / 2 * * 使用纳秒为单位计算以各个算法得到求和结果的时间,进行比较,从而得出,需要寻求更好的算法去提高效率 * * */ public class RecordTimeOfThreeAlgorithms { public static void main(String[] args){ //… Continue Reading 02数据结构与抽象 算法效率分析

1.包(Bag)的简介 1.1 什么是包 在现实生活中,我们常见的包有购物袋,塑料袋,布袋等。这些物品的共同特性是他们都是一种容器,可以用来装物品。 而抽象数据类型(ADT)包是没有特定次序的对象的有限集合。这些对象具有相同的或相关的数据类型。包可以含有重复项。 包的行为有: 1.得到当前包中的项数 2.查看包是否为空 3.将给定的对象加到包中 4.从包中删除一个未指定的对象 5.可能的话,从包中删除一个具体对象的一次出现 6.可能的话,从包中删除一个具体对象的全部出现 7.从包中删除所有的对象 8.统计包中的某个对象的个数 9.测试包中是否含有某个对象 10.查看包中的所有对象 1.2说明一个包 可以使用UML来描述一个包类: 包的规格说明(Specification) 抽象数据类型:Bag 数据 有限个对象,不需要唯一,无序,且有相同的数据类型 这个集合中的对象个数 操作 伪代码 UML 描述 getCurrentSize() +getCurrentSize(): integer 任务:报告包中当前的对象个数 输入:无 输出:包中当前对象的个数 isEmpty() +isEmpty(): boolean 任务:查看包是否为空 输入:无 输出:根据包是否为空返回真或假 add(newEntry) +add(newEntry: T): boolean 任务:将给定对象添加到包中 输入:newEntry是一个对象 输出:根据添加是否成功返回真或假 remove() +remove(): T 任务:从包中删除未指定的项,如果可能的话… Continue Reading 01数据结构与抽象 包(bag)

放假前在图书馆淘了本好书数据结构与抽象:Java语言描述(原书第4版),现在看的差不多了,近期将根据本书的内容做相应的分享。 我打算分为12篇博文来分享整本书的内容,这本书所讲的是数据结构的Java实现,从最简单的包结构开始讲起。书中先举出日常生活中常见的列子,再将这些例子抽象出来,形成数据结构,然后进一步使用软件工程的方法,分析对应的ADT所需的功能,写出对应ADT的规格说明。之后根据规格说明选出先要实现的一组核心方法,先实现这些核心方法,再做相应测试,之后再实现更多的方法。本书内容细致,举例清晰明了,是一本很好的用来巩固数据结构和Java编程语言的书。 下面列出将要分享的博文,及博文中的主要内容: 文章标题为红色说明该文章还未开始写,文章标题为绿色说明该文章正在写,文章标题为蓝色说明该文章已写完 全部代码托管在github上https://github.com/Young2018/DSA 1.包(Bag) 包的说明 包的顺序实现 包的链式实现 2.算法分析(Algorithm analysis) 引例说明优化算法的必要性 评估算法效率的方法 评估算法效率举例 3.栈(Stack) 栈的说明 栈顶链式实现 栈的顺序实现 使用java.util.Vector实现栈 4.递归(Recursive) 递归说明 递归处理数组 递归处理链表 递归方法的时间效率分析 递归问题举例 尾递归 简介递归 使用栈来代替递归 5.排序(Sorting) 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 基数排序 排序算法分析 6.队列(Queue)、双端队列和优先队列 队列、双端队列和有限队列的说明 队列、双端队列和有限队列的实现 7.线性表(List) 线性表的说明 线性表的顺序实现 线性表的链式实现 8.查找(Searching) 无序数组的查找 有序数组的查找 无序链的查找 有序链的查找 9.字典(Dictionary)及散列(Hash)… Continue Reading 数据结构与抽象学习记录汇总