JAVA——堆排序、桶排序以及链表
失踪了快一个星期了，因为最近这段时间实在是太忙了，原本想两天一更的，但是发现没啥时间，所以索性随缘更新吧，现在总结一下这段时间学习的一些算法：
---堆排序---
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构：
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大根堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
即：arr[i]>arr[(i-1)/2]
小根堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
a.假设给定无序序列结构如下
2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
此时，我们就将一个无需序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
a.将堆顶元素9和末尾元素4进行交换
b.重新调整结构，使其继续满足堆定义
c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
再简单总结下堆排序的基本思路：
a.将无需序列构建成一个堆，根据升序降序需求选择大根堆或小根堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
综上所述，为实现堆排序，我需要：
1.一个能判断当前元素是否需要上升的代码：heapInsert;
2.一个能判断当前元素是否需要下降的代码：heapify;
3.swap交换函数；
4.heapsort函数，将传入的数组首先逐个进行heapInsert排成大根堆，然后将头元素和尾元素对换，堆长度减1；当堆长度不为0时反复执行，直至有序
话不多说，我们来看看代码，首先是插入一个元素判断其是否需要上升的代码heapInsert：
public static void heapInsert(int[] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}
它的主要逻辑是：如果当前节点值大于父节点值，那么就和父节点进行交换；
其次我们来看看另一个代码heapify，它用于判断一个结点是否需要下沉：
public static void heapify(int arr[],int index,int size){int left = index * 2 + 1;while(left<size){int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;largest = arr[index] > arr[largest] ? index : largest;if(largest == index){break;}swap(arr,index,largest);index = largest;left = index * 2 + 1;}}
在heapify中，定义了左孩子节点；
代码的第3行，含义是当该结点含有左孩子节点时，便执行while循环判断它是否需要继续下沉；
代码的第4行，是基于右孩子节点存在的情况下，左右孩子节点进行比较，挑选出大的那一个去和父节点比较；
代码的第6行，当最大值就是父节点的时候，已经做到局部有序，因为其下面的值在heapInsert里已经被排成大根堆形式，倘若能确定父节点比两个子节点都要大，那么子节点的一系列子节点一定比该父节点小，所以再循环下去无意义，直接break跳出循环；
代码的第9行，能走到这里说明：最大值不等于父节点值，那么就执行交换操作，将最大值下标和父节点下标对应的值在数组中进行交换；
代码的第10行，第11行，是让当前值继续往下遍历，跟随旧的父节点的位置，继续往下判断它是否还要需要向下移动；
整个代码如下：
import java.util.Arrays;import java.util.Scanner;public class heapSort {public static void heapSort(int arr[]){if (arr == null || arr.length < 2) {return;}for (int i = 0; i < arr.length; i++) {heapInsert(arr, i);}int size = arr.length;swap(arr,0,--size);while(size>0){heapify(arr,0,size);swap(arr,0,--size);}}public static void heapInsert(int[] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}public static void heapify(int arr[],int index,int size){int left = index * 2 + 1;while(left<size){int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;largest = arr[index] > arr[largest] ? index : largest;if(largest == index){break;}swap(arr,index,largest);index = largest;left = index * 2 + 1;}}public static void swap(int arr[],int i,int j){int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}//for testpublic static void comparator(int arr[]){Arrays.sort(arr);}public static int[] generateRandomArray(int maxSize,int maxValue){int arr[] = new int[(int)(maxSize*Math.random())+1];for(int i = 0;i<arr.length;i++){arr[i] = (int)(maxValue*Math.random())+1;}return arr;}public static int[] copyArray(int arr[]){int arr2[] = new int[arr.length];for(int i=0;i<arr.length;i++){arr2[i] = arr[i];}return arr2;}public static boolean isEqual(int arr[],int arr2[]){int count = 0;for(int i=0;i<arr.length;i++){if(arr[i]==arr2[i]){count++;continue;}else{break;}}if(count==arr.length){return true;}else return false;}public static void main(String args[]){Scanner reader = new Scanner(System.in);System.out.println("请输入测试次数：");int testtime = reader.nextInt();for(int i=0;i<testtime;i++){int arr[] = generateRandomArray(100,100);int arr2[] = copyArray(arr);heapSort(arr);comparator(arr2);if(!isEqual(arr,arr2)){System.out.println("compare failed!");}else {System.out.println("compare succeed!");}}}}
---桶排序---
首先，声明一下，桶排序这种算法十分特殊，适用的情况是：已知最高位的位数，且位数不太大，并且要将每个数字变为长度相等，具体实现就是最高位用0补齐
一、思想
一句话总结：划分多个范围相同的区间，每个子区间自排序，最后合并。
桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。
桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。
二、图解过程
为了实现代码，我们需要：
1.一个用于返回数组中最大数字的最高位数的函数，我们把它叫做maxbits；
2.核心桶排序算法，我们把它叫做radixSort；
3.一个取出当前位数值的算法，叫做getDigit；
还是老样子，我们通过代码来看看如何实现：
public static int maxbits(int[] arr) {int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {max = Math.max(arr[i], max);}int res = 0;while (max != 0) {res++;max /= 10;}return res;}
这个算法能找出数组中的最大值，并返回他的最高位数有几位；
接下来我们来看看核心算法：
public static void radixSort(int arr[], int L, int R, int digit) {final int radix = 10;int[] bucket = new int[R - L + 1];int i = 0, j = 0;for (int d = 1; d <= digit; d++) {int[] count = new int[radix];for (i = L; i <= R; i++) {j = getDigit(arr[i], d);count[j]++;}for (i = 1; i < radix; i++) {count[i] = count[i] + count[i - 1];}for (i = R; i >= L; i--) {j = getDigit(arr[i], d);bucket[count[j]-1] = arr[i];count[j]--;}for (i = 0, j = 0; i < arr.length; i++, j++) {arr[i] = bucket[j];}}}
首先，我们定义了一个常量radix，表示十进制；
其次，我们申请了一个桶数组，它的长度就等于传参进来的数组的长度；
然后我们需要定义一个位数变量，记作d，这里的d应该小于等于最高位的digit，如代码第五行所示，for循环的含义是在每一位上进行桶排序操作，当最高位数排序完毕时，整个数组将有序；
代码的第6行，定义了一个计数数组，它的数组下标，就等于当前位数的数值；
代码的第7行，第一个for循环，先取出arr[i]第d位上的那个数字，然后让计数数组对应位数自增；
代码的第11行，第二个for循环，它的意义是改编当前计数数组，将区间计数变为累加计数；
代码第14行，第三个for循环，再次遍历数组，只不过是从右向左(为了增加稳定性)，目的是为了找出每个数应该放在哪里，所以首先使用getDigit函数取出d位置上的数字j，count[j]代表的意思是从0到j的所有下标数总共有多少个，所以该数字arr[i]应该存放在对应bucket的下标为count[j]-1的位置，然后使count[j]自减，既能代表已经存放，也能代表下次存放的下标区间；
代码第19行，第四个for循环，将桶中的元素还原到数组；
我们来看看整体代码的实现：
public static void radixSort(int arr[]) {if (arr == null || arr.length < 2) {return;}radixSort(arr, 0, arr.length - 1, maxbits(arr));}public static int maxbits(int[] arr) {int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {max = Math.max(arr[i], max);}int res = 0;while (max != 0) {res++;max /= 10;}return res;}public static void radixSort(int arr[], int L, int R, int digit) {final int radix = 10;int[] bucket = new int[R - L + 1];int i = 0, j = 0;for (int d = 1; d <= digit; d++) {int[] count = new int[radix];for (i = L; i <= R; i++) {j = getDigit(arr[i], d);count[j]++;}for (i = 1; i < radix; i++) {count[i] = count[i] + count[i - 1];}for (i = R; i >= L; i--) {j = getDigit(arr[i], d);bucket[count[j]-1] = arr[i];count[j]--;}for (i = 0, j = 0; i < arr.length; i++, j++) {arr[i] = bucket[j];}}}public static int getDigit(int x, int d) {return ((x / (int) Math.pow(10, d - 1)) % 10);}
看看这个getDigit代码，实现的非常妙，取位函数通常都是除以10，取出第d位的数字，就是除以10的d-1次幂之后，将该位数转化到各位上，再进行取余操作；pow的返回值为double，所以需要强制转型为int。
---链表---
有关链表的定义我就不过多声明了，接下来首先介绍几个链表的基础操作：
import java.util.Stack;public class LinkedList {//链表节点的声明public static class ListNode{int val;ListNode next;public ListNode(int val) {this.val = val;this.next = null;}}//链表中添加元素public static void InsertList(ListNode head, int val) {if (head == null) {return;}ListNode tempNode = new ListNode(val);ListNode p = head;while (p != null) {p=p.next;//p指向下一节点}p.next = tempNode;}//链表中删除元素public static void deleteList(ListNode head, int val) {if (head == null) {return;}if (head.val == val) {head = head.next;}ListNode p =head;while (p.next != null && p.next.val != val) {p = p.next;}if (p.next == null) {System.out.println("未找到该值");} else {p.next = p.next.next;}}public static void printList(ListNode head) {ListNode p =head;while (p != null) {System.out.print(p.val+"\t");p=p.next;}}public static void invertedprintList(ListNode head) {Stack<ListNode> stack = new Stack<>();ListNode p =head;while (p != null) {stack.push(p);p=p.next;}while(!stack.isEmpty()){p = stack.pop();System.out.print(p.val+"\t");}}public static void main(String[] args) {ListNode List = new ListNode(3);List.next = new ListNode(5);List.next.next = new ListNode(7);List.next.next.next = new ListNode(11);printList(List);invertedprintList(List);}
这是在列表中进行删除，添加，查询，打印以及反转链表的代码，不多阐述；
当然，这里的翻转链表操作中引入了栈空间，导致空间复杂度为o(n)，那么有没有一种方法使空间复杂度为o(1)呢？答案是肯定的：
/**** 反转单向和双向链表* 【题目】 分别实现反转单向链表和反转双向链表的函数。* 【要求】 如果链表长度为N，时间复杂度要求为O(N)，额外空间* 复杂度要求为O(1)*/public class reverseList {public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}public static Node reverseList(Node head) {Node pre = null;Node next = null;while (head != null) {next = head.next;head.next = pre;pre = head;head = next;}return pre;}public static class DoubleNode {public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data) {this.value = data;}}public static DoubleNode reverseList(DoubleNode head) {DoubleNode pre = null;DoubleNode next = null;while (head != null) {next = head.next;head.next = pre;head.last = next;pre = head;head = next;}return pre;}public static void printLinkedList(Node head) {System.out.print("Linked List: ");while (head != null) {System.out.print(head.value + " ");head = head.next;}System.out.println();}public static void printDoubleLinkedList(DoubleNode head) {System.out.print("Double Linked List: ");DoubleNode end = null;while (head != null) {System.out.print(head.value + " ");end = head;head = head.next;}System.out.print("| ");while (end != null) {System.out.print(end.value + " ");end = end.last;}System.out.println();}public static void main(String[] args) {Node head1 = new Node(1);head1.next = new Node(2);head1.next.next = new Node(3);printLinkedList(head1);head1 = reverseList(head1);printLinkedList(head1);DoubleNode head2 = new DoubleNode(1);head2.next = new DoubleNode(2);head2.next.last = head2;head2.next.next = new DoubleNode(3);head2.next.next.last = head2.next;head2.next.next.next = new DoubleNode(4);head2.next.next.next.last = head2.next.next;printDoubleLinkedList(head2);printDoubleLinkedList(reverseList(head2));}}
我们来分析一下反转单向链表的操作：
首先定义两个新的Node型变量pre和next，当head不为空时：
1.用next来存放head.next的空间；
2.将head.next指向pre,头结点翻转后就是尾结点，所以第一次循环head.next会指向null；
3.令pre来到下一个节点head处；
4.令head来到下一个节点head.next(next存放的位置)处；
分析完单链表的，双链表自然而然也就会了，无非就是多了一步将前驱改为后继，将后继改为前驱，其它都是一样；
代码的执行效果图如下：
Problem1:打印两个有序链表的公共部分
因为链表是有序的，所以我们可以采取和归并算法一样的思路：定义两个变量遍历两个链表，当i.value<j.value时，j不动，i继续遍历；反之，当j.value<i.value时，i不动，j继续遍历;当i,value==j.value时，就输出该数字，i，j同时往后；代码的实现如下：
public class LinkedList_printPublicPart {public static class ListNode{int val;ListNode next;ListNode(int val) {this.val = val;this.next = null;}}public static void printcommonPart(ListNode head1,ListNode head2) {System.out.print("common part:");while (head1 != null && head2 != null) {if (head1.val < head2.val) {head1 = head1.next;} else if (head1.val > head2.val) {head2 = head2.next;} else {System.out.print(head1.val+"\t");head1 = head1.next;head2 = head2.next;}}System.out.println();}public static void printLinkedList(ListNode head) {System.out.print("Linked List: ");ListNode p = head;while (p != null) {System.out.print(p.val + " ");p = p.next;}System.out.println();}public static void main(String[] args) {ListNode node1 = new ListNode(2);node1.next = new ListNode(3);node1.next.next = new ListNode(5);node1.next.next.next = new ListNode(6);ListNode node2 = new ListNode(1);node2.next = new ListNode(2);node2.next.next = new ListNode(5);node2.next.next.next = new ListNode(7);node2.next.next.next.next = new ListNode(8);printLinkedList(node1);printLinkedList(node2);printcommonPart(node1, node2);}}
今天就总结这么多吧，写了很多字了，改天再总结两个链表的题目！