亲宝软件园·资讯

展开

Java堆排序与时间复杂度

淡沫初夏Zz 人气:0

一、堆排序

1、什么是堆排序

(1)堆排序:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

(2)堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

2、堆排序思想

(1)将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆

(2)将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端

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

3、代码实现

import java.util.Arrays;
public class Sort {
     //将任意数组进行原地堆排序
    public static void heapSort(int[] arr) {
        //把数组调整为最大堆,从最后一个非叶子节点开始下沉
        for (int i = (arr.length-1-1)/2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        //将堆顶元素和最后一个元素交换
        for (int i = arr.length-1; i > 0 ; i--) {
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }
   //下沉操作
    private static void siftDown(int[] arr, int i, int n) {
        while ((2 * i)+1 < n){
            int j = (2 * i) + 1;
            if(j+1<n && arr[j+1]>arr[j]){
               j = j+1;
            }
            if(arr[i] >= arr[j]){
                break;
            }else{
                swap(arr,i,j);
                i = j;
            }
        }
    }
     public static void main(String []args){
        int []arr = {7,6,7,11,5,12,3,0,1};
        System.out.println("排序前:"+ Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:"+Arrays.toString(arr));
    }
}

运行截图:

二、时间复杂度分析

1、初始化建堆

初始化建堆只需要对二叉树的非叶子节点由下至上,由右至左选取非叶子节点来调用adjusthead()函数。那么倒数第二层的最右边的非叶子节点就是最后一个非叶子结点。

 假设高度为k,则从倒数第二层右边的节点开始,这一层的节点都要执行子节点比较然后交换;倒数第三层呢,则会选择其子节点进行比较和交换,如果没交换就可以不用再执行下去了。高层也是这样逐渐递归。

 那么总的时间计算为:s = 2^( i - 1 ) * ( k - i );其中 i 表示第几层,2^( i - 1) 表示该层上有多少个元素,( k - i) 表示子树上要下调比较的次数。

S = n - log(n) -1,所以时间复杂度为:O(n)

2、排序重建堆

每次重建意味着有一个节点出堆,所以需要将堆的容量减一。adjustheap()函数的时间复杂度k=log(n),k为堆的层数。所以在每次重建时,随着堆的容量的减小,层数会下降,函数时间复杂度会变化。重建堆一共需要n-1次循环,每次循环的比较次数为log(i),则相加为:log2+log3+…+log(n-1)+log(n)≈log(n!)。

所以时间复杂度为O(nlogn)

3、总结

初始化建堆的时间复杂度为O(n),排序重建堆的时间复杂度为nlog(n),所以总的时间复杂度为O(nlogn),空间复杂度为O(1)。

加载全部内容

相关教程
猜你喜欢
用户评论