八大排序算法之堆排序

待我称王封你为后i 2022-05-30 02:38 197阅读 0赞

例如数组 a=\{19,3,60,7,1,15,33,24,45,32,79,85\};

排序思想：

1，堆排序也是选择排序的一种，根据堆得特性，每次把最大或最小值（本次以最大值为例）拿出来，按序排列；

2，堆排序是对普通选择排序的一种优化：如果是一个稳定堆，每次在选择最大值时，只用沿着二叉树其中一个分叉去交换即可，其他分叉符合堆得特性（因是排好的稳定堆），可以看作是稳定的，不用重排交换，省去了绝大多数的比较交换步骤，数组的数越多，分支越多，该算法的优势就越明显；

3，第一步，将数组初始化为稳定堆，稳定堆的特性：二叉树之父节点总比其左右孩子节点大！初始化稳定堆有很多方法，可以从堆顶向堆底方向初始化，也可以从堆底向堆顶方向排列初始化，也可以通过小三角递归调等完成初始化，本例为理解方便，选用从堆底向堆顶方向初始化，即，每次从小三角里找到最大值放在父节点，从最后一个小三角向前循环，第一遍，找到所有数的最大值，第二遍循环找到次最大值放在第二层节点上，依次类推，完成稳定堆得初始化；

4，初始化完稳定堆之后，将选出的最大值与最后一个数字交换放在数组的最后固定下来（以后循环不再用到此数字），此时除了顶部三角不稳定，下面都是稳定的，根据稳定堆得特性（父节点总是大于其左右孩子节点），从顶部往底部寻找交换，只沿着变动的那个分叉交换下去（只用单线一次循环即可），其他分叉不用动，交换完毕后，次最大数又被移到顶部，此时的堆仍然是一个稳定堆，再将顶部的最大值交换的数组的后面固定下来，重复这个步骤，依次类推，即可完成；

排序趟数：

1，初始化堆所用趟数：不确定，最大趟数是二叉树的层数，最小一趟

2，初始化堆后所用趟数：length-2次

排序原理：

稳定堆特性，二叉树排序，具体见上述排序思想

参考图片：

![Center][]

具体代码实现如下：

//主方法

**\[java\]**  [view plain][]  [copy][view plain]

1.  <span style="font-size:14px;">    public static void heapSort(int\[\] array)\{  
2.            
3.          int length=array.length;  
4.          initHeap(array, length);//初始化稳定堆  
5.          System.out.println("初始化堆后：" + Arrays.toString(array));  
6.          switchData(array,0,length-1);//交换第一个元素和本轮最后一个元素  
7.          //二叉树排序  
8.          for (int length2 = length - 1; length2 > 1 ; length2--) \{ //循环length - 2次  
9.              int index=0;  
10.             while(2 \* index + 1 < length2)\{ //只要有左孩子节点就可能产生交换，进入循环  
11.                 if (2 \* index + 2 < length2) \{ //左右孩子都有  
12.                     int max = index;  
13.                     if (array\[max\] < array\[2 \* index + 1\]) \{  
14.                         max = 2 \* index + 1;  
15.                     \}  
16.                     if (array\[max\] < array\[2 \* index + 2\]) \{  
17.                         max = 2 \* index + 2;  
18.                     \}  
19.                     if (max != index) \{  
20.                         switchData(array, index, max);  
21.                         index = max;  
22.                     \}else \{  
23.                         break;//max==index，表示节点最大，下面的堆都是稳定的，不用继续循环  
24.                     \}  
25.                       
26.                 \}  
27.                 if (2 \* index + 1 < length2 && 2 \* index + 2 >= length2) \{ //只有左孩子，没有右孩子  
28.                     if (array\[index\] < array\[2 \* index + 1\]) \{  
29.                         switchData(array, index, 2 \* index + 1);  
30.                     \}else \{  
31.                         break;//2 \* index + 1==index，表示节点最大，下面的堆都是稳定的，不用继续循环  
32.                     \}  
33.                 \}  
34.             \}  
35.             switchData(array, 0, length2 - 1);//交换第一个元素和本轮最后一个元素  
36.         \}  
37.     \}</span>

**\[java\]**  [view plain][]  [copy][view plain]

1.  <span style="font-size:14px;">//初始化堆；  
2.      public static void initHeap(int\[\] array,int length)\{  
3.            
4.          int high=length-1;  
5.          boolean isChange=false;  
6.          for(int k=(high-1)/2;k >= 0;k--)\{  
7.              //找到最后一个父节点  
8.              int left=2\*k+1;  
9.              int right=left+1;  
10.             //判断是否有节点  
11.             if(left<=high)\{  
12.                 int max=left;  
13.                 if(right<=high)\{  
14.                     if(array\[left\]<array\[right\])\{  
15.                         max=right;  
16.                     \}  
17.                 \}  
18.                 //将最大值跟父节点交换  
19.                 if(array\[max\] > array\[k\])\{  
20.                     isChange=true;  
21.                     switchData(array,max,k);  
22.                 \}  
23.             \}  
24.         \}  
25.         if(isChange)\{ //如果一次就能完成稳定堆的初始化，则不再需要递归调用，以达到优化算法的目的  
26.             initHeap(array,length);   
27.             System.out.println("递归："\+Arrays.toString(array));  
28.         \}  
29.           
30.     \}</span>

**\[java\]**  [view plain][]  [copy][view plain]

1.  //交换数组中两个数的方法，因为要多次用到，封装成一个方法；  
2.      public static void switchData(int\[\] array,int index1 ,int index2)\{  
3.          array\[index1\] ^= array\[index2\];  
4.          array\[index2\] ^= array\[index1\];  
5.          array\[index1\] ^= array\[index2\];  
6.      \}

[Center]: /images/20220530/77587f85a55b4206a50872be425bf0d4.png
[view plain]: http://blog.csdn.net/yxb_yingu/article/details/51336197#