JAVA——堆排序、桶排序以及链表

vlambda
2022-03-15

JAVA——堆排序、桶排序以及链表

失踪了快一个星期了，因为最近这段时间实在是太忙了，原本想两天一更的，但是发现没啥时间，所以索性随缘更新吧，现在总结一下这段时间学习的一些算法：

---堆排序---

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构：

　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

JAVA——堆排序、桶排序以及链表

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大根堆：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.假设给定无序序列结构如下

JAVA——堆排序、桶排序以及链表

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

JAVA——堆排序、桶排序以及链表

4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

JAVA——堆排序、桶排序以及链表

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

JAVA——堆排序、桶排序以及链表

此时，我们就将一个无需序列构造成了一个大顶堆。

步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

JAVA——堆排序、桶排序以及链表

b.重新调整结构，使其继续满足堆定义

JAVA——堆排序、桶排序以及链表

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

JAVA——堆排序、桶排序以及链表

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

JAVA——堆排序、桶排序以及链表

再简单总结下堆排序的基本思路：

　　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 test public 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);
    }}

今天就总结这么多吧，写了很多字了，改天再总结两个链表的题目！

vlambda博客
学习文章列表