堆排序基本介绍 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。 堆是具有以下性质的完全二叉树： 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。 一般升序采用大顶堆，降序采用小顶堆。 基本思想 将待排序序列构造成一个大顶堆，此时整个序列的最大值就是堆顶的根节点arr[0]。 将其与末尾元素进行交换，此时末尾就为最大值。 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。 反复执行，便能得到一个有序序列了。 思路要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。 我们从最后一个非叶子结点开始（最后一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左子节点至右子节点，从子节点至父节点进行调整，让元素大的成为父节点。 2.找到第二 ...

树树（Tree）是n(n>=0)个结点的有限集。n=0时称为空树。 在任意一颗非空树中： (1)有且仅有一个特定的称为根（Root）的结点。 (2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、…..、Tm,其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。 树的常用术语 名称 含义 节点 树中的数据元素 树的度 树内各节点的度的最大值 节点的度 节点拥有的子树的数目称为度，记作d(v) 叶子节点 节点的度数为0，称为叶子节点leaf、终端节点、末端节点 分支节点 节点度数不为0，称为非终端节点或分支节点 分支 节点之间的关系 内部节点 除根节点外的分支节点，当然也不包括叶子节点 孩子节点 节点的子树的根节点成为该节点的孩子 双亲节点 父节点，即该节点的前驱 兄弟节点 具有相同双亲节点的节点 祖先节点 从根节点到该节点所经分支上所有的节点。 子孙节点 节点的所有子树上的节点都成为该节点的子孙。 节点的层次 根节点为第一层，根的孩子为第二层，依次类推记作( ...

散列表介绍散列表(Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。存储位置 = f(key)，这个映射函数叫做散列函数，存放记录的数组叫做散列表。 散列技术既是一种存储方法，也是一种查找方法。散列技术最适合的求解问题是查找与给定值相等的记录。 散列冲突在理想的情况下，每一个关键码值，通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。我们时常会碰到两个关键字key1 ≠ key2，但是却有f(key1)=f(key2)，这种现象我们称为冲突(collision)，并把key1和key2称为这个散列函数的同义词(synonym)。 散列函数的构造方法好的散列函数满足两个原则：1.计算简单 2.散列地址分布均匀 如果关键字是字符串如何处理？其实无论是英文字符，还是中文字符，也包括各种各样的符号，它们都可以转化为某种数字来对待，比如ASClI码或者Unicode码等，因此也就可以使用下面的这些方法。 总之，现实中，应该视不同的情况采用不同的散列 ...

斐波那契数列斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）。 黄金分割是指将整体一分为二，较大部分与整体部分的比值等于较小部分与较大部分的比值，其比值约为0.618。这个比例被公认为是最能引起美感的比例，因此被称为黄金分割。 斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618。 斐波那契查找斐波那契查找算法类似于二分查找，也需要记录是有序的，仅改变了中间结点（mid）的位置。 思路 在斐波那契数列中找一个数F[k]，使 F[k]-1 恰好大于或等于 顺序表的长度n。 若顺序表长度n小于这个F[k]-1，则将原顺序表的长度n扩展为 F[k]-1，并向其扩展后尾部的空缺值填充原顺序表中最后一个 ...

线性查找介绍线性查找（Sequential Search）又叫顺序查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。 代码1234567891011121314151617181920212223package com.nanzx.search;public class SeqSearch { public static void main(String[] args) { int arr[] = { 1, 9, 11, -1, 34, 89 }; int index = seqSearch(arr, -11); if (index == -1) { System.out.println("没有找到。"); } else { System.out.println(& ...

基数排序介绍 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法。 基数排序(Radix Sort)是桶排序的扩展。 基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。 基本思想首先定义10个“桶”，下标为0~9；然后遍历数组，按照元素的“个位”数值，依次放入对应下标的桶中，放完所有元素后，从第0个桶开始遍历，依次取出桶中元素按顺序放入原始数组中；同理，之后再遍历数组，按照元素的“十位”数值，做上一步相同的操作；以此类推，直到按照数组中最大元素的最高位操作完为止。 思路 代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535 ...

归并排序基本思想归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。 思路 分阶段可以理解为就是递归拆分子序列的过程。 再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤： 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061package com.nanzx.sort;import java.util.Arrays;public class MergeSort { public static void main(S ...

快速排序快速排序（Quicksort）是对冒泡排序的一种改进。 基本思想1．先从数列中取出一个数作为基准数。 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。 思路快速排序的进一步说明：挖坑填数+分治法 以一个数组作为示例，取区间第一个数为基准数。(基准数可以为数组内的任意元素，一般取首、尾或中间的元素) 0 1 2 3 4 5 6 7 8 9 72 6 57 88 60 42 83 73 48 85 初始时，i = 0; j = 9; temp = arr[i] = 72 由于已经将arr[0]中的数保存到temp这个临时变量中，可以理解成在数组arr[0]上挖了个坑，可以将其它数据填充到这来。 从 j 开始向前找一个比temp小或等于temp的数。当 j =8 时，符合条件，将arr[8]挖出再填到上一个坑arr[0]中。arr[0]=arr[8]; 这样一个坑arr[0]就被搞定了，但又形成了一个新坑arr[8]，这怎么 ...

希尔排序直接插入排序的效率在某些时候是很高的，比如，记录本身就是基本有序的，我们只需要少量的插入操作，就可以完成整个记录集的排序工作，此时直接插入很高效。还有就是记录数比较少时，直接插入的优势也比较明显。可问题在于两个条件本身就过于苛刻，现实中记录少或者基本有序都属于特殊情况。 希尔排序是直接插入排序经过改进之后的一个更高效的版本。 基本思想希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。 思路 代码实现123456789101112131415161718192021222324252627package com.nanzx.sort;import java.util.Arrays;public class ShellSort { public static void main(String[] args) { int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 }; shellS ...