【八大排序之选择排序---堆排序】_堆排序筛选法

堆排序：

时间复杂度为O(nlogn)
堆排序算法首先将所有元素(从未排序的数组)插入堆中，然后从堆的根节点依次删除，直到堆空为止。主要利用现有数组进行就地排序，具体做法是，当删除一个元素时，只是将数组中的第一个元素与最后一个元素交换位置而不是移除，同时减小堆的大小，即数组大小，然后再对第一个元素进行堆化。持续这个过程直到剩余元素为1.

在数组中直接进行堆排序，需要知道几个参数，即最后一个元素的位置是i=count-1，count为数组大小，则最后一个元素的双亲位置为(count-1)/2。任意一个节点j的左子节点位置l=2j+1，右子节点位置r=2j+2.

##代码如下：

public static void heap(int[] arr)
    {    //堆排序  1、先创建堆
        for(int i=(arr.length-1) / 2; i>=0; i--)  //从数组中间的值开始，先作为顶点，然后从右边到左边，从上到下调整堆结构
        {
            adjust(arr,i,arr.length);      //结束后形成了大顶堆
        }
 
        for(int i=arr.length-1 ; i>0 ; i--)   //交换堆顶元素与末尾元素后 再调整堆结构，构成大顶堆
        {
            int temp=arr[i];
            arr[i]=arr[0];
            arr[0]=temp;
 
            adjust(arr,0,i);   //将最大的那个放在末尾，不进行调整
        }
    }
    public static void adjust(int[] arr,int parent,int length)
    {      //2、调整堆结构(大顶堆)
        int father=arr[parent];  //把temp作为父节点
        int lChild=2*parent+1;  //父节点的左孩子
        while (lChild<length)   //如果左孩子小于数组长度，说明存在右孩子
        {
            int rChild=lChild+1; //右孩子比左孩子大一
            if(rChild<length && arr[lChild] < arr[rChild]) //如果右孩子依然存在，且右孩子值大于左孩子，则选右孩子节点
            {
                lChild++;   //左孩子结点始终指向大的节点
            }
            if(father >= arr[lChild])    //如果父节点大于孩子节点中较大的那个，则结束循环
            {
                break;
            }
            arr[parent]=arr[lChild];  //否则把孩子的值赋给父亲
            parent=lChild; //然后孩子当爹，往下筛选
            lChild=2*lChild+1;   //然后把左孩子换成新爹的左孩子
            arr[parent]=father;   //最后将值交换
        }
 
 
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40