private static boolean isHeapEmpty(int[] heap) {
if(heap[0]==Integer.MAX_VALUE){
return true;
}
return false;
}
/*
* 构造小顶堆
*/
private static int[] buildHeap(int[] numbers) {
int[] heap=new int[numbers.length];
for(int i=0;i<heap.length;i++){
heap[i]=numbers[i];
}
for(int j=(heap.length>>1)-1;j>=0;j--){ //从有孩子的结点开始，从底向上维护堆
adjustHeap(heap,j);
}
return heap;
}
/*
* 维护堆
*/
private static void adjustHeap(int[] heap, int j) {
int left=j<<1;
int right=(j<<1)+1;
int largest=j;
if(left<heap.length //该左孩子下标必须在数组内
&&heap[left]!=Integer.MAX_VALUE //该元素必须未被覆盖
&&heap[j]<heap[left]){
largest=left;
}
if(right<heap.length
&&heap[right]!=Integer.MAX_VALUE
&&heap[largest]<heap[right]){
largest=right;
}
if(largest!=j){
swap(heap, j, largest);
adjustHeap(heap, largest); //继续往下调整
}
}
/*
* 快速排序
*/
public static void quickSort(int[] numbers){
if(numbers==null){
System.out.println("Invalid input!");
return;
}
System.out.println("QuickSort:");
quickSort(numbers,0,numbers.length-1);
}
private static void quickSort(int[] numbers, int start, int end) {
if(start<end){
int mid=patition(numbers,start,end);
quickSort(numbers, start, mid-1);
quickSort(numbers, mid+1, end);
}
}
/*
* 选一个数，将小于它的数放在左边，大于它的放在右边
*/
private static int patition(int[] numbers, int start, int end) {
int small=start-1;
int index=start;
int temp=numbers[end]; //选择数组最后一个元素作为比较数
while(index<=end){
if(numbers[index]<temp){
small++;
if(index!=small){
swap(numbers, small, index);
}
}
index++;
}
swap(numbers, small+1, end);
return small+1;
}
/*
* 交换数组的两个元素
*/
private static void swap(int[] numbers, int a, int b) {
int temp = numbers[a];
numbers[a] = numbers[b];
numbers[b] = temp;
System.out.println("current numbers:" + //记录交换次数
""+Arrays.toString(numbers)+"----swap times:"+(++swapTimes));
}