使用堆排序选出数组中的最大值,然后使用计数排序对整个数组进行排序
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);
}
}
}
分享到:
相关推荐
- **描述**:使用选择排序算法对一个数组进行排序。 - **实现思路**: - 从未排序的部分中选出最小(或最大)的元素。 - 将其放到已排序部分的末尾。 - 重复上述步骤直到所有元素都被排序。 #### 知识点二十九:...
- 使用线段树(Segment Tree)或斐波那契堆等数据结构实现RMQ查询。 - **RMQ离线算法O(N*LOGN)+O(1)求解LCA** - LCA(Lowest Common Ancestor)问题是指在树中找到两个节点的最近公共祖先。本节介绍了如何通过RMQ...
- 归并排序是一种稳定的排序算法,同时也可以用来计算数组中的逆序数。 - **逆序数推排列数** - 通过计算逆序数来推断排列的数量。 - **二分查找** - 二分查找是一种在有序数组中查找特定元素的有效方法。 - **二...
- C++ STL中的优先队列是一种基于堆的数据结构,用于实现优先级队列。 21. **堆栈** - 堆栈是一种只允许在一端进行插入和删除操作的线性表。 22. **区间最大频率** - 区间最大频率问题是指在一个区间内出现...
除此之外,还有快速排序、插入排序、选择排序、希尔排序、计数排序、桶排序、基数排序等其他排序算法,每种都有其特点和适用场景。例如,快速排序以其平均时间复杂度为O(n log n)和优秀的实际性能而受到广泛应用;...
- **堆排序(Heap Sort)**:利用堆这种数据结构所设计的一种排序算法。 - **计数排序(Counting Sort)**:适用于一定范围内的整数排序,在辅助空间的帮助下,对每一个输入的元素x,确定小于x的元素个数。 - **桶排序...
包括插入排序、堆排序、合并排序、计数排序、冒泡排序、快速排序等。 ##### 7.8、二分搜索 二分搜索是一种在有序数组中查找特定元素的高效算法。 #### 八、技巧 这些技巧包括输入输出优化、递归、位运算、字典序...
标题《C语言实现一些经典算法,可以免费下载》和描述《参加比赛后第一次知道算法这么重要,在网上找过很多算法的资料,这个资料对我最有帮助》表明了本资料是关于使用C语言实现各类经典算法,并且可以免费获取的电子...
**STL中的PRIORITY_QUEUE**:标准模板库中的优先队列,可以方便地实现堆的操作。 **归并排序求逆序数**:在归并排序的过程中统计逆序数的数量,可以实现线性对数级别的效率。 **二分查找**:一种高效的查找算法,...
- **计数排序**:适用于整数排序,通过统计每个数值出现的次数来排序。对于非数字类型的数据不适用。 #### 数据结构 数据结构是存储和组织数据的方式,是算法设计的基础。 1. **1:1 结构** - **队列**:先进先...
堆排序:最坏情况下比较次数不是n(n-1)/2。 - **结论**:正确答案为D。 #### 24. 静态方法访问限制 - **问题描述**:静态方法能否访问类中的所有成员? - **答案解析**:静态方法只能访问类中的静态成员,不能...
7.11 面试例题:最大值,不允许使用统计功能131 7.12 面试例题:生产者/消费者问题132 第8章与计数、测量、排序有关的智力题139 8.1 面试例题:开锁143 8.2 面试例题:三个开关145 8.3 面试例题:过桥146 8.4...
7.11 面试例题:最大值,不允许使用统计功能131 7.12 面试例题:生产者/消费者问题132 第8章与计数、测量、排序有关的智力题139 8.1 面试例题:开锁143 8.2 面试例题:三个开关145 8.3 面试例题:过桥146 8.4...