堆排序

本文主要是介绍堆排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.堆排序的基本思想：

*用堆排序实现升序
* 其主要用到了大根堆的思想(先理解大根堆的思想,再进行堆排序)
*
* 因为大根堆可以快速找到最大数,所以只要每次都把这个最大数和最后一个数交换,那么依次进行：
* 就可以使得最大数被换到最后一个,倒二大的数换到倒二个,直到heapSize缩到0为止,则全部换完,完成排序

2.实现代码及解析：

 1 public static void HeapSort(int[] arr) 
 2     {
 3         if (arr == null || arr.length == 1) {
 4             return;
 5         }
 6         for (int i = 0; i < arr.length; i++) {
 7             HeapInsert(arr,i);//先将其调整为大根堆的形式
 8         }
 9         int heapSize = arr.length;
10         //接下来开始逐步取出这些元素
11         swap(arr,0,--heapSize);//因为arr[0]肯定是最大数,将其换到最后一个(注意是前--)
12         while (heapSize > 0) {
13             Heapify(arr,0,heapSize);//因为把某个小数换到第一个了,要进行大根堆的向下调整
14             swap(arr,0,--heapSize);//把最大数换到当前子数组的最后一个
15         }
16     }
17     
18     public static void HeapInsert(int[] arr,int index) 
19     {
20         while (arr[index] > arr[(index - 1) / 2]) {
21             swap(arr,index,(index - 1) / 2);
22             index = (index - 1) / 2;
23         }
24     }
25     
26     public static void Heapify(int[] arr,int index,int heapSize)
27     {
28         int left = 2 * index + 1;
29         while (left < heapSize) {
30             int largest = left;
31             if (left + 1 < heapSize && arr[left] < arr[left + 1]) {
32                 largest = left + 1;
33             }
34             if (arr[largest] <= arr[index])
35             {
36                 largest = index;
37             }
38             if (largest == index) {
39                 break;
40             }
41             swap(arr,largest,index);
42             index = largest;
43             left = 2 * index + 1;
44         }
45     }
46     
47     public static void swap(int[] arr,int a,int b) 
48     {
49         if (a != b) {
50             arr[a] = arr[a] ^ arr[b];
51             arr[b] = arr[a] ^ arr[b];
52             arr[a] = arr[a] ^ arr[b];
53         }
54     }

这篇关于堆排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！