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

 

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

 

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

}

}

}