本文主要向大家介绍了【云计算】排序算法之堆排序，通过具体的内容向大家展现，希望对大家学习云计算有所帮助。

1、堆排序

　　堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

2、堆排序基本思想及步骤

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

步骤一 ：构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

假设给定无序序列结构如下

A、此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。.

B、找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

C、这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

步骤二 ：将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

A：将堆顶元素9和末尾元素4进行交换

B 、重新调整结构，使其继续满足堆定义

C 、再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

再简单总结下堆排序的基本思路：

将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

代码实现

java方式一：

package sort;

import java.util.Arrays;

/**
 * ZhangJunJie
 * 2018/10/12 20:34
 * Describe：堆排序
 **/
public class HeapSort2 {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;ktemp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

运行结果：

java方式二：

package sort;

import java.util.Arrays;

/**
 * ZhangJunJie
 * 2018/10/12 19:26
 * Describe：堆排序
 **/
public class HeapSort {
    public static void main(String[] args) {
        int[] a = {2, 5, 9, 6, 1, 4, 8, 7, 12, 50};
        sort(a);
        System.out.println(Arrays.toString(a));
    }

    public static void sort(int[] a) {
        int len = a.length;
        for (int i = 0; i < len - 1; i++) {
            // 建堆
            buildHeap(a, len - 1 - i);
            // 交换堆顶元素和最后一个元素
            swap(a, 0, len - 1 - i);
        }
    }

    private static void swap(int[] a, int i, int j) {
        // TODO Auto-generated method stub
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;

    }

    public static void buildHeap(int[] a, int lastIndex) {
        // 从最后一个节点的父节点开始
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            // 当前节点存在子节点
            while (i * 2 + 1 <= lastIndex) {
                // 左节点下标值
                int l = i * 2 + 1;
                // 右结点下标值
                int r = i * 2 + 2;

                // 默认左节点为最大值
                int biggerIndex = l;
                // 存在右结点
                if (l < lastIndex) {
                    // 右结点的值比左节点大
                    if (a[r] > a[l]) {
                        biggerIndex = r;
                    }
                }
                // 当前节点的值比孩子节点的最小值小，交换
                if (a[i] < a[biggerIndex]) {
                    swap(a, i, biggerIndex);
                    // 把最大值下标赋给当前节点，进入下一次while循环判断
                    i = biggerIndex;
                } else {
                    break;
                }

            }

        }
    }
}

运行结果：

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标大数据云计算大数据安全频道！