选择排序----堆排序----java实现

雨点打透心脏的1/2处 2022-07-21 00:26 218阅读 0赞

（1）小顶堆

假设有n个元素的序列，k0-kn,如果将这组数据排成一棵完全二叉树，则此树的特点是：树中所有节点的值都小于其左右节点的值，此树的根必然是最小的；

（2）大顶堆

假设有n个元素的序列，k0-kn,如果将这组数据排成一棵完全二叉树，则此树的特点是：树中所有节点的值都大于其左右节点的值，此树的根必然是最大的；

堆排序算法思想：

大顶堆的根节点一定是这组数据中最大的数，如果需要对一组数进行排序，则需要先将这组数据建成大（小）顶堆，然后接可以选择出这组数据中最大（小）的数。

第一趟先将0—n-1处的所有数据建成大顶堆，就可以选择出这组数据中最大的数；

第二趟将0-n-2处的所有数据建成大顶堆，就可以选择出这组数据中最大的数；

。。。。。。。

第k趟将0-n-k处的所有数据建成大顶堆，就可以选择出这组数据中最大的数；

堆排序的步骤分为两步：

（1）建堆；

从最后一个非叶子节点开始，比较该节点和其孩子节点中加大的那个节点的值，

如果较大的那个子节点的值大于父节点，则交换父节点和该子节点的值；

向前逐步调整直到根节点，保证每个节点的值都大于等于其左右子节点的值，一次建      堆完成

（2）把堆的根节点和当前数组的最后一个节点交换；

对于包含n个元素的数组而言，需要n-1次建堆，每次建堆的作用就是选出该堆的最大（小）值；

public class HeapSort
    {
       public void heapSort(int[] array)
       {
    	   //有n个元素进行n-1次建堆
    	   for (int i = 0; i < array.length-1; i++)
    	{
    		   bulidMaxHeap(array,array.length-1-i);//一次建堆
    		   swap(array,0,array.length-1-i);//交换堆顶和最后一个元素
    		   
    	}
       }
       private void bulidMaxHeap(int[]array,int lastIndex)
       {
    	   for (int i = (lastIndex - 1)/2; i >= 0; i--)//从最后一个非叶子节点到根节点进行一次建堆
    	{
    		int current = i;//保存当前正在判断的节点
    		while(2*current + 1 <= lastIndex)//当前节点有子节点
    		{
    			//保存左右节点中数值大的那个元素的索引
    			int biggerIndex = 2*current + 1;//当前节点的左节点的索引
    			if(biggerIndex < lastIndex)//当前节点有右节点
    			{
    				//若是右节点比左节点大，biggerIndex保存右节点的索引
    				if(array[biggerIndex+1] > array[biggerIndex])
    				{
    					biggerIndex++;
    				}
    			}
    			if(array[current] < array[biggerIndex])//如果当前节点小于它的子节点中较大的那个元素，将当前节点和简答的子节点交换
    			{
    				swap(array,current,biggerIndex);
    				current = biggerIndex;//交换后可能导致子节点和子节点的左右孩子大小不对，再进行whlie循环判断
    			}
    			else
    			{
    				break;
    			}
    		}
    		
    	}
       }
       private void swap(int[]array,int i,int j)
       {
    	   int temp = array[i];
    	   array[i] = array[j];
    	   array[j] = temp;
       }