排序算法——堆排序-蒲公英云

排序算法——堆排序

堆排序是利用堆这种数据结构所设计的一种排序算法。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。升序采用大顶堆，降序采用小顶堆。大顶堆：arr[i] > >= arr[2i+1] && arr[i] >= arr[2i+2]；小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]。

例如一组数组{9,8,7,6,5,4,3,2,1}，先从最后一个非叶子节点（有子结点的结点）开始。也就是6（第一个非叶子节点：arr.length/2-1=9/2-1=3），再从左至右，从下至上进行调整。

第一个非叶子节点也就是6第一趟以6对子节点和父节点比较：子节点2和1都比6小，父节点8比6大，所以位置不发生改变。

第二个非叶子节点也就是7，第二趟以7对子节点和父节点比较：子节点4和3都比7小，父节点9比7大，所以位置不发生改变。

第三个非叶子节点也就是8，第三趟以8对子节点和父节点比较：子节点6和5都比8小，父节点9比8大，所以位置不发生改变。

第四个非叶子节点也就是9，第四趟以9对子节点和父节点比较：子节点8和7都比9小，没有父节点，所以位置不发生改变。

经过四趟后得到大顶堆{9,8,7,6,5,4,3,2,1}。如下图：
在这里插入图片描述
得到大顶堆后，将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换……

堆顶元素9与末尾元素1进行交换得到{1,8,7,6,5,4,3,2,9}，继续调整堆得到{8,6,7,2,5,4,3,1,9}，如下图：
在这里插入图片描述
堆顶元素8与末尾元素1进行交换得到{1,6,7,2,5,4,3,8,9}，继续调整堆得到{7,6,4,2,5,1,3,8,9}，如下图：

堆顶元素7与末尾元素3进行交换得到{3,6,4,2,5,1,7,8,9}，继续调整堆得到{6,5,4,2,3,1,7,8,9}，如下图：

堆顶元素6与末尾元素1进行交换得到{1,5,4,2,3,6,7,8,9}，继续调整堆得到{5,3,4,2,1,6,7,8,9}，如下图：
在这里插入图片描述
堆顶元素5与末尾元素1进行交换得到{1,3,4,2,5,6,7,8,9}，继续调整堆得到{4,3,1,2,5,6,7,8,9}，如下图：

堆顶元素4与末尾元素2进行交换得到{2,3,1,4,5,6,7,8,9}，继续调整堆得到{3,2,1,4,5,6,7,8,9}，如下图：

堆顶元素3与末尾元素1进行交换得到{1,2,3,4,5,6,7,8,9}，继续调整堆得到{2,1,3,4,5,6,7,8,9}，如下图：
在这里插入图片描述
堆顶元素2与末尾元素1进行交换得到{1,2,3,4,5,6,7,8,9}，完成升序排序。

Java代码实现：

public static void main(String[] args) { 
    int[] arr = { 9,8,7,6,5,4,3,2,1};
    sort(arr);
}
public static void sort(int []arr)//堆排序
{ 
    //构建大顶堆
    System.out.println("构建大顶堆——开始");
    for(int i=arr.length/2-1;i>=0;i--){ 
        //从第一个非叶子结点从下至上，从右至左调整结构
        adjustHeap(arr,i,arr.length);
        for (int l : arr) { 
            System.out.print(l+",");
        }
        System.out.println();
    }
    System.out.println("构建大顶堆——结束");
    //调整堆结构+交换堆顶元素与末尾元素
    int z=0;
    for(int j=arr.length-1;j>0;j--){ 
        int temp=arr[0];
        arr[0] = arr[j];
        arr[j] = temp;//将堆顶元素与末尾元素进行交换
        adjustHeap(arr,0,j);//重新对堆进行调整
        z++;
        System.err.println("第"+z+"趟：");
        for (int l : arr) { 
            System.out.print(l+",");
        }
        System.out.println();
    }
}
/** * 调整大顶堆 * @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;k<length;k=k*2+1){ //从i结点的左子结点开始，也就是2i+1处开始
        if(k+1<length && arr[k]<arr[k+1]){ //如果左子结点小于右子结点，k指向右子结点
            k++;
        }
        if(arr[k] >temp){ //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            arr[i] = arr[k];
            i = k;
        }else{ 
            break;
        }
    }
    arr[i] = temp;//将temp值放到最终的位置
}