黄皖's Blog

桶排序介绍桶排序就是把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。 之后每个桶里面的数据就是有序的了，我们在进行合并汇总。 为方便理解我还准备了图片： 实现原理为了让大家更好的对桶排序理解，下面形象生动的画出几个桶，其实过程并不复杂，大家可以看到图中分为几个桶，然后在桶里面进行排序，这样子就快了许多，然后合并就是了。 实现代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778package fg;import java.util.ArrayList;import java.util.Collection;import java.util.Collections;import java.util.Linke ...

堆排序介绍堆排序：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构。并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子 堆结构该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是： 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 特点堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。 过程描述堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然 ...

前言我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。 从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。 为方便理解我还准备了动图： 实现代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677package fg;public class QuickSort{ private static int count; /** * 快速排序 * * @param num 排序的数组 ...

将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。 还可以通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 ….. 直到全部小的数组合并起来。 为方便理解我还准备了动图： 实现过程： 实现代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647package fg;class Main { public static void main(String[] args) { int[] arr = {49,38,65,97,76,13,27}; int[] tmp = new int[arr.length]; //新建一个临时数组存放 ...

希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。 希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。 希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。 为方便理解我还准备了图片： 实现代码：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253package fg;public class ShellSort { public s ...

冒泡排序介绍冒泡排序就是把把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置…. 我们对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样一趟比较交换下来之后，排在最右的元素就会是最大的数。 除去最右的元素，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。 为方便理解我还准备了动图：性质：1、时间复杂度：O(n2) 2、空间复杂度：O(1) 3、稳定排序 4、原地排序 实现代码：123456789101112131415161718192021222324252627282930package fg;class bubbleSort { private static bubbleSort TestSort; public static void bubbleSort(int[] arrary){ //从第一个元素开始，向后依次成对比较，逆序则交换。 //对所有的元素都进行这一操作 。 for(in ...

前言：​ 我们在玩打牌的时候，你是怎么整理那些牌的呢？一种简单的方法就是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。当我们给无序数组做排序的时候，为了要插入元素，我们需要腾出空间，将其余所有元素在插入之前都向右移动一位，这种算法我们称之为插入排序。 过程描述：1、从数组第2个元素开始抽取元素。 2、把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。 3、继续选取第3，4，…n个元素,重复步骤 2 ，选择适当的位置插入。 动图： 实现代码：1234567891011121314151617181920212223242526272829303132333435package fg;import java.util.Arrays;public class InsertSort{ public static void insertSort (int[] arr) { int j = 0; int temp = 0; ...

测试分类：1.黑盒测试：不需要写代码，给出输入值，看程序能否输出期望值。 2.白盒测试：需要写代码，关注程序具体执行流程。 Junit使用：白盒测试废话不多说，直接附上代码： 12345678910111213141516package itcast;/** * 计算器类 */public class Calculator{ //加法 public int add(int a,int b){ // int i=3/0; return a+b; } //减法 public int sub(int a,int b){ return a-b; }} 当然我们也可以使用创建对象来看，但是就不知道是否是执行正确的，并且一个主方法只可以运行一个，就很麻烦，因此我们就用单元测试。 123456789101112131415package itcast;import java.util.Calendar;public class CalculatorTest&# ...

Java集合框架（一）：大纲 Java集合框架（二）：整体概览 Java集合框架（三）：Collection 源码分析 Java集合框架（四）：Iterator 源码分析 Java集合框架（五）：ListIterator 源码分析 JavaJava集合框架（六）：Set 源码分析 Java集合框架（七）：SortedSet 源码分析 Java集合框架（八）：List 源码分析 Java集合框架（九）：Queue 源码分析 Java集合框架（十）：Deque 源码分析 Java集合框架（十一）：Map 源码分析 Java集合框架（十二）：SortedMap 源码分析 Java集合框架（十三）：HashSet 源码分析 Java集合框架（十四）：LinkedHashSet 源码分析 Java集合框架（十五）：TreeSet 源码分析 Java集合框架（十六）：ArrayList 源码分析 Java集合框架（十七）：LinkedList 源码分析 Java集合框架（十八）：HashMap 源码分析 Java集合框架（十九）：LinkedHashMap 源码分析 Java集合框架（二十）：Tr ...

1、HashTable 简介和 HashMap 一样，Hashtable 也是一个散列表。从Java 1.2开始，这个类被改进以实现Map接口，使其成为Java Collections Framework的成员。 与新的集合实现不同，Hashtable是同步的。 如果不需要线程安全实现，建议使用HashMap代替Hashtable。 如果需要线程安全的高度并发实现，那么建议使用ConcurrentHashMap代替Hashtable。 该类实现了一个哈希表，它将键映射到值。 任何非null对象都可以用作键或值。要成功存储和检索哈希表中的对象，用作键的对象必须实现hashCode方法和equals方法。 通常，默认负载系数（0.75）在时间和空间成本之间提供了良好的折衷。 较高的值会减少空间开销，但会增加查找条目的时间成本（这反映在大多数Hashtable操作中，包括get和put）。 初始容量控制了浪费空间和重新运算操作的需要之间的权衡，这是非常耗时的。 如果初始容量大于Hashtable将包含的最大条目数除以其加载因子，则不会发生重复操作。 但是，将初始容量设置得太高会浪费空间。 如 ...