常用算法笔记 > 常用排序算法
堆排序

1、堆排序时间复杂度

堆排序的时间复杂度是O(N*lgN)

假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历多少次呢?

堆排序是采用的二叉堆进行排序的,二叉堆就是一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的定义,它的深度至少是lg(N+1)。最多是多少呢?由于二叉堆是完全二叉树,因此,它的深度最多也不会超过lg(2N)。因此,遍历一趟的时间复杂度是O(N),而遍历次数介于lg(N+1)和lg(2N)之间;因此得出它的时间复杂度是O(N*lgN)。

2、堆排序稳定性

堆排序是不稳定的算法,它不满足稳定算法的定义。它在交换数据的时候,是比较父结点和子节点之间的数据,所以,即便是存在两个数值相等的兄弟节点,它们的相对顺序在排序也可能发生变化。



3、堆排序原理说明

这里,必须引入一个完全二叉树的概念,然后过渡到堆的概念。


上图,就是一个完全二叉树,其特点在于:

  1. 从作为第一层的根开始,除了最后一层之外,第N层的元素个数都必须是2的N次方;第一层一个元素,第二层4个,第三层8个,以此类推。

  2. 而最后一行的元素,都要紧贴在左边,换句话说,每一行的元素都从最左边开始安放,两个元素之间不能有空闲,具备了这两个特点的树,就是一棵完全二叉树。

那么,完全二叉树与堆有什么关系呢?

我们假设有一棵完全二叉树,在满足作为完全二叉树的基础上,对于任意一个拥有父节点的子节点,其数值均不小于父节点的值;这样层层递推,就是根节点的值最小,这样的树,称为小根堆。

同理,又有一棵完全二叉树,对于任意一个子节点来说,均不大于其父节点的值,如此递推,就是根节点的值是最大的,这样的数,称为大根堆。


如上图,左边就是大根堆;右边则是小根堆,这里必须要注意一点,只要求子节点与父节点的关系,两个节点的大小关系与其左右位置没有任何关系。

明确下大根堆,小根堆的概念,继续说堆排序。

现在对于堆排序来说,我们先要做的是,把待排序的一堆无序的数,整理成一个大根堆,或者小根堆,下面讨论以大根堆为例子。

给定一个列表array=[16,7,3,20,17,8],对其进行堆排序(使用大根堆)。

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

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

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

此处必须注意,我们把6和9比较交换之后,必须考量9这个节点对于其子节点会不会产生任何影响?因为其是叶子节点,所以不加考虑;但是,一定要熟练这种思维,写代码的时候就比较容易理解为什么会出现一次非常重要的交换了。

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

在真正代码的实现中,这时候4和9交换过后,必须考虑9所在的这个节点位置,因为其上的值变了,必须判断对其的两个子节点是否造成了影响,这么说不合适,实际上就是判断其作为根节点的那棵子树,是否还满足大根堆的原则,每一次交换,都必须要循环把子树部分判别清楚。

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

牢记上面说的规则,每次交换都要把改变了的那个节点所在的树重新判定一下,这里就用上了,4和9交换了,变动了的那棵子树就必须重新调整,一直调整到符合大根堆的规则为截。

此时,我们就将一个无序序列构造成了一个大顶堆。

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

a.将堆顶元素9和末尾元素4进行交换

这里,必须说明一下,所谓的交换,实际上就是把最大值从树里面拿掉了,剩下参与到排序的树,其实只有总结点的个数减去拿掉的节点个数了。所以图中用的是虚线。

b.重新调整结构,使其继续满足堆定义

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

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

golang代码:

package main

import "fmt"

func HeapSort(arr []int) {
   length := len(arr)
   startNode := length/2 -1
   //构造大顶堆
   for k := startNode; k >= 0;k-- {
      buildHeap(arr, k)
   }
   //依次从堆顶取出最大的元素放到末尾.
   lastNodePos := length - 1
   for ;lastNodePos > 0;lastNodePos-- {
      swap(arr, 0, lastNodePos)
      buildHeap(arr[0:lastNodePos], 0)
   }
}

func buildHeap(arr []int, currentPos int) {
   length := len(arr)
/***
结束条件 
1. 当前节点是没有左右子节点,也就是当前节点是叶子节点
2. 当前节点大于左右节点. 这里需要结合HeapSort方法的第一个
循环在buildHeap过程中 采用从最深的的非叶子节点构造,所以除了
当前节点他的左右节点都已经是最大堆了,所以当当前节点大于左右
节点的没有必要在继续循环.
 */
   for currentPos*2+1 < length {
      leftChildPos := currentPos*2 + 1
      rightChildPos := leftChildPos + 1
      maxPos := leftChildPos
      //选择左右子节点中最大的节点
      if rightChildPos < length {
        if arr[leftChildPos] < arr[rightChildPos] {
           maxPos = rightChildPos
        }
      }

      if arr[maxPos] > arr[currentPos] {
         swap(arr, maxPos, currentPos)
         currentPos = maxPos
      } else {
         break
      }
   }
}

func swap(s []int, i int, j int) {
   s[i], s[j] = s[j], s[i]
}

func main() {
   items := []int{8, 2, 9, 1, 3, 7, 22}
   HeapSort(items)
   fmt.Println(items)
}


c++代码实现:

#include <iostream>

void swap(int *&arr,int i,int j){
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
} 

void buildHeap(int *&arr,int i,int n){
//以arr[i]为根建立堆(升序大顶堆) 
    int temp=arr[i]; 
    for(int k=2*i+1;k<n;k=2*k+1){
        if(k+1<n&&arr[k]<arr[k+1]) {
            k++;
        }
        if(temp<arr[k]){
            arr[i]=arr[k];
            i=k;
        }else{
            break;  
        }
    }
    arr[i]=temp;
}
void heapSort(int arr[],int n){
    int i,j;
    for(i=n/2-1;i>=0;i--){
    //建好了堆 
        buildHeap(arr,i,n);
    }
    for(j=n-1;j>=0;j--){
        swap(arr,j,0);
        buildHeap(arr,0,j);
    } 
}
int main(int argc, char** argv) {
 int arr[]={4,12,35,98,4,44,58,13,15};
 heapSort(arr,9);
 for(int i=0;i<9;i++){
   printf("%d ",arr[i]);
 }
 return 0;
}