vlambda博客
学习文章列表

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

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