Java学习之算法

[TOC]

十大排序算法

冒泡排序

比较相邻元素，如果前一个比后一个大，则交换他们

冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但是这种改进对于提升性能没有太大作用

选择排序

在未排序的序列中找到最小的元素，存放到起始位置。再找其余最小的排到已排序列的末尾，直到所有元素都排序完毕；

唯一好处就是不占额外空间了吧

插入排序

把第一个排列元素看作有序序列，第二个往后是未排列序列；

从头到尾扫描未排列序列，将扫描到的元素插入到有序序列的适当位置（相同时，插入到相等元素的后边）

有一种优化算法–折半插入

希尔排序

希尔排序又称递减增量排序算法，是非稳定排序算法

public static int[] shell_demo2(int[] list){//希尔排序
    int skip=list.length/2;
    do {
        for (int i = skip; i < list.length; i++) {
            //System.out.printf("每%d轮的i:%d值\n",skip,i);
            int j = i - skip;int temp=list[i];
               for (;j >=0&&temp<list[j]; j -= skip) {
                list[i] = list[j];
            }
            list[j+skip] = temp;
        }
        skip /= 2;
    } while (skip > 0);
    return list;
}

归并排序

public static int[] sort(int[] a,int low,int high){
    int mid = (low+high)/2;
    if(low<high){
        sort(a,low,mid);
        sort(a,mid+1,high);
        //左右归并
        merge(a,low,mid,high);
    }
    return a;
}

public static void merge(int[] a, int low, int mid, int high) {
    int[] temp = new int[high-low+1];
    int i= low;
    int j = mid+1;
    int k=0;
    // 把较小的数先移到新数组中
    while(i<=mid && j<=high){
        if(a[i]<a[j]){
            temp[k++] = a[i++];
        }else{
            temp[k++] = a[j++];
        }
    }
    // 把左边剩余的数移入数组
    while(i<=mid){
        temp[k++] = a[i++];
    }
    // 把右边边剩余的数移入数组
    while(j<=high){
        temp[k++] = a[j++];
    }
    // 把新数组中的数覆盖nums数组
    for(int x=0;x<temp.length;x++){
        a[x+low] = temp[x];
    }
}

快速排序

快速排序时间复杂度：

最好的时间复杂度和平均时间复杂度就是O(nlogn);

正常情况下是递归log₂n次，每次遍历的最坏时间复杂度是n，所以平均时间复杂度是O(nlogn)；

最好的时间复杂度就是每次都划分的很均匀；时间复杂度就是O(nlogn)；

最坏的时间复杂度是O(n^2),这种情况就是原先的数据就是排序好，这样每次只能位移一个数据， 每次划分的子序列只比上一次划分少一个记录，注意两一个为空。

从数列中挑出一个元素，作为基准；重新排列数列，所有比基准小的摆放在基准前面，所有比基准大的元素摆到基准后边（相同的数字可以放在任意一边）；递归的把小于基准值元素的子序列和大于基准元素的字序列进行排序

public static int[] quick_sort(int arr[], int left, int right) {//quick_sort(list, 0, list.length - 1)
    if (left < right) {
        int partitionindex = partition(arr, left, right);
        quick_sort(arr, left, partitionindex - 1);
        quick_sort(arr, partitionindex + 1, right);
    }
    return arr;
}

public static int partition(int[] arr, int left, int right) {
    int index = left + 1;
    for (int i = index; i <= right; i++) {
        if (arr[i] < arr[left]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, left, index - 1);
    return index - 1;
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

随机化快速排序

就是在设置基准值的时候不采用最左边的那个数作为基准值，而是采用一个随机数列取一个随机的索引跟最左边的进行交换，然后进行排序

双路快速排序

就是两边都设置索引值，把比基准值小的i+1并进行交换，比基准值大的j-1,然后进行i和j上的值进行交换，之后i+1，j-1；然后进行下一轮，直到i>j时候暂停，这时候就说明全部都已经比较过一次了；

三路排序算法

是二路快速排序的进一步改进版本，将值分为三部分，小于V，等于V，大于V，V是标定值；三路快速排序，对处理大量重复元素的数组非常有效，提高了快速排序的过程

public static void sort(int[] arr,int l,int r){
    if(l>r){
        return;
    }
    int refer=arr[l];
    int lt=l;
    int gt=r+1;
    int i=l+1;
    while(i<gt){
        if(arr[i]<refer){
            swap(arr,i,lt+1);
            i++;
            lt++;
        }
        else if(arr[i]>refer){
            swap(arr,i,gt-1);
            gt--;
        }
        else{
            i++;
        }
    }
    //交换标准值
    System.out.println(i+"||"+lt+"||"+gt);
    swap(arr,l,lt);
    sort(arr,0,lt-1);
    sort(arr,gt,r);
}
public static void swap(int[] arr ,int i,int j){
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}

堆排序

先构造根据要求序列构造相应的大堆或者小堆，然后把堆顶元素和最后一个元素进行互换，得到最大值或者最小值，然后对其他在进行大堆或者小堆排序，重复操作，直到把所有元素都排序完成

public static int[]  duisort(int[] sourceArray){
    int[] arr= Arrays.copyOf(sourceArray,sourceArray.length);
    buildMaxheap(arr);
    int len=arr.length;
    for (int i=len-1;i>0;i--){
        swap(arr,0,i);
        len--;
        handif(arr,0,len);
    }
    return arr;
}
public static void buildMaxheap(int[] arr){
    for (int i=(arr.length/2);i>=0;i--){
        handif(arr,i,arr.length);
    }
}
public static void handif(int[] arr,int i,int len){
    int left=2*i+1;
    int right=2*(i+1);
    int largest=i;
    if(left<len&&arr[left]>arr[largest]){
        largest=left;
    }
    if(right<len&&arr[right]>arr[largest]){
        largest=right;
    }
    if(largest!=i){
        swap(arr,i,largest);
        handif(arr,largest,len);//对分支内的所有序列进行排序
    }
}
public static void swap(int[] arr,int i ,int j){
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}

计数排序

创建一个数列，数列的长度就是所给数组中的最大值，遍历所给数组arr，新数列中对应的序号的内容加一，遍历新创数组，可以得到对应的数列

public static int[] jishu(int[] arr) {
    int max = getMaxValue(arr);

    int[] result = new int[arr.length];
    int[] arr_num = new int[max];
    Arrays.fill(arr_num, 0);
    for (int item : arr) {
        arr_num[item - 1] += 1;
        //System.out.println(Arrays.toString(arr_num));
    }
    int hassortindex = 0;
    for (int i = 0; i < max; i++) {
        if (arr_num[i] > 0) {
            for (int j = arr_num[i]; j > 0; j--) {
                result[hassortindex] = i + 1;
                hassortindex++;
            }
        }
    }
    return result;
}

public static int getMaxValue(int[] arr) {
    int Max = 0;
    for (int item : arr) {
        if (item > Max) {
            Max = item;
        }
    }
    return Max;
}

桶排序

什么时候最快：输入的数据可以均匀分配到每一个桶中；

什么时候最慢：当输入的数据被分配到同一个桶中；

利用多维数组，每一行作为一个桶的概念，每一个桶的大小是可以自己定的

public static int[] tong_sort(int[] list,int bucketSize){//tong_sort(list,5)
    int[] arr= Arrays.copyOf(list,list.length);
    int maxValue=arr[0];
    int minValue=arr[0];
    for(int item :arr){
        if(item>maxValue)maxValue=item;
        else if(item<minValue)minValue=item;
    }
    int bucketCount=(int)Math.ceil((double)(maxValue-minValue)/bucketSize);
    System.out.println("桶的数量是"+bucketCount);
    int[][] buckets=new int[bucketCount][0];
    for (int item :arr){
        int index=(item-minValue)/bucketSize;
        buckets[index]=arrAppend(buckets[index],item);
    }
    int arrindex=0;
    for (int[] bucket:buckets){
        if(bucket.length==0){
            continue;
        }
        demo_quick.quick_sort(bucket, 0, bucket.length - 1);//使用快排对每一个桶内元素进行排序
        for (int value:bucket){
            arr[arrindex]=value;
            arrindex++;
        }
    }
    return arr;
}
public static int[] arrAppend(int[] arr ,int value){
    arr=Arrays.copyOf(arr,arr.length+1);
    arr[arr.length-1]=value;
    return arr;
}

基数排序

基数排序：根据键值的每一位数字来分配桶；

计数排序：每个桶只存储单一数值；

桶排序：每一个桶存储一定范围的数值；

public static void main(String[] args) {
    int[] list= new int[]{42, 20, 17, 13, 28, 14, 23, 15};
    System.out.println(Arrays.toString(radixSort(list)));//假定全部都是正整数的二位数，主要是为了了解算法实现
}
public static int[] radixSort(int [] arr){
    int[][] arr_num=new int[10][0];
    for (int j : arr) {
        arr_num[j % 10] = arrAdd(arr_num[j % 10], j);
    }
    int index=0;
    for(int i=0;i<10;i++){
        for(int item :arr_num[i]){
            if(item!=0){
                arr[index]=item;
                index++;
            }
        }
    }
    /System.out.println("中间的数列："+Arrays.toString(arr));
    for (int i=0;i<10;i++)
        Arrays.fill(arr_num[i],0);
    for (int i=0;i<arr.length;i++){
        arr_num[arr[i]/10]=arrAdd(arr_num[arr[i]/10],arr[i]);
    }
    index=0;
    for(int i=0;i<10;i++){
        for(int item :arr_num[i]){
            if(item!=0){
                arr[index]=item;
                index++;
            }
        }
    }
    return arr;
}
public static int getBucketCount(int min,int max){
    int count=0;
    return count;
}
public static void swap(int[] arr,int i,int j){
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}
public static int[] arrAdd(int[] list,int value){
    int[] arr=Arrays.copyOf(list, list.length+1);
    arr[list.length]=value;
    return arr;
}

排序算法的衍生问题

归并排序和快速排序，都使用了分治算法；分治算法就是将原来的问题分割成同等结构的问题，之后将子问题逐个解决，原问题也就得到了解决

查找算法

顺序查找

顺序遍历查找

折半查找（二分查找）

说明：元素必须是有序的，如果是无序的则要先进行排序操作

复杂度分析 ：最坏情况下log₂(n+1);期望时间复杂度O(log₂n) ;;(测试 log2n)

下代码是查找小于等于t的最接近的值，若要查找t,则需要将5-8拆成两个if ,else if

public int BinarySearch(T[] nums,T t){
    int left=0;int right=nums.length;int ans=0;
    while(left<=right){
        int mid=(left+right)>>1;
        if(t.compareTo(nums[mid])<=0){
            ans=mid;
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    return ans;
}

插值查找

复杂度分析：查找成功或者失败的时间复杂度均为O(log₂(log₂n))。

public  int interpolationSearch(int[] nums,int key){
    int low=0;int height=nums.length-1;int ans=-1;
    while(low<height){
        int mid=low+(int)((float)(key-nums[low])/(nums[height]-nums[low])*(height-low));
        if(nums[mid]==key)return mid;
        if(nums[mid]>key)height=mid-1;
        if(nums[mid]<key)low=mid+1;
    }
    return ans;
}

斐波那契查找

是二分查找的一种提升算法，通过运用黄金比例的概念再数列中进行选点进行查找，提高查找效率。同样的斐波那契查找也属于一种有序的查找算法。要求表中记录的个数为某个斐波那契数-1 即length=F(k)-1

public int fibonacciSearch(T[] nums,T t){
    int ans=-1,left=0,right=nums.length-1;
    List<Integer> indexes=buildFibonacci(nums.length);
    int k=indexes.size()-1;
    if(indexes.size()==0){
        System.out.println("您输入的字符串有误");
        return -2;
    }
    while(left<=right){
        int mid=left+indexes.get(k)-1;
        if(nums[mid].compareTo(t)<0){left=mid+1;k-=2;}
        else if(nums[mid].compareTo(t)>0){right=mid-1;k-=1;}
        else{ ans=mid;break;}
    }
    return ans;
}
public List<Integer> buildFibonacci(int num){
    List<Integer> fibo=new ArrayList<>();
    fibo.add(1);
    fibo.add(1);
    Integer add_num=0;
    for(int i=2;add_num<num;i++){
        add_num=fibo.get(i-1)+fibo.get(i-2);
        fibo.add(add_num);
    }
    if(add_num!=num)return new ArrayList<>();
    return fibo;
}

树表查询

二叉排序树的建立以及二叉排序树的搜索

private class Node{
    private Key key;
    private Node left,right;
    public Node(Key key){
        this.key=key;
        left=right=null;
    }
}
private Node root;//根节点
private int count;//树中的节点个数
public Demo_Deep(){
    root=null;
    count=0;
}
public int size(){
    return count;
}
public boolean isEmpty(){
    return count==0;
}
public boolean search(Key key){
    return search(root,key);
}
private boolean search(Node node,Key key){
    boolean flag=false;
    if(node==null){
        return false;
    }
    if(node.key.compareTo(key)==0){
        System.out.println(node.key);
        return true;
    }else if (node.key.compareTo(key)>0){
        return search(node.left,key);
    }else
        return search(node.right,key);
}

public void insert(Key key){
    root=insert(root,key);
}
private Node insert(Node node, Key key){
    if(node==null){
        count++;
        return new Node(key);
    }
    if (key.compareTo(node.key)<0){
        node.left=insert(node.left,key);
    }else{
        node.right=insert(node.right,key);
    }
    return node;
}

分块查询

哈希表查找

链表

单向链表

单向链表的创建

public class DemoLinkedList<T> implements Iterable<T>{
    private Node head;
    private int N;
    private class Node{
        T item;
        Node next;
        public Node(T item,Node next){
            this.item=item;
            this.next=next;
        }
    }
    public DemoLinkedList(){
        this.head=new Node(null,null);
        this.N=0;
    }

    //清空链表
    public void clear(){//设置头结点的下一个结点为空，把链表的长度归为0
        head.next=null;
        this.N=0;
    }


    //返回链表的长度
    public int length(){
        return N;
    }

    //是否为空
    public boolean isEmpty(){
        return N==0;
    }
    //获取指定位置i处的元素
    public T get(int i){
        Node node=head.next;
        for(int j=0;j<i;j++){
            node=node.next;
        }
        return node.item;
    }
    //添加指定的元素
    public void  insert(T t) {
        Node n=head;
        while(n.next!=null){
            n=n.next;
        }
        //创建新节点,让最后一个结点指向新结点
        n.next=new Node(t,null);
        //链表长度加一
        N++;
    }
    //添加指定的一个元素,再线性表的第i个元素之前插入一个值为t的数据元素
    public void insert(int i,T t){
        Node pre=head;
        for(int index=0;index<=i-1;index++){
            pre=pre.next;
        }
        Node curr=pre.next;
        Node newnode=new Node(t,curr);
        pre.next=newnode;
        N++;
    }
    //删除并返回线性表中的第i个数据元素
    public T remove(int i){
        Node pre=head;
        for(int index=0;index<=i-1;index++){
            pre=pre.next;
        }
        Node node=pre.next;
        pre.next=node.next;
        N--;
        return node.item;
    }
    //返回线性表中首次出现的指定的数据元素的位序号，若不存在则返回-1
    public int indexOf(T t){
        Node node=head;
        int index=0;
        while(node.next!=null){
            if(node.item==t){
                return index;
            }
            index++;
            node=node.next;
        }
        return -1;
    }

    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }
    //提供一个遍历方法
    private class LIterator implements Iterator{
        private Node n;
        public LIterator(){
            this.n=head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n=n.next;
            return n.item;
        }
    }
} 

双向链表

双向链表的实现

public class TowWayLinkList<T> implements Iterable<T>{
    private Node head;
    private Node last;
    private int N;
    public class Node{
        T data;
        Node pre;
        Node next;
        public  Node(T data,Node pre,Node next){
            this.data=data;
            this.pre=pre;
            this.next=next;

        }
    }
    public TowWayLinkList(){
        //初始化头结点和尾结点
        this.head=new Node(null,null,null);
        this.last=null;
        //初始化链表长度
        this.N=0;
    }
    public void clear(){
        this.head.next=null;
        this.head.pre=null;
        this.head.data=null;
        this.last=null;
        this.N=0;
    }
    public int length(){
        return N;
    }
    public boolean isEmpty(){
        return N==0;
    }
    public  T getFirst(){
        if(isEmpty())return null;
        return head.next.data;
    }
    public T getLast(){
        if(isEmpty()) return null;
        return last.data;
    }
    public void insert(T t){
        if(isEmpty()){//链表为空
            Node newNode  =new Node(t,head,null);
            head.next=newNode;
            last=newNode;
            last.next=last;
        }else{//链表不为空
            Node oldlast=last;
            Node newNode=new Node(t,oldlast,null);
            oldlast.next=newNode;
            last=newNode;
        }
        N++;
    }
    public void insert(int i,T t){
        Node n=head;
        for(int index=0;index<i&&index<N;index++){
            n=n.next;
        }
        Node nextNode=n.next;
        //创建新节点
        Node newNode=new Node(t,n,nextNode);
        n.next=newNode;
        nextNode.pre=newNode;
        N++;
    }
    public T get(int i){
        Node n=head.next;
        for(int index=0;index<i&&index<N;index++){
            n=n.next;
        }
        return n.data;
    }
    public int indexOf(T t){
        Node n=head;
        for(int index=0;n.next!=null;index++){
            n=n.next;
            if(n.next.equals(t)){
                return index;
            }
        }
        return -1;
    }
    public T remove(int i){
        Node p=head;
        for(int index=0;index<i;index++){
            p=p.next;
        }
        Node node=p.next;
        Node nextNode=node.next;
        p.next=nextNode;
        nextNode.pre=p;
        N--;
        return node.data;
    }

    @Override
    public Iterator<T> iterator() {//提供一个遍历方法
        return new TIterator();
    }
    private class TIterator implements Iterator{
        private Node n;
        public TIterator(){
            this.n=head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n=n.next;
            return n.data;
        }
    }
}

单链表反转

//用来反转整个链表
public void reverse(){
    //判断是否为空链表,若为空
    if(isEmpty()){
        return;
    }else{
        reverse(head.next);
    }
}
//反转指定的curr,并且把反转之后的结点
public Node reverse(Node curr){
    if(curr.next==null){
        head.next=curr;
        return curr;
    }
    //递归的调用当前结点的下一个结点，返回值就是利埃纳表反转后，当前结点的下一个结点
    Node pre=reverse(curr.next);
    //让返回的结点的下一个结点
    pre.next=curr;
    curr.next=null;
    System.out.println(curr.item+"排序完成");
    return curr;
}

快慢指针

中间值问题、单链表是否有环路、环路的入口问题

public T getMid(){
    Node fast=head.next;
    Node slow=head.next;
    while(fast!=null&&fast.next.next!=null){
        fast=fast.next.next;
        slow=slow.next;
    }
    return slow.item;
}
public boolean isCircle(){
    Node fast=head.next;
    Node slow=head.next;
    while(fast.next.next!=null&&fast!=null){
        fast=fast.next.next;
        slow=slow.next;
        if(fast.equals(slow)){
            return true;
        }
    }
    return false;
}
public T CircleInter(){
    Node fast=head.next;
    Node slow=head.next;
    Node temp=null;
    while(fast!=null&&fast.next.next==null){
        fast=fast.next.next;
        slow=slow.next;
        if(fast.equals(slow)){
            temp= head.next;
            continue;
        }
        if(temp!=null){
            temp=temp.next;
            if(temp.equals(slow)){
                break;
            }
        }
    }
    return temp.item;
}

约瑟夫问题

约瑟夫问题可以转化为一个环形链表来处理这个问题，自杀的人通过删除结点来模拟

栈

栈是一个基于先进先出的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表

栈的实现

案例

括号匹配问题

public static boolean isMatch(String str){
    int num=0;
    Demo_stack<Character> charsStack=new Demo_stack<Character>();
    int index=0;
    while(index<str.length()){
        char ch=str.charAt(index);
        charsStack.push(ch);
        index++;
    }
    for(Character ch:charsStack){
        System.out.println(ch);
    }
    for(int i=0;i<str.length();i++){
        Character ch=charsStack.pop();
        if(ch.equals(')'))num++;
        if(ch.equals('('))num--;
        if(num<0){
            return false;
        }
    }
    if(num>0)return false;
    if(num==0)return true;
    return false;
}

逆波兰表达式

就是后缀表达式的实现，一般人们都习惯于使用，中缀表达式。即a+b,逆波兰表达式用ab+表示

队列

队列的创建这次也是使用的线性表

public void enqueue(T t){//向队列中加入元素
    if(last==null){
        last=new Node(t,null);
        head.next=last;N++;
    }
    else{//当前last结点不为空
        Node oldlast=last;
        last=new Node(t,null);
        oldlast.next=last;N++;
    }

}
public T dequeue(){//从队列中取出元素

    if(isEmpty())return null;
    Node oldfirst=head.next;
    head.next=oldfirst.next;
    N--;
    if(isEmpty()){
        last=null;
    }
    return oldfirst.item;
}

堆

是一类特殊的数据结构的统称；堆可以看作一颗完全二叉树的数组对象；堆中的某个节点的之总是不大于或不小于其父节点的值；

大根堆（小根堆）的建立，大根堆（小根堆）的取出其中的元素

public class Demo_shiftDown <T extends Comparable>{
    protected T[] data;
    protected int count;
    protected int capacity;
    public Demo_shiftDown(int capacity){
        data=(T[])new Comparable[capacity+1];
        count=0;
        this.capacity=capacity;
    }
    public int size(){
        return count;
    }
    public boolean isEmpty(){
        return count==0;
    }
    public void insert(T item){
        assert count+1<capacity;
        data[count+1]=item;
        count++;
        shiftUp(count);
    }
    private void shiftUp(int k){
        while(k>1&&data[k].compareTo(data[k/2])>0){
            System.out.println(k+"子节点是"+data[k]+"父节点是"+data[k/2]+"||是否要换位置"+(data[k].compareTo(data[k/2])>0));
            swap(k,k/2);
            k/=2;
        }
    }
    public void swap(int i,int j){
        T temp=data[i];
        data[i]=data[j];
        data[j]=temp;
    }
    //这往上是大根堆（小根堆）的建立过程

    //从大堆中取出堆顶元素，即去除所存储的最大数据
    public T extractMax(){
        assert count>0;
        T ret=data[1];
        swap(1,count);
        count--;
        shiftDown(1);
        return ret;
    }
    //获取最大堆中的堆顶元素
    public T getMax(){
        assert (count>0);
        return data[1];
    }
    public void shiftDown(int k){
        while(2*k<count){
            int j=2*k;
            if(j+1<count&&data[j+1].compareTo(data[j])>0)j++;
            if(data[k].compareTo(data[j])>=0)break;
            swap(k,j);
            k=j;
        }
        System.out.println("shiftDown结束");
    }

    public static void main(String[] args) {
        Demo_shiftDown<Integer> heapShiftDown = new Demo_shiftDown<>(100);
        // 堆中元素个数
        int N = 100;
        // 堆中元素取值范围[0, M)
        int M = 100;
        for( int i = 0 ; i < N ; i ++ )
            heapShiftDown.insert( new Integer((int)(Math.random() * M)) );
        Integer[] arr = new Integer[N];
        // 将最大堆中的数据逐渐使用extractMax取出来
        // 取出来的顺序应该是按照从大到小的顺序取出来的
        for( int i = 0 ; i < N ; i ++ ){
            arr[i] = heapShiftDown.extractMax();
            System.out.print(arr[i] + " ");
        }
        // 确保arr数组是从大到小排列的
        for( int i = 1 ; i < N ; i ++ )
            assert arr[i-1] >= arr[i];
    }
}

基础堆排序

①基础堆排序，建立大根堆或者小根堆之后②最大元素跟最后一个元素换位置之后count-1,③然后从最后一个非叶子节点向上比较向左依次比较④重新建立大根堆和小根堆；重复上述②③④动作，直到堆中的元素全部取出

优化堆排序

主要是将上述的第三步，改成了比较少数，跟改变值有分支关系的就行了，例如:62和17交换位置之后，只需要给更改节点到最下边叶子节点的值就可以了，但是基础堆排序就需要遍历整个非叶子节点，重新建堆，减少了比较次数

索引堆及其优化

如果堆中存储的元素较大，那么进行交换就需要消耗大量的时间，这个时候就需要使用索引堆，堆中存储的是数组的索引，操作的也都是索引

protected T[] data;      // 最大索引堆中的数据
protected int[] indexes;    // 最大索引堆中的索引
protected int count;
protected int capacity;
// 构造函数, 构造一个空堆, 可容纳capacity个元素
public Demo_IndexHeap(int capacity){
    data = (T[])new Comparable[capacity+1];
    indexes = new int[capacity+1];
    count = 0;
    this.capacity = capacity;
}
// 返回索引堆中的元素个数
public int size(){
    return count;
}
// 返回一个布尔值, 表示索引堆中是否为空
// 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
// 传入的i对用户而言,是从0索引的
public void insert(int i, T item){
    assert count + 1 <= capacity;
    assert i + 1 >= 1 && i + 1 <= capacity;
    i += 1;
    data[i] = item;
    indexes[count+1] = i;
    count ++;
    shiftUp(count);
}

// 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据
public T extractMax(){
    assert count > 0;
    T ret = data[indexes[1]];
    swapIndexes( 1 , count );
    count --;
    shiftDown(1);
    return ret;
}
// 从最大索引堆中取出堆顶元素的索引
public int extractMaxIndex(){
    assert count > 0;
    int maxIndex = indexes[1] - 1;
    swapIndexes( 1 , count );
    count --;
    shiftDown(1);
    return maxIndex;
}
// 获取最大索引堆中的堆顶元素
public T getMax(){
    assert count > 0;
    return data[indexes[1]];
}
public void print(){
    for(int i=1;i<count+1;i++){
        System.out.println("索引列表中索引序号为"+i+"索引中对应的索引"+getMaxIndex()+"对应的值是"+extractMax());
    }
}
// 获取最大索引堆中的堆顶元素的索引
public int getMaxIndex(){
    assert count > 0;
    return indexes[1]-1;
}
private void swapIndexes(int i, int j){
    int t = indexes[i];
    indexes[i] = indexes[j];
    indexes[j] = t;
}
//k是堆的索引
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftUp(int k){
    while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){
        swapIndexes(k, k/2);
        k /= 2;
    }
}

// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftDown(int k){
    while( 2*k <= count ){
        int j = 2*k;
        if( j+1 <= count && data[indexes[j+1]].compareTo(data[indexes[j]]) > 0 )
            j ++;
        if( data[indexes[k]].compareTo(data[indexes[j]]) >= 0 )
            break;
        swapIndexes(k, j);
        k = j;
    }
}

// 测试 IndexMaxHeap
public static void main(String[] args) {

    int N = 1000;
    Demo_IndexHeap<Integer> indexMaxHeap = new Demo_IndexHeap<>(N);
    for( int i = 0 ; i < N ; i ++ )
        indexMaxHeap.insert( i , (int)(Math.random()*N) );
    System.out.println(indexMaxHeap.getMax());
    System.out.println("最大值的索引"+indexMaxHeap.getMaxIndex());
    indexMaxHeap.print();
}

树

二分搜索树

若它的左子树不为空，左子树上所有的节点都小于他的根节点

若他的右子树不为空，右子树上所有的节点都小于它的根节点

public class Demo_insert<Key extends Comparable<Key>,Value> { 
	private class Node{
        private Key key;
        private Node left,right;
        public Node(Key key){
            this.key=key;
            left=right=null;
        }
    }
    private Node root;//根节点
    private int count;//树中的节点个数
    public Demo_insert(){
        root=null;
        count=0;
    }
    public int size(){
        return count;
    }
    public boolean isEmpty(){
        return count==0;
    }
}

二分搜索树的插入

public void insert(Key key){
    root=insert(root,key);
}
private Node insert(Node node,Key key){
    if(node==null){
        count++;
        return new Node(key);
    }
    if (key.compareTo(node.key)<=0){
        node.left=insert(node.left,key);
    }else{
        node.right=insert(node.left,key);
    }
    return node;
}

二分搜索树节点的搜索

public boolean search(Key key){
    return search(root,key);
}
private boolean search(Node node,Key key){
    boolean flag=false;
    if(node==null){
        return false;
    }
    if(node.key.compareTo(key)==0){
        System.out.println(node.key);
        return true;
    }else if (node.key.compareTo(key)>0){
        return search(node.left,key);
    }else
        return search(node.right,key);
}

二分搜索树深度优先遍历

private void preOrder(Node node){//前序遍历，先遍历根节点，在遍历左节点，在遍历右节点
    if(node==null){
        return;
    }
    System.out.println(node.key+"  ");
    preOrder(node.left);
    preOrder(node.right);
}

private void inOrder(Node node){//中序遍历，先左节点，再根节点，再右节点
    if(node==null){
        return;
    }
    inOrder(node.left);
    System.out.println(node.key);
    inOrder(node.right);
}

private void postOrder(Node node){//后序遍历，先左子节点，再右节点，最后根节点
    if(node==null){
        return ;
    }
    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.key);
}

二分搜索树层级遍历

private void LevelOrder(){
    LinkedList<Node> q=new LinkedList<Node>();
    q.add(root);
    while(!q.isEmpty()){
        Node node=q.remove();
        System.out.println(node.key);
        if(node.left!=null){
            q.add(node.left);
        }
        if(node.right!=null){
            q.add(node.right);
        }
    }
}

二分搜索树节点删除

删除二分搜索树的最大或最小结点

①找到最大或者最小结点：遍历左子树或者右子树

②如果最小结点没有右子树，直接删除；如果最小结点有右子树，

private Node removeMin(Node node){
    if(node.left==null){
        Node rightNode=node.right;
        node.right=null;
        count--;
        return rightNode;
    }
    Node.left=removeMin(node.left);
    return node;
}

红黑树

红黑树的定义

​ 1、红链接均为左连接；
​ 2、没有任何一个结点同时为两条红链接相连
​ 3、该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同
红黑树是基于2-3树进行定义的
红黑树的树结点API设计

红黑树的平衡化

​ 红黑树的左旋
​ 使用范围：红色链接出现在右节点

​ 红黑树的右旋
​ 连续两个链接是红色链接

红黑树的插入

#### 向单个2-结点中拆入新键

​ ①当新键小于当前结点的键，我们只需要新增一个红色链接即可
​ ②当新键大于当前结点的键，那么需要新建一个红色的右链接，这时候就需要通过左旋，把红色链接变成左链接，操作才算完成

#### 向底部2-结点插入新键

​ 直接红色链接进行链接，如果出现红色结点在右侧，那么要进行左旋，之后要保证符合红黑树定义
#### 颜色反转
​ 当一个结点的左子节点和右子节点的color都是红色的时候，也就是出现了临时的4-结点
​ 这时候只需要把左子节点和右子节点的color变成黑色，同时让当前结点的颜色变成红色

向一个双键树（即一个3-结点）中插入新建

​ 这种情况又分为三种子情况
​ ①大于原树当中的两个结点
​ 插入新键，用红键进行链接，之后就会发现出现了一个结点的两个结点都是红色链接的，这时候就需要进行颜色反转
​ ②小于元素当中的两个结点
​ 插入新键，用红键进行链接，之后就会发现出现了连续两个链接都是红色的链接，这时候就需要进行右旋，之后进行颜色反转
​ ③介于两个值之间
​ 用红色的新键进行链接，就会发现如下图，出现了红色链接是右链接，进行左旋，然后右旋，之后颜色反转

红黑树的根节点的的颜色总是黑色的

向树底部的3-结点插入新键

这个插入之后就会生成一个临时的4-结点，需要使用到颜色反转

红黑树的API设计

代码在Node中加上String方法主要是为了方便测试时出现的问题

package day_algorithm.demo_redBlackTree;

public class RedBlackTree<Key extends Comparable<Key>,Value> {//红黑树的实现
    private Node root;
    private int N;
    private static final boolean RED = true;//红色链接标识
    private static final boolean BLACK =false;//黑色链接标识
    private class Node{
        public  Key key;
        private Value value;
        public Node left;
        public Node right;
        public boolean color;

        public Node(Key key, Value value, Node left, Node right, boolean color) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.color = color;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    ", left=" + left +
                    ", right=" + right +
                    ", color=" + color +
                    '}';
        }
    }
    public RedBlackTree(){//构造方法
        N=0;
        root=null;
    }
    private boolean isRed(Node x){//判断当前结点的父结点指向链接是否为红色
        if(x==null){
            return false;
        }
        return x.color==RED;
    }
    private Node rotateLeft(Node h){//左旋调整
        //System.out.println(h.left+"-"+h.right);
        //System.out.println(root);
        Node x=h.right;//获取结点的右子结点
        h.right=x.left;
        x.left=h;
        x.color=h.color;
        h.color=RED;
        //System.out.println("变换之后的"+root);
        return x;
    }
    private Node rotateRight(Node h){//右旋调整
        Node x=h.left;
        h.left=x.right;
        x.right=h;
        x.color=h.color;
        h.color=RED;
        return x;
    }
    private void flipColors(Node h){//颜色反转，相当于拆分4-结点
        h.color=RED;
        h.left.color=BLACK;
        h.right.color=BLACK;
    }
    public void put(Key key,Value value){//在整个树上完成插入操作
        //System.out.println(root.left+"="+root.right);
        root=put(root,key,value);
        root.color=BLACK;
    }
    private Node put(Node h,Key key,Value value){//在指定树中，完成插入操作，并返回添加新元素后的新树
        if(h==null){
            N++;
            return new Node(key,value,null,null,RED);
        }
        //System.out.println(key+"--"+root.left+"="+root.right);
        //去比较h结点键和key的大小
        if(key.compareTo(h.key)<0){
            h.left=put(h.left,key,value);
        }
        else if(key.compareTo(h.key)>0){
            h.right=put(h.right,key,value);
        }else{
            h.value=value;
        }
        //进行左旋,左子节点为黑色，右子结点为红色
        if(isRed(h.right)&&!isRed(h.left)){
            h=rotateLeft(h);
        }
        //进行右旋,当当前结点的左子结点，和左子节点的左子节点都是红色链接
        if(isRed(h.left)&&isRed(h.left.left)){
            h=rotateRight(h);
        }

        //颜色反转,当前结点的左子结点和右子结点都是红色
        if(isRed(h.left)&&isRed(h.right)){
            flipColors(h);
        }
        return h;
    }
    public  Value get(Key key){//根据key，从树中查找对应的值
        return get(root,key);
    }
    private Value get(Node x,Key key){//从指定的树x中找出对应的值
        if(x==null){
            return null;
        }
        if(key.compareTo(x.key)<0){
            return get(x.left,key);
        }else if(key.compareTo(x.key)>0){
            return get(x.right,key);
        }else{
            return x.value;
        }
    }
    public int size(){
        return N;
    }
}

测试

package day_algorithm.demo_redBlackTree;

public class RedBlackTreeTest {
    public static void main(String[] args) {
        //创建红黑树
        RedBlackTree<String, String> tree = new RedBlackTree<>();
        //插入红黑树
        tree.put("1","张三");
        tree.put("2","张2");
        tree.put("3","张3");
        tree.put("3","张重复更改的");

        //从树中获取元素

        System.out.println("tree.get(\"1\") = " + tree.get("1"));
        System.out.println("tree.get(\"2\") = " + tree.get("2"));
        System.out.println("tree.get(\"3\") = " + tree.get("3"));
    }
}

图

动态规划

笔记

笔记1：markDown上下标可以使用

<sub>下标</sub>
~下表~
<sup>上标</sup>
^上标^