`
还可以
  • 浏览: 80963 次
  • 性别: Icon_minigender_1
  • 来自: 重庆
社区版块
存档分类
最新评论

算法实现-计数排序(使用堆排序筛选数组中的最大值)

阅读更多

 

使用堆排序选出数组中的最大值,然后使用计数排序对整个数组进行排序

 

package com.sort;

 

public class HeapSort {

/**

* 将整棵树构建为最大堆

* @param a

*/

public void builMaxHeap(int[] a){

int length = a.length-1;//堆排序数据长度,第一个数据不使用,设置为0,哨兵值

int heapSize = length/2;

for(;heapSize > 0 ;heapSize--){

maxHeapfy(a,heapSize);

}

}

/**

* 将子树构建为最大堆

* @param a

* @param root

*/

public void maxHeapfy(int[] a,int root){

int largest = root;

int left = 2*largest;

int right = 2*largest +1;

if(left>a.length-1){//当左子树大于数组最后一个元素的下标时,直接返回

return;

}else if(left == a.length-1){//当左子树等于数组最后一个元素的下标时,比较数组

if(a[root]<a[left]){

int tmp = a[root];

a[root] = a[left];

a[left]= tmp;

}

return;

}

//其他情况则表示存在右节点,按照一颗完整子树去比较根节点与左右子树的大小

if(a[largest]<a[left]){

largest = left;

}

if(a[largest]<a[right]){

largest = right;

}

if(root != largest){//保持树中的根节点为最大值

int tmp;

tmp = a[root];

a[root] = a[largest];

a[largest] = tmp;

}else if(root == largest){//如果根节点为最大值

if(a[left]>a[right]){//比较左右子树的大小

largest = left;

}else{

largest = right;

}

}

//largest = largest + 1;

maxHeapfy(a,largest);

}

/**

* 堆排序算法

* @param a

* @return

*/

public int[] heapSort(int[] a){

this.builMaxHeap(a);

int length = a.length-1;

int[] b = new int[a.length];

b[0] = -1;//哨兵值,这个树不参与排序,和a数组中第一个值保持一致

for(int i=length;i>0;i--){//循环将树重新构建成最大堆

b[i] = a[1];//将新构建的最大堆中根节点赋值给数组b

a[1] = -1;//将根节点赋值无用的-1标记

this.maxHeapfy(a, 1);//重新构建堆

}

return b;

}

public static void main(String[] args) {

int[] a = new int[]{-1,4,1,3,2,16,22,23,0,25,25,25,9,10,14,8,1000};

HeapSort heapSort = new HeapSort();

int[] b = heapSort.heapSort(a);

for(Integer sortHeap:b){

System.out.println(sortHeap);

}

}

 

}


 

 

 

package com.sort;

 

public class CountSort {

 

public int[] countSort(int[] a){

HeapSort heapSort = new HeapSort();

heapSort.builMaxHeap(a);

int length = a[1]+1;

int[] c = new int[length];//构造计数的临时数组

for(int i = 1;i<a.length;i++){//对a中的数组元素进行计数,

c[a[i]] = c[a[i]]+1;

}

for(int j = 1;j<c.length;j++){//记录小于当前元素的元素个数

c[j] = c[j]+c[j-1];

}

int[] b = new int[a.length];//新建复制数组

int alength = a.length - 1;

for(int index = alength;index>=1;index--){//在b数组中进行排序

b[c[a[index]]] = a[index];

c[a[index]] = c[a[index]]-1;

}

return b;

}

/**

* @param args

*/

public static void main(String[] args) {

CountSort countSort = new CountSort();

int[] a = new int[]{0,2,1,6,7,10,100,23};

int[] b = countSort.countSort(a);

for(Integer i : b){

System.out.println(i);

}

}

}


分享到:
评论

相关推荐

    编程算法练习--没事的时候练练

    - **描述**:使用选择排序算法对一个数组进行排序。 - **实现思路**: - 从未排序的部分中选出最小(或最大)的元素。 - 将其放到已排序部分的末尾。 - 重复上述步骤直到所有元素都被排序。 #### 知识点二十九:...

    ACM/ICPC算法大全(c语言)

    - 使用线段树(Segment Tree)或斐波那契堆等数据结构实现RMQ查询。 - **RMQ离线算法O(N*LOGN)+O(1)求解LCA** - LCA(Lowest Common Ancestor)问题是指在树中找到两个节点的最近公共祖先。本节介绍了如何通过RMQ...

    ACM算法整合

    - 归并排序是一种稳定的排序算法,同时也可以用来计算数组中的逆序数。 - **逆序数推排列数** - 通过计算逆序数来推断排列的数量。 - **二分查找** - 二分查找是一种在有序数组中查找特定元素的有效方法。 - **二...

    ACM编程题模板和各种经典算法数据结构实现代码

    - C++ STL中的优先队列是一种基于堆的数据结构,用于实现优先级队列。 21. **堆栈** - 堆栈是一种只允许在一端进行插入和删除操作的线性表。 22. **区间最大频率** - 区间最大频率问题是指在一个区间内出现...

    数据结构各种算法

    除此之外,还有快速排序、插入排序、选择排序、希尔排序、计数排序、桶排序、基数排序等其他排序算法,每种都有其特点和适用场景。例如,快速排序以其平均时间复杂度为O(n log n)和优秀的实际性能而受到广泛应用;...

    algorithm-ebook_zh-hans

    - **堆排序(Heap Sort)**:利用堆这种数据结构所设计的一种排序算法。 - **计数排序(Counting Sort)**:适用于一定范围内的整数排序,在辅助空间的帮助下,对每一个输入的元素x,确定小于x的元素个数。 - **桶排序...

    ACM程序算法模板与经典算法大集合

    包括插入排序、堆排序、合并排序、计数排序、冒泡排序、快速排序等。 ##### 7.8、二分搜索 二分搜索是一种在有序数组中查找特定元素的高效算法。 #### 八、技巧 这些技巧包括输入输出优化、递归、位运算、字典序...

    C语言实现一些经典算法,可以免费下载

    标题《C语言实现一些经典算法,可以免费下载》和描述《参加比赛后第一次知道算法这么重要,在网上找过很多算法的资料,这个资料对我最有帮助》表明了本资料是关于使用C语言实现各类经典算法,并且可以免费获取的电子...

    经典算法源代码(for ACM)

    **STL中的PRIORITY_QUEUE**:标准模板库中的优先队列,可以方便地实现堆的操作。 **归并排序求逆序数**:在归并排序的过程中统计逆序数的数量,可以实现线性对数级别的效率。 **二分查找**:一种高效的查找算法,...

    Noip知识的

    - **计数排序**:适用于整数排序,通过统计每个数值出现的次数来排序。对于非数字类型的数据不适用。 #### 数据结构 数据结构是存储和组织数据的方式,是算法设计的基础。 1. **1:1 结构** - **队列**:先进先...

    2021-2022计算机二级等级考试试题及答案No.17205.docx

    堆排序:最坏情况下比较次数不是n(n-1)/2。 - **结论**:正确答案为D。 #### 24. 静态方法访问限制 - **问题描述**:静态方法能否访问类中的所有成员? - **答案解析**:静态方法只能访问类中的静态成员,不能...

    程序员面试攻略 part1(共2个)

    7.11 面试例题:最大值,不允许使用统计功能131 7.12 面试例题:生产者/消费者问题132 第8章与计数、测量、排序有关的智力题139 8.1 面试例题:开锁143 8.2 面试例题:三个开关145 8.3 面试例题:过桥146 8.4...

    程序员面试攻略part 2(共2个)

    7.11 面试例题:最大值,不允许使用统计功能131 7.12 面试例题:生产者/消费者问题132 第8章与计数、测量、排序有关的智力题139 8.1 面试例题:开锁143 8.2 面试例题:三个开关145 8.3 面试例题:过桥146 8.4...

Global site tag (gtag.js) - Google Analytics