希尔排序
排序原理：
选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
对分好组的每一组数据完成插入排序；
减小增长量，最小减为1，重复第二步操作；
代码实现：
import java.util.Arrays; public class ShellSort { public static void main(String[] args) { int[] a=new int[]{5,2,4,35,13,1,8,6,32,7,543}; System.out.println(Arrays.toString(a)); sort(a); System.out.println(Arrays.toString(a)); } public static void sort(int[] a) { for(int gap=a.length/2;gap>0;gap/=2) { for(int i=gap;i<a.length;i++) { for(int j=i;j-gap>=0;j--) { if(a[j-gap]>a[j]) { int temp=a[j-gap]; a[j-gap]=a[j]; a[j]=temp; } else break; } } } } }
时间复杂度分析：
在希尔排序中，增长量 h并没有固定的规则，有很多论文研究了各种不同的递增序列，但都无法证明某个序列是最好的，因此对于希尔排序不做时间复杂度分析
归并排序
排序原理：
1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止；
2.将相邻的两个子组进行合并成一个有序的大组；
3.不断的重复步骤2，直到最终只有一个组为止；
归并原理：
代码实现：
import java.util.Arrays; public class MergeSort1 { public static void main(String[] args) { int[] a=new int[]{50,23,88,35,65,53,90,13,52,42,16,18,73,25,77,66}; System.out.println(Arrays.toString(a)); sort(a,0,a.length-1); System.out.println(Arrays.toString(a)); } public static void sort(int[] a,int l,int r) { if(l==r) return; int mid=(l+r)/2; sort(a,l,mid); sort(a,mid+1,r); int[] temp=new int[r-l+1]; int i=0; int s1=l; int s2=mid+1; while(s1<=mid && s2<=r) { if(a[s1]<a[s2]) { temp[i]=a[s1]; s1++; i++; }else { temp[i]=a[s2]; s2++; i++; } } while(s1<=mid) { temp[i]=a[s1]; s1++; i++; } while(s2<=r) { temp[i]=a[s2]; s2++; i++; } for(int i1=0;i1<temp.length;i1++) { a[l+i1]=temp[i1]; } } }
时间复杂度分析：
用树状图来描述归并，如果一个数组有 8 个元素，那么它将每次除以 2 找最小的子数组，共拆 log8 次，值为 3，所以树共有 3 层 , 那么自顶向下第 k 层有 2^k 个子数组，每个数组的长度为 2^(3-k) ，归并最多需要 2^(3-k)次比较。因此每层的比较次数为 2^k * 2^(3-k)=2^3, 那么 3 层总共为 3*2^3 。
假设元素的个数为 n ，那么使用归并排序拆分的次数为 log2(n), 所以共 log2(n) 层，那么使用 log2(n) 替换上面 3*2^3中的 3 这个层数，最终得出的归并排序的时间复杂度为： log2(n)*2^(log2(n))=log2(n)*n, 根据大 O推导法则，忽略底数，最终归并排序的时间复杂度为 O(nlogn);
线性表
线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。基于线性表，又可以实现栈和队列。
顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中再逻辑结构上响铃的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
顺序表的查找效率很高，根据索引可以直接定位，查找的时间复杂度为O(1)，但是插入和删除的时候需要移动其他的元素，所以效率较低，比如，在位置i处插入，需要把i位置后面的元素依次向右移动一次，因此插入和删除的时间复杂度为O(n)。
由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作，需要更换新的更大的数组，把数据从就旧的数组中拷贝到新的数组中，这个过程比较耗时
Java中ArrayList集合的底层也是一种顺序表，使用数组实现，同样提供了增删改查以及扩容等功能。
链表
链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。
在使用链表的时候，需要先创建一个节点类
public class Node<T> { //存储元素 public T item; //指向下一个结点 public Node next; public Node(T item, Node next) { this.item = item; this.next = next; } }
生成链表：
public static void main(String[] args) throws Exception { //构建结点 Node<Integer> first = new Node<Integer>(11, null); Node<Integer> second = new Node<Integer>(13, null); Node<Integer> third = new Node<Integer>(12, null); Node<Integer> fourth = new Node<Integer>(8, null); Node<Integer> fifth = new Node<Integer>(9, null); //生成链表 first.next = second; second.next = third; third.next = fourth; fourth.next = fifth; }
栈
栈是一种基于先进后出 (FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）
我们称数据进入到栈的动作为 压栈 ，数据从栈中出去的动作为 弹栈 。
既可以使用顺序表实现栈，也可以用链表实现栈
使用数组，实现一个简单的不可扩容的栈：
public class stackDemo<m> { m[] a; int f=-1; public stackDemo(int num) { a=(m[])new Object[num]; } public void add(m n) { if(f==a.length-1) { System.out.println("栈满"); return; } f++; a[f]=n; } public m get() { if(f==-1) { System.out.println("栈空！"); return null; } m temp=a[f]; f--; return temp; } public static void main(String[] args) { stackDemo s=new stackDemo(5); String[] str=new String[] {"123","g","e","g","w","f","h","r"}; for(int i=0;i<7;i++) s.add(str[i]); for(int i=0;i<7;i++) System.out.println(s.get()); } }
队列
队列是一种基于先进先出 (FIFO) 的数据结构，是一种只能在一端进行插入 ,在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先被读出来。
同样的，既可以使用顺序表实现队列，也可以用链表实现队列
public class columnDemo <m>{ m[] a; int b=0; int e=0; public columnDemo(int num) { a=(m[])new Object[num]; } public void add(m value) { if(e==a.length) { System.out.println("队列已满！"); return; } a[e]=value; e++; } public m get() { if(b==e) { System.out.println("队空！"); return null; } int n=b; b++; return a[n%a.length]; } public static void main(String[] args) { columnDemo c=new columnDemo(5); String[] str=new String[] {"123","g","e","g","w","f","h","r"}; for(int i=0;i<7;i++) c.add(str[i]); for(int i=0;i<7;i++) System.out.println(c.get()); } }
