当前位置:首页 > 服务端 > 22.1.8 堆排序、桶排序

22.1.8 堆排序、桶排序

22.1.8 堆排序、桶排序

1. 堆排序:时间复杂度:O(nlogn), 空间复杂度:O(1)

(1)完全二叉树:
  • 第i个节点的左孩子:2*i+1;

  • 第i个节点的右孩子:2*i+2;

  • 第i个节点的父节点:(i-1)/2;

(2)大根堆:以节点i为根节点的子树中,节点i上的值是这棵子树中最大的。
(3)小根堆:以节点i为根节点的子树中,节点i上的值是这棵子树中最小的。
(4)code:
public static void main(String[] args)
{
int[] arr = {2,5,3,6,2,1,9,7,8};
heapSoft(arr);
for(int cur:arr)
System.out.print(cur+" ");
}

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

public static void heapSoft(int[] arr)
{

if(arr == null || arr.length<2)
return;
int heapsize = arr.length;
       
       //两个方法构建大根堆
for(int i=0;i<arr.length;i++)//O(N)
heapinsert(arr,i);//该操作时间复杂度为O(logn)
       
       //for(int i = arr.length-1;i>=0;i--)
           //heapify(arr,i,arr.length);//该操作时间复杂度为O(N)
       
while(heapsize>0)
{
heapify(arr,0,heapsize);
swap(arr,0,--heapsize);
}
}


//堆中最重要两个操作
//构建大根堆
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;
}
}

//改变index位置的值后,重新构建大根堆。
public static void heapify(int[] arr,int index,int headsize)
{
int left = index*2+1;
while(left<headsize)
{
int largest = arr[left]<arr[left+1] && left+1<headsize?left+1:left;

largest = arr[largest]>arr[index]?largest:index;
if (index == largest)
break;
swap(arr,largest,index);
index = largest;
left = index*2+1;
}
}

(2)堆注意事项:

  • 用系统提供的小根堆(例如,PriorityQueue<Integer>)只能单次add或者poll一个数,不支持 用户改掉已构建好的堆中的某个值然后以少量时间代价重新构建堆的功能,有需求需要手写堆(高效需求)。

(3)比较器

  • 相当于c++中的比较运算符重载,可以实现两个类实例化的变量之间的比较。可以配合java中Array.sort(待排序的数组,排序方式)一起使用。

  • 返回值标准:

    返回值为负数,第一个参数排在前面;

    返回值为正数,第二个参数排在前面;

    返回值为0;谁在前面无所谓。

  • code:

import java.lang.*;
import java.util.Arrays;
import java.util.Comparator ;
@SuppressWarnings("unused")
public class selectionSoft {

public static void main(String[] args) {
Student student1 = new Student("A", 2, 23);
Student student2 = new Student("B", 3, 21);
Student student3 = new Student("C", 1, 22);

Student[] students = new Student[] { student1, student2, student3 };

Arrays.sort(students, new IdAscendingComparator());
printStudents(students);
}

public static class Student {
public String name;
public int id;
public int age;

public Student(String name, int id, int age) {
this.name = name;
this.id = id;
this.age = age;
}
}

public static class IdAscendingComparator implements Comparator<Student> {

public int compare(Student o1, Student o2) {
return o1.id - o2.id;
}

}

public static void printStudents(Student[] students) {
for (Student student : students) {
System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
}
}


}
  • 运行结果:

Name : C, Id : 1, Age : 22 Name : A, Id : 2, Age : 23 Name : B, Id : 3, Age : 21

(4)桶排序

  • 1)桶排序思想下的排序都是不基于比较的排序

  • 2)时间复杂度为O(N),额外空间负载度O(M)

  • 3)应用范围有限,需要样本的数据状况满足桶的划分

  • code:

    //算法思想:
//假设有一组数:011,022,021,035,096,145
//最大的数145有三个十进制位,我们先根据个位数字的大小在count数组中记录词频,1的词频是2,2的词频是1,5的词频是2,6的词频是1,其余数的次词频为0,即count[1]=2,count[2]=1,count[5]=2,count[6]=1,其余的count[0,3,4,7,8,9]=0.再把count数组加工为前缀和数组,即count[0]=0,count[1]=2,count[2]=count[3]=count[4]=3,count[5]=5,count[6]=7,count[7,8,9]=7,在bucket数组中,从数的右侧开始看,145,各位上的5对应的前缀和数组中的5,所以145应放在bucket数组中下标为(5-1)=4的位置,然后count[5]--,变为4,同理096应放在bucket[6]......将011放到bucket中相当于完成了一次入桶出桶。

public static void main(String[] args)
{
int[] arr = {2,5,6,1,3,6,3,2,6};
radixSort(arr,0,arr.length-1,maxbits(arr));
for(int cur:arr)
System.out.print(cur+" ");

}

public static void radixSort(int[] arr,int L,int R,int digit)//digit表示最大的十进制位数。
{
final int radix = 10;
int i=0,j=0;
int[] bucket = new int[R-L+1];//辅助数组,便于后面的入桶和出桶。
for(int d = 1;d <= digit; d++)//确定入桶和出桶的次数
{
int[] count = new int[radix];//count数组用来存前缀和,长度一定10
for(i=L;i<=R;i++)
{
j = getDight(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 = getDight(arr[i],d);
bucket[count[j]-1] = arr[i];
count[j]--;
}
}
for(i=L,j = 0;i<=R;i++,j++)
{
arr[i] = bucket[j];
}
}

public static int maxbits(int[] arr)
       //这个函数用来确定数组中最大的的数一共有多少个十进制位,100为三位,1000为四位。
  {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++)
      {
max = Math.max(max, arr[i]);
}
int res = 0;
while (max != 0)
      {
res++;
max /= 10;
}
return res;
}

public static int getDight(int x,int d)
{
return ((x/((int)Math.pow(10,d-1 )))%10);
}

 

作者:张满月。
来源链接:https://www.cnblogs.com/txzmy/p/15779618.html

版权声明:
1、Java侠(https://www.javaxia.com)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。





本文链接:https://www.javaxia.com/server/125323.html

标签: unused variable
分享给朋友:

“22.1.8 堆排序、桶排序” 的相关文章

Python基础知识2022年05月16日 21:27:39
[C++]VC自定义发IP包例子2022年05月17日 20:41:27
常用日志框架介绍2022年05月19日 20:04:06
多线程编程(1)2022年05月20日 21:26:51
Spring Boot+微信小程序2022年05月20日 21:27:40
Python 散列表查询2022年05月20日 21:28:09
python中对切片的理解2022年05月23日 21:57:45