第三天，第三道面试题，坚持下去

港控/mmm° 2022-08-20 09:16 198阅读 0赞

Java中常用的排序方法。

第一种，堆排序

堆排序的原理介绍：

#### 堆排序实现原理图 ####

给定一个整形数组a\[\]=\{16,7,3,20,17,8\}，对其进行堆排序。

首先根据该数组元素构建一个完全二叉树，得到

![2011100413554262.jpg][]

然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：

![2011100413563593.jpg][]![2011100413573782.jpg][]![2011100413581745.jpg][]20和16交换后导致16不满足堆的性质，因此需重新调整

![2011100414001028.jpg][]这样就得到了初始堆。

即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。

![2011100414014182.jpg][]此时3位于堆顶不满堆的性质，则需调整继续调整![2011100414031854.jpg][]

![2011100414052837.jpg][]![2011100414061869.jpg][]![2011100414071128.jpg][]![2011100414083298.jpg][]![2011100414092466.jpg][]![2011100414100910.jpg][]

![2011100414104814.jpg][]![2011100414111814.jpg][]![2011100414121056.jpg][]

这样整个区间便已经有序了。

从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R\[1...n\]中选择最大记录，需比较n-1次，然后从R\[1...n-2\]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序，不适合记录较少的排序。

堆排序的算法使用的工具类：

class ArrayUtils 
    {
       public static void printArray(int[] array){
          System.out.println("{");
    	  for(int i=0;i<array.length;i++){
    	     System.out.println(array[i]);
    		 if(i<array.length-1){
    		     System.out.print(", ");
    		 }
    	  }
    	  System.out.println("}");
       }
       public static void exchangeElements(int[] array,int index1,int index2){
          int temp = array[index1];
    	  array[index1]=array[index2];
    	  array[index2]=temp;
       }
    }

主程序代码：

public class HeapSort
    {
    	public static void main(String[] args){
    	   int[] array={整数数组的元素};
    	   System.out.println("排序之前的顺序：");
    	   ArrayUtils.printArray(array);
    
    	   heapSort(array);
    
    	   System.out.println("排序后的顺序：");
    	   ArrayUtils.printArray(array);
    	}
    	public static void headSort(int[] array){
    	   if(array == null || array.length<=1){
    	       return;
    	   }
    	   buildMaxHeap(array);
    
    	   for(int i= array.length-1;i>=1; i--){
    	      ArrayUtils.exchangeElements(array,0,i);
    		  maxHeap(array, i, 0);
    	   }
    
    	}
    	private static void buildMaxHeap(int[] array){
    	   if(array == null || array.length<=1){
    	      return;
    	   }
    	   int half=array.length/2;
    	   for(int i=half; i>= 0; i--){
    	      maxHeap(array, array.length,i);
    	   }
    	}
    	private static void maxHeap(int[] array,int heapSize,int index){
    	   int left = index * 2 + 1;
    	   int right = index * 2+ 2;
    	   int largest = index;
    	   if(left < heapSize && array[left] > array[index]){
    		   largest = left;
    	   }
    	   if(right < heapSize && array[right] > array[largest]){
    	       largest = right;
    	   }
    	   if(index != largest){
    	      ArrayUtils.exchangeElements(array, index,largest);
    		  maxHeap(array,heapSize,largest);
    	   }
    	}
    }

**每天进步一点点，今天你进步了吗？ Day  Day  Up**

**于无声处听惊雷--------三石**

[2011100413554262.jpg]: /images/20220731/92fee7204e924cc290145d84890158ff.png
[2011100413563593.jpg]: http://pic002.cnblogs.com/images/2011/288799/2011100413563593.jpg
[2011100413573782.jpg]: http://pic002.cnblogs.com/images/2011/288799/2011100413573782.jpg
[2011100413581745.jpg]: /images/20220731/81aa3ed8dc3840de9cd3f1935dde5302.png
[2011100414001028.jpg]: /images/20220731/a57dc1445bd04a11a0cd9fd8d43502f2.png
[2011100414014182.jpg]: http://pic002.cnblogs.com/images/2011/288799/2011100414014182.jpg
[2011100414031854.jpg]: /images/20220731/81ce4e355c1e425aa6d0280aca0a2189.png
[2011100414052837.jpg]: http://pic002.cnblogs.com/images/2011/288799/2011100414052837.jpg
[2011100414061869.jpg]: http://pic002.cnblogs.com/images/2011/288799/2011100414061869.jpg
[2011100414071128.jpg]: http://pic002.cnblogs.com/images/2011/288799/2011100414071128.jpg
[2011100414083298.jpg]: http://pic002.cnblogs.com/images/2011/288799/2011100414083298.jpg
[2011100414092466.jpg]: http://pic002.cnblogs.com/images/2011/288799/2011100414092466.jpg
[2011100414100910.jpg]: /images/20220731/490512d00a2b4bef929bcf5ce0164cb4.png
[2011100414104814.jpg]: http://pic002.cnblogs.com/images/2011/288799/2011100414104814.jpg
[2011100414111814.jpg]: http://pic002.cnblogs.com/images/2011/288799/2011100414111814.jpg
[2011100414121056.jpg]: /images/20220731/c24e8c1c285240aa8e4a0e5e1da8cf86.png