首页 > 编程知识 正文

桶排序和基数排序的区别,桶排序的流程图

时间:2023-05-05 12:20:24 阅读:141709 作者:1174

桶排序炉结构用数组实现的完全二叉树结构什么是完全二叉树结构?

从左到右依次排满的是完全二叉树结构。

满足该结构时,I节点的左边的子节点为2i 1,右边的子节点为2i 2。 父节点是(i-1 )/2。

堆是特殊的完全二叉树

在完全二叉树中,如果各子树的最大值在最上面,则在大树根完全二叉树中,如果各子树的最小值在最上面,则小树根堆结构的heapInsert和heapify操作堆结构的增大和减小优先级队列结构是堆结构重叠萝卜堆,父节点是

去除最大值的顶点节点,使其馀的结构仍为大根山。

可以用最后一个根节点交换最大值并断开连接。 通过交换上升的值,比较替换位置,使堆返回到大根的堆中。

public classcode 06 _ heapsort { publicstaticvoidheapsort (int [ ] arr ) if(arr==null||arr.length2) { return; }for(intI=0; i arr.length; I ) HEAPinsert(ARR,I ); (} int size=arr.length; swap(arr,0,--size ); wile(size0) heap ify (arr,0,size ); swap(arr,0,--size ); } publicstaticvoidheapinsert (int [ ] arr,int index ) (while ) arr[index]arr ) (index - 1 )/2 ) ) swap ) arr,int } publicstaticvoidheapify (int [ ] arr,int index,int size ) intleft=index*2; while(leftsize ) int largest=left1size arr [ left1] arr [ left ]? 左1 :左; largest=arr[largest] arr[index]? largest :索引; if(largest==index ) { break; }swap(arr,largest,index ); 索引=largest; left=index * 2 1; }publicstaticvoidswap(int[]arr,int i,int j ) { int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; }满是二叉树的n个节点

叶节点为N/2个,进行1的动作

楼上的N/4个进行2次动作

的总体复杂度t(n )=N/2 N/4*2 N/8 *3 ……

通过相位减法,t(n )=N N/2 N/4 N/8 ……

属于o(n )级的复杂性

主题1 已知一个几乎有序的数组,几乎有序是指,如果把数组排好顺序的话,每个元素移动的距离可以不超过k,并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

设k=6

准备小的砌墙结构

遍历数组,遍历前七个数字。 这七个数的最小值是当前数组的最小值。 由于该数组几乎是规则的,因此最小值被调整为第一位移动到6以下。 这样找到最小值,然后把这七个数字向后移动。 每次移动时,都可以从小根堆中弹出当前最小值。 最后一次遍历完成后,数组排序完成。

该方法的复杂度为o(n*logk ),几乎可以认为是o ) n )的算法

数组需要扩展,但扩展的次数有限。 扩张的水平是o(logn )不影响最终的表现

黑盒

- add

-保罗

黑匣子的话,不需要手写堆积。

使用比较器比较器的本质是比较运算符比较器的过载可以很好地应用

在特殊标准的排序上比较器可以很好的应用在根据特殊标准排序的结构上 比如堆 桶排序

(不基于比较的排序,要根据数据状况定制的。)

桶排序思想下的排序

计数排序

要将[0,200]年龄的人进行排序,可以准备一个[0,200]的一个数组。

每遇到一个k岁的人,那么arr[k]++,就可以统计出年龄的次频表出来。

然后按照年龄这个数组的顺序,将人倒出就进行了排序。

但是如果这个数据不是年龄,而是其他很大的数,那么就需要很大的数组来装载,这很浪费空间,也很没必要。

因此可以采用基数排序。

基数排序

先根据各位数字,放进0-9十个桶中,然后按顺序倒出来。然后再按照十位,放进对应的桶里,然后倒出来。 最后一直放到最高位,就成功排序了。(十进制的数)

仍然是要根据数据状况排序的,如果没有进制的数,还是没法排序

桶应该怎么表示

用一个词频数组来表示,这个词频数组处理十进制数的时候就是10位的一个数组。

然后将词频数组count,变成词频的累加数组count。那么count每一位表示的就是这一位,小于等于k的数有多少个。

再建立一个辅助的help数组,长度跟需要排序的数组一样长。

然后从右往左,看原来的数组。最后一位的个位数是k,count[k]–,然后并将这个数放在help的count[k]位置,cont[k]为当前个位数小于等于k的数的数量。

然后十位,百位同样这样操作。

代码 import java.util.Arrays;public class Code08_RadixSort { // only for no-negative value 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(max, arr[i]); } int res = 0; while (max != 0) { res++; max /= 10; } return res; } public static void radixSort(int[] arr, int begin, int end, int digit) { final int radix = 10; //digit 表示最大值有几个十进制位 int i = 0, j = 0; int[] bucket = new int[end - begin + 1]; //和原数组一样长的桶 for (int d = 1; d <= digit; d++) { //有多少位,出桶入桶多少次 //count[i] 当前位是(0~i)的数有几个。处理成累计数组之后 int[] count = new int[radix]; for (i = begin; i <= end; i++) { j = getDigit(arr[i], d); //拿出第d位数 count[j]++; //形成词频表 } for (i = 1; i < radix; i++) { count[i] = count[i] + count[i - 1]; //变成累加数组 } for (i = end; i >= begin; i--) { j = getDigit(arr[i], d); bucket[count[j] - 1] = arr[i]; //根据count-1,填入辅助数组 count[j]--; } for (i = begin, j = 0; i <= end; i++, j++) { arr[i] = bucket[j]; //把这个结构放回arr } } } public static int getDigit(int x, int d) { return ((x / ((int) Math.pow(10, d - 1))) % 10); }}

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。