堆排序 - ONESRC

排序思路

堆排序（heap sort）是一种树形选择排序方法。他的特点是将R[1..n] (为配合二叉树的顺序存储结构，这里我们从1开始计算下标)看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中父结点和子节点之间的位置关系在无序区中选择最大（或者最小）的元素。

堆性质：

小根堆：父节点小于左右子节点

$$ k_i \leq k_{2i} \quad \& \quad k_i \leq k_{2i+1} $$

大根堆：父节点大于左右子节点

$$ k_i \geq k_{2i} \quad \& \quad k_i \geq k_{2i+1} $$

堆排序的排序过程与简单选择排序类似，只是挑选最大或者最小元素时采用的方法不同，这里采用大根堆，每次挑选最大元素归位。挑选最大元素是采用筛选（sift）的方法实现的。

排序算法

#include<stdio.h>
//筛选方法
void sift(int R[],int low,int high){
    int i=low,j=2*i;//R[j]是R[i]的左孩子
    int tmp =R[i];//记录下父节点，便于后续赋值,这里tmp可以优化掉，此处不再修改
    while(j<=high){//子节点在有效范围内时循环
        if(j<high&&R[j]<R[j+1])j++;//如果右子树存在，将j指向左右孩子中较大的那一个
        if(tmp<R[j]){//如果子节点较大，将子节点移动到父节点的位置，并将i和j跟着做出调整
            R[i]=R[j];
            i=j;
            j=2*i;
        }else break;
    }
    R[i]=tmp;//将被筛选的节点放入最后位置
}
void heap_sort(int R[],int n){
    int i,tmp;
    for(i=n/2;i>=1;i--){//构建初始堆，只有1-n/2有子节点，所以遍历其即可
        sift(R,i,n);
    }
    for(i=n;i>1;i--){//进行n-1趟，每次堆中元素少一个
        tmp=R[1];//将最后一个元素与R[1]交换
        R[1]=R[i];
        R[i]=tmp;
        sift(R,1,i-1);//在[1..i-1]里面，最大元素为R[1],[i..n]已经有序
    }
}
int main(void){
    int a[] = {0,0,1,2,3,4,5,6,7,8,9};//这里的有序数据是从a[1]开始的，a[0]不参与排序
    heap_sort(a, 10);
}

变换过程：

初始状态：
       0
   1       2
 3   4   5   6
7 8 9 0 0 0 0 0
-----------------------------------
low=5,high=10
       0
   1       2
 3   9   5   6
7 8 4 0 0 0 0 0
-----------------------------------
low=4,high=10
       0
   1       2
 8   9   5   6
7 3 4 0 0 0 0 0
-----------------------------------
low=3,high=10
       0
   1       6
 8   9   5   2
7 3 4 0 0 0 0 0
-----------------------------------
low=2,high=10
       0
   9       6
 8   4   5   2
7 3 1 0 0 0 0 0
-----------------------------------
low=1,high=10
       9
   8       6
 7   4   5   2
0 3 1 0 0 0 0 0
-----------------------------------
low=1,high=9
       8
   7       6
 3   4   5   2
0 1 9 0 0 0 0 0
-----------------------------------
low=1,high=8
       7
   4       6
 3   1   5   2
0 8 9 0 0 0 0 0
-----------------------------------
low=1,high=7
       6
   4       5
 3   1   0   2
7 8 9 0 0 0 0 0
-----------------------------------
low=1,high=6
       5
   4       2
 3   1   0   6
7 8 9 0 0 0 0 0
-----------------------------------
low=1,high=5
       4
   3       2
 0   1   5   6
7 8 9 0 0 0 0 0
-----------------------------------
low=1,high=4
       3
   1       2
 0   4   5   6
7 8 9 0 0 0 0 0
-----------------------------------
low=1,high=3
       2
   1       0
 3   4   5   6
7 8 9 0 0 0 0 0
-----------------------------------
low=1,high=2
       1
   0       2
 3   4   5   6
7 8 9 0 0 0 0 0
-----------------------------------
low=1,high=1
       0
   1       2
 3   4   5   6
7 8 9 0 0 0 0 0
-----------------------------------

我们做出一些微调，让下标从0开始

#include<stdio.h>
//筛选方法
void sift(int R[],int low,int high){
    int i=low,j=2*i+1;//微调
    int tmp =R[i];
    while(j<=high){
        if(j<high&&R[j]<R[j+1])j++;//微调
        if(tmp<R[j]){
            R[i]=R[j];
            i=j;
            j=2*i+1;//微调
        }else break;
    }
    R[i]=tmp;
}
void heap_sort(int R[],int n){
    int i,tmp;
    for(i=n/2-1;i>=0;i--){//微调
        sift(R,i,n-1);
    }
    for(i=n-1;i>0;i--){//微调
        tmp=R[0];//微调
        R[0]=R[i];
        R[i]=tmp;
        sift(R,0,i-1);//微调
    }
}
int main(void){
    int a[] = {0,1,2,3,4,5,6,7,8,9};
    heap_sort(a, 10);
}

算法分析

时间复杂度：

堆排序的时间主要是由建立初始堆和反复重建堆这两部分时间构成，它们均是通过用sift实现的。

n个节点的完全二叉树的高度

$$ h=\lfloor log_2n \rfloor+1 $$

在初始建立堆时，需要筛选调整的层为h-1~1层

其最好、最坏、平均时间复杂度均为O(nlog~2~n)

空间复杂度：

只使用了i，j，tmp三个辅助变量，与问题规模n无关。空间复杂度为O(1)

稳定性：

相同元素的相对位置可能改变，这是一种不稳定的排序方法。

复杂性：

较复杂

归位：

是，堆排序每趟产生的有序区一定是全局有序区。

本文由 ukuq 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jan 29, 2019 at 10:07 pm