首页 - 通讯 - 堆排序

堆排序

2023-10-07 20:42

总结

本章介绍排序算法中的堆排序。

目录
1.堆排序简介
2.堆排序的图形化描述
3。堆排序的时间复杂度和稳定性
4。堆排序的实现
4.1 堆排序 C 实现
4.2 堆排序 C++ 实现
4.3 堆排序 Java 实现

转载请注明出处:http://www.gsm-guard.net/skywang12345/p/3602162.html


更多排序和算法请参考:数据结构与算法系列目录

堆排序简介

堆排序是指利用堆的数据结构设计的排序算法。
所以,在学习堆排序之前,有必要了解一下堆!如果读者对堆不熟悉,建议先了解一下堆(建议大家通过二叉堆、左倾堆、倾斜堆、二项式堆或者斐波那契堆等文章来了解),然后再学习这一章。

我们知道堆分为“最大堆”和“最小堆”。最大堆通常用于“升序”排序,而最小堆通常用于“降序”排序。
由于最大堆和最小堆是对称的,所以只需要了解其中之一即可。本文将详细讲解最大堆实现的升序排序。

最大堆升序排序的基本思想:
①初始化堆:将序列a[1...n]构造成最大堆。
②交换数据:交换a[1]和a[n],使得a[n]为a[1...n]中的最大值;然后将 a[1...n-1] 调整为最大堆大小。接下来,交换a[1]和a[n-1],使得a[n-1]为a[1...n-1]中的最大值;然后 a[1...n-2 ] 重新缩放到最大值。依此类推,直到整个序列井然有序。

下面通过图文结合的方式分析堆排序的实现过程。注意,实现中使用了“数组实现的二进制堆的属性”。
第一个元素索引为0的情况:
性质1:i的左孩子索引为(2*i+1);
性质2:i的左子节点索引为 子节点索引为(2*i+2);
性质3:索引为i的父节点索引为floor((i- 1)/2);

例如,对于最大堆{110,100,90,40,80,20,60,10,30,50,70}:索引为0的左孩子全为1;索引为 0 的右子节点有 2;索引为 8 的父节点为 3。

堆排序图解说明

堆排序(升序)代码

/*
 *(最大)堆向下调整算法
 *
 * 注意:在数组实现的堆中,第N个节点的左孩子索引值为(2N+1),右孩子索引值为(2N+2)。
 * 其中,N为数组下标索引值。例如,数组中第一个数字对应的N是0。
 *
 * 参数说明:
 * a -- 待排序的数组
 * start -- 下降调整点的起始位置(一般为0,表示从第1个开始)
 * end -- 直到范围(通常是数组中最后一个元素的索引)
 */
void maxheap_down(inta[],int开始,int结束)
{
    int c = 开始; //当前节点的位置
    int l = 2*c + 1//左孩子的位置int tmp = a[c]; //当前节点的大小
    for (;l <= 结束;c=l,l=2*l+1)
    {
        // “l”是左孩子,“l+1”是右孩子
        if ( l < 结束 && a[l] < a[l+1])
            l++; // 选择左右子节点中较大的一个,即 m_heap[l+1]
        if (tmp >= a[l])
            //调整完成
        其他 //兑换价值
 {
            a[c] = a[l];
            a[l]= tmp;
        }
    }
}

/*
 * 堆排序(从小到大)
 *
 * 参数说明:
 * a -- 待排序的数组
 * n -- 数组的长度
 */
void heap_sort_asc(int a[], int n)
{
    int我;

    // 从(n/2-1) --> 0 依次遍历。遍历之后,得到的数组实际上是一个(最大)二叉堆。 
    对于(i = n / 2 - 1;i >= 0;i--)
        maxheap_down(a, i, n-1);//从最后一个元素开始调整顺序,不断缩小调整范围,直到第一个元素
    对于(i = n - 1;i > 0;i--)
    {
        // 交换a[0]和a[i]。交换后,a[i]是a[0...i]中最大的。 
        交换(a[0],a[i]);
        // 调整 a[0...i-1],使 a[0...i-1] 仍然是最大堆。
        // 即保证a[i-1]为a[0...i-1]中的最大值。 
        maxheap_down(a, 0, i-1);
    }
}

heap_sort_asc(a, n) 用于对数组a进行升序排序;其中 a 是数组,n 是数组的长度。
heap_sort_asc(a, n)的操作分为两部分:初始化堆和交换数据。
maxheap_down(a, start, end) 是最大堆的向下调整算法。

下面演示了对于a={20,30,90,40,70,110,60,10,100,50,80},n=11的heap_sort_asc(a, n)堆排序过程。以下是数组a对应的初始化结构体:

1 初始化堆

在堆排序算法中,要排序的数组首先必须转换为二叉堆。
下面演示将数组{20,30,90,40,70,110,60,10,100,50,80}转换为最大堆{110,100,90,40,80,20,60,10,30,50 ,70}一步。

1.1 i=11/2-1,即i=4

以上就是maxheap_down(a, 4, 9)的调整过程。 maxheap_down(a, 4, 9)的作用是降低a[4...9]; a[4] 的左子节点是 a[9],右子节点是 a[10]。调整时,选择左右孩子中较大的一个(即a[10])并与a[4]交换。

1.2 i=3

以上是maxheap_down(a, 3, 9)的调整过程。 maxheap_down(a, 3, 9)的作用是降低a[3...9]; a[3] 的左子节点是 a[7],右子节点是 a[8]。调整时,选择左右孩子中较大的一个(即a[8]),与a[4]交换。

1.3 i=2

1.4 i=1

1.5 i=0

调整完成后,得到最大堆。此时数组{20,30,90,40,70,110,60,10,100,50,80}变为{110,100,90,40,80,20,60,10,30,50,70}。

第 2 部分交换数据

将数组转换为最大堆后,必须交换数据,使数组成为真正的有序数组。
数据交换部分比较简单。下面仅给出将最大值放在数组末尾的示意图。

上图是n=10时交换数据的示意图。
当n=10时,首先交换a[0]和a[10],使得a[10]为a[0...10]之间的最大值;然后,调整 a[0... 9] 我们将其称为最大堆。交换后:a[10] 就可以了!
当n=9时,首先交换a[0]和a[9],使得a[9]为a[0...9]之间的最大值;然后,调整a[0...8] 让它称为max-heap。交换后:a[9...10] 就正常了!
...
依此类推,直到订购了 a[0...10]。

堆排序的时间复杂度和稳定性

堆排序时间复杂度
堆排序的时间复杂度为O(N*lgN)。
假设要排序的序列中有N个数字。一次遍历的时间复杂度是O(N)。我们需要遍历它多少次?
堆排序使用二叉堆进行排序。二叉堆是一棵二叉树。需要遍历的次数就是二叉树的深度。根据完全二叉树的定义,它的深度至少为lg(N+1)。最大是多少?由于二叉堆是完全二叉树,因此其深度最多不能超过lg(2N)。因此,一次遍历的时间复杂度为O(N),遍历次数在lg(N+1)到lg(2N)之间;因此,其时间复杂度为O(N*lgN)。

堆排序稳定性
堆排序是一种不稳定的算法,它不符合稳定算法的定义。当它交换数据时,它会比较父节点和子节点之间的数据。因此,即使有两个兄弟节点的值相等,它们在排序时的相对顺序也可能会改变。
算法稳定性——假设序列中有a[i]=a[j]。如果排序前,a[i]在a[j]前面;并且排序后,a[i]仍然在a前面。 [j] 前面。那么这个排序算法是稳定的!

堆排序实现

以下是堆排序的三种实现:C、C++和Java。这三种实现的原理和输出结果是相同的。每个实现都包括“对应最大堆的升序排序”和“对应最小堆的降序排序”。
堆排序C实现
实现代码(heap_sort.c)

 1 /**
 2  * 堆排序:C 语言
 3  *
 4  * @author skywang
 5  * @日期 2014/03/12
 6 */
 7
 8 #include 
 9
 10 // 数组长度
 11 #define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
 12 #define 交换(a,b) (a^=b,b^=a,a^=b)
 13
 14 /*
 15  *(最大)堆向下调整算法 16  *
 17  * 注:在数组实现的堆中,第N个节点的左孩子索引值为(2N+1),右孩子索引值为(2N +2)。
 18  * 其中,N为数组下标索引值。例如,数组中第一个数字对应的N是0。
 19  *
 20  * 参数说明:
 21  * a -- 待排序的数组
 22  * start -- 下降调整点的起始位置(一般为0,表示从第一个开始)
 23  * end -- 直到范围(通常是数组中最后一个元素的索引)
 24 */
 25 void maxheap_down(inta[], int开始,int结束)
 26 {
 27 int c = 开始; //当前节点的位置
 28 int l = 2*c + 1//左孩子的位置
 29 int tmp = a[c]; //当前节点的大小
 30 对于 (;l <= 结束;c=l,l=2*l+1)
 31  {
 32 // “l”是左孩子,“l+1”是右孩子 33 if (l < end && a[l] < a[l+1])
 34l++; // 选择左右子节点中较大的一个,即 m_heap[l+1]
 35 if (tmp >= a[l])
 36 断裂//调整完成
 37 其他 //兑换价值
 38  {
 39 a[c] = a[l];
 40 a[l]= tmp;
 41  }
 42  }
 43}
 44
 45 /*
 46  * 堆排序(从小到大)
 47  *
 48  * 参数说明:
 49  * a -- 待排序的数组
 50  * n -- 数组的长度
 51 */
 52 void heap_sort_asc(int a[],  intn)
 53 {
 54 inti;
 55 56 //从(n/2-1) --> 0依次遍历。遍历之后,得到的数组实际上是一个(最大)二叉堆。 
 57 对于 (i = n / 2 - 1; i >= 0;我--)
 58 maxheap_down(a, i, n-1);
 59
 60 //从最后一个元素开始调整顺序,不断缩小调整范围,直到第一个元素
 61 对于(i = n - 1;i > 0;i--)
 62  {
 63 // 交换 a[0] 和 a[i]。交换后,a[i]是a[0...i]中最大的。 
 64 交换(a[0], a[i]);
 65 // 调整a[0...i-1],使a[0...i-1]仍然是最大堆。
 66 // 即保证a[i-1]为a[0...i-1]中的最大值。 
 67 maxheap_down(a, 0, i-1);
 68  }
 69}
 70
71/*
 72  *(最小)堆向下调整算法
 73  *
 74  * 注:在数组实现的堆中,第N个节点的左孩子索引值为(2N+1),右孩子索引值为(2N +2)。 75  * 其中,N为数组下标索引值。例如,数组中第一个数字对应的N是0。
 76  *
 77  * 参数说明:
 78  * a -- 待排序的数组
 79  * start -- 下降调整点的起始位置(一般为0,表示从第一个开始)
 80  * end -- 直到范围(通常是数组中最后一个元素的索引)
 81 */
 82 void minheap_down(inta[], int开始,int结束)
 83 {
 84 int c = 开始; //当前节点的位置
 85 int l = 2*c + 1//左孩子的位置
2 
 87 对于 (;l <= 结束;c=l,l=2*l+1)
 88  {
 89 // “l”是左孩子,“l+1”是右孩子
 90 if ( l < end && a[l] > a[l+1])
 91l++; // 选择两个孩子中较小的一个 92 if (tmp <= a[l])
 93 断裂//调整完成
 94 其他 //兑换价值
 95  {
 96 a[c] = a[l];
 97 a[l]= tmp;
 98  }
 99  }
100}
101
102 /*
103  * 堆排序(从大到小)
104*
105  * 参数说明:
106  * a -- 待排序的数组
107  * n -- 数组的长度
108 */
109 void heap_sort_desc(int a[], intn)
110{
111inti;
112
113 // 从(n/2-1) --> 0依次遍历每一个。遍历完后,得到的数组实际上是一个最小堆。 
114 对于 (i = n / 2 - 1; i >= 0; i --)
115 minheap_down(a, i, n-1);
116
117 // 从最后一个元素开始调整顺序,不断缩小调整范围,直到第一个元素118 对于(i = n - 1;i > 0;i--119  {
120 // 交换a[0]和a[i]。交换后,a[i]是a[0...i]中最小的。 
121 交换(a[0], a[i]);
122 // 调整 a[0...i-1],使 a[0...i-1] 仍然是最小堆。
123 // 即保证a[i-1]为a[0...i-1]中的最小值。 
124 minheap_down(a, 0, i-1);
125}
126}
127
128 void main()
129{
130int我;
131 int a[] = {20,30,90,40, ,110,60,10,100,50,80};
132 int ilen = 长度(a);
133
134 printf("排序前:");
135 对于 (i=0; i)
136 printf("%d ", a[i]);
137 printf("\n");
138
139 heap_sort_asc(a, ilen); //升序
140 //heap_sort_desc(a, ilen); // 按降序排列 
141142 printf("排序后:");
143 对于 (i=0; i)
144 printf("%d ", a[i]);
145 printf("\n");
146 }
查看代码

堆排序C++实现
实现代码(HeapSort.cpp)

 1 /**
 2  * 堆排序:C++
 3  *
 4  * @author skywang
 5  * @日期 2014/03/11
 6 */
 7
 8 #include 
 9 使用 命名空间 std;
 10
 11 /*
 12  *(最大)堆向下调整算法
 13  *
 14  * 注:在数组实现的堆中,第N个节点的左孩子索引值为(2N+1),右孩子索引值为(2N +2)。
 15  * 其中,N为数组下标索引值。例如,数组中第一个数字对应的N是0。
 16  *
 17  * 参数说明: 18  * a -- 待排序的数组
 19  * start -- 下降调整点的起始位置(一般为0,表示从第一个开始)
 20  * end -- 直到范围(通常是数组中最后一个元素的索引)
 21 */
 22 void maxHeapDown(int* a,  int开始,int结束)
 23 {
 24 int c = 开始; //当前节点的位置
 25 int l = 2*c + 1//左孩子的位置
 26 int tmp = a[c]; //当前节点的大小
 27 对于 (;l <= 结束;c=l,l=2*l+1)
 28  {
 29 // “l”是左孩子,“l+1”是右孩子
 30 if ( l < 结束 && a[l] < a[l+1])
 31l++; // 选择左右子节点中较大的一个,即 m_heap[l+1]
 32 if (tmp >= a[l]) 33 断裂//调整完成
 34 其他 //兑换价值
 35  {
 36 a[c] = a[l];
 37 a[l]= tmp;
 38  }
 39  }
 40}
 41
 42 /*
 43  * 堆排序(从小到大)
 44  *
 45  * 参数说明:
 46  * a -- 待排序的数组
 47  * n -- 数组的长度
 48 */
 49 void heapSortAsc(int* a, intn)
 50 {
 51 int i,tmp;
 52
 53 //从(n/2-1) --> 0依次遍历。遍历之后,得到的数组实际上是一个(最大)二叉堆。 
 54 对于 (i = n / 2 - 1; i >= 0;我--)
 55 maxHeapDown(a, i, n-1);
 56 57 //从最后一个元素开始调整顺序,不断缩小调整范围,直到第一个元素
 58 对于 (i = n - 1; i > 0; i--)
 59  {
 60 // 交换 a[0] 和 a[i]。交换后,a[i]是a[0...i]中最大的。 
 61 tmp = a[0];
 62 a[0] = a[i];
 63 a[i] = tmp;
 64 // 调整a[0...i-1],使a[0...i-1]仍然是最大堆。
 65 // 即保证a[i-1]为a[0...i-1]中的最大值。 
 66 maxHeapDown(a, 0, i-1);
 67  }
 68}
 69
 70 /*
 71  *(最小)堆向下调整算法
 72  *
 73  * 注:在数组实现的堆中,第N个节点的左孩子索引值为(2N+1),右孩子索引值为(2N +2)。
 74  * 其中,N为数组下标索引值。例如,数组中第一个数字对应的N是0。
 75  *
 76  * 参数说明:
 77  * a -- 待排序的数组 78  * start -- 下降调整点的起始位置(一般为0,表示从第一个开始)
 79  * end -- 直到范围(通常是数组中最后一个元素的索引)
 80 */
 81 void minHeapDown(int* a,  int开始,int结束)
 82 {
 83 int c = 开始; //当前节点的位置
 84 int l = 2*c + 1//左孩子的位置
2 
 86 对于 (;l <= 结束;c=l,l=2*l+1)
 87  {
 88 // “l”是左孩子,“l+1”是右孩子
 89 if ( l < end && a[l] > a[l+1])
 90l++; // 选择两个孩子中较小的一个
 91 if (tmp <= a[l])
 92 断裂//调整完成 93 其他 //兑换价值
 94  {
 95 a[c] = a[l];
 96 a[l]= tmp;
 97  }
 98  }
 99}
100
101 /*
102  * 堆排序(从大到小)
103*
104  * 参数说明:
105  * a -- 待排序的数组
106  * n -- 数组的长度
107 */
108 void heapSortDesc(int* a, int n )
109{
110 int i,tmp;
111
112 // 从(n/2-1) --> 0依次遍历每一个。遍历完后,得到的数组实际上是一个最小堆。 
113 对于 (i = n / 2 - 1; i >= 0; i--)
114 minHeapDown(a, i, n-1);
115
116 // 从最后一个元素开始调整顺序,不断缩小调整范围,直到第一个元素
117 对于(i = n - 1;i > 0;i--118  {
119 // 交换a[0]和a[i]。交换后,a[i]是a[0...i]中最小的。 
120 tmp = a[0];121 a[0] = a[i];
122 a[i] = tmp;
123 // 调整 a[0...i-1],使 a[0...i-1] 仍然是最小堆。
124 // 即保证a[i-1]为a[0...i-1]中的最小值。 
125 minHeapDown(a, 0, i-1);
126}
127}
128
129 int main()
130{
131int我;
132 int a[] = {20,30,90,40, ,110,60,10,100,50,80};
133 int ilen = (sizeof(a)) / (sizeof(a[ 0]));
134
135 cout << "排序前:";
136 对于 (i=0; i)
137 cout << a[i] << " ";
138 cout << endl;
139
140 heapSortAsc(a, ilen); //升序
141 //heapSortDesc(a, ilen); // 按降序排列 
142
143 cout << "排序后:";144 对于 (i=0; i)
145 cout << a[i] << " ";
146 cout << endl;
147
148返回0149 }
查看代码

堆排序Java实现
实现代码(www.gsm-guard.net)

 1 /**
 2  * 堆排序:Java
 3  *
 4  * @author skywang
 5  * @日期 2014/03/11
 6 */
 7
 8 公共  堆排序 {
 9
 10 /*
 11  *(最大)堆向下调整算法
 12  *
 13  * 注:在数组实现的堆中,第N个节点的左孩子索引值为(2N+1),右孩子索引值为(2N +2)。
 14  * 其中,N为数组下标索引值。例如,数组中第一个数字对应的N是0。
 15  *
 16  * 参数说明: 17  * a -- 待排序的数组
 18  * start -- 下降调整点的起始位置(一般为0,表示从第一个开始)
 19  * end -- 直到范围(通常是数组中最后一个元素的索引)
 20 */
 21 公共 静态 空  maxHeapDown(int[] a, int开始, int结束) {
 22 int c = 开始; //当前节点的位置
 23 int l = 2*c + 1; // 左孩子的位置
 24 int tmp = a[c]; //当前节点的大小
 25
 26 for (;l <= end;c=l,l=2*l+1) {
 27 // “l”是左孩子,“l+1”是右孩子
 28 if (l < end && a[l] < a[l+1])
 29l++; // 选择左右子节点中较大的一个,即 m_heap[l+1] 30 if (tmp >= a[l])
 31 断裂//调整完成
 32 else { //兑换价值
 33 a[c] = a[l];
 34 a[l]= tmp;
 35  }
 36  }
 37  }
 38
 39 /*
 40  * 堆排序(从小到大)
 41  *
 42  * 参数说明:
 43  * a -- 待排序的数组
 44  * n -- 数组的长度
 45 */
 46 公共 静态 空  heapSortAsc(int[] a, int n ){
 47 int i,tmp;
 48
 49 //从(n/2-1) --> 0依次遍历。遍历之后,得到的数组实际上是一个(最大)二叉堆。  50 对于 (i = n / 2 - 1; i >= 0; i--)
 51 maxHeapDown(a, i, n-1);
 52
 53 //从最后一个元素开始调整顺序,不断缩小调整范围,直到第一个元素
 54 对于 (i = n - 1; i > 0; i--) {
 55 // 交换 a[0] 和 a[i]。交换后,a[i]是a[0...i]中最大的。 
 56 tmp = a[0];
 57 a[0] = a[i];
 58 a[i] = tmp;
 59 // 调整a[0...i-1],使a[0...i-1]仍然是最大堆。
 60 // 即保证a[i-1]为a[0...i-1]中的最大值。 
 61 maxHeapDown(a, 0, i-1);
 62  }
 63  }
 64
 65 /*
 66  *(最小)堆向下调整算法
 67  *
 68  * 注:在数组实现的堆中,第N个节点的左孩子索引值为(2N+1),右孩子索引值为(2N +2)。 69  * 其中,N为数组下标索引值。例如,数组中第一个数字对应的N是0。
 70  *
 71  * 参数说明:
 72  * a -- 待排序的数组
 73  * start -- 下降调整点的起始位置(一般为0,表示从第一个开始)
 74  * end -- 直到范围(通常是数组中最后一个元素的索引)
 75 */
 76 公共 静态 空  minHeapDown(int[] a, int开始, int结束) {
 77 int c = 开始; //当前节点的位置
 78 int l = 2*c + 1; // 左孩子的位置
 79 int tmp = a[c]; //当前节点的大小
 80
 81 for (;l <= end;c=l,l=2*l+1) {
 82 // “l”是左孩子,“l+1”是右孩子
 83 if ( l < end && a[l] > a[l+1])84l++; // 选择两个孩子中较小的一个
 85 if (tmp <= a[l])
 86 断裂//调整完成
 87 else { //兑换价值
 88 a[c] = a[l];
 89 a[l]= tmp;
 90  }
 91  }
 92  }
93
 94 /*
 95  * 堆排序(从大到小)
 96  *
 97  * 参数说明:
 98  * a -- 待排序的数组
 99  * n -- 数组的长度
100 */
101 公共 静态 void 堆排序( int[] a, int n) {
102 int i,tmp;
103
104 // 从(n/2-1) --> 0依次遍历每一个。遍历完后,得到的数组实际上是一个最小堆。 105 对于 (i = n / 2 - 1; i >= 0; i--)
106 minHeapDown(a, i, n-1);
107
108 // 从最后一个元素开始调整顺序,不断缩小调整范围,直到第一个元素
109 对于 (i = n - 1; i > 0; i--) {
110 // 交换a[0]和a[i]。交换后,a[i]是a[0...i]中最小的。 
111 tmp = a[0];
112 a[0] = a[i];
113 a[i] = tmp;
114 // 调整 a[0...i-1],使 a[0...i-1] 仍然是最小堆。
115 // 即保证a[i-1]为a[0...i-1]中的最小值。 
116 minHeapDown(a, 0, i-1);
117}
118}
119
120 public 静态 void main(String[] args ) {
121int我;
122 int a[] = {20,30,90,40,70,110,60,10,100,50,80};
123
124 System.out.printf("排序前:");
125 对于 (i=0; i)126 System.out.printf("%d", a[i]);
127 System.out.printf("\n");
128
129 heapSortAsc(a, a.length); //升序
130 //heapSortDesc(a, a.length); // 按降序排列 
131
132 System.out.printf("排序后:");
133 对于 (i=0; i)
134 System.out.printf("%d", a[i]);
135 System.out.printf("\n");
136}
137}
查看代码

他们的输出:

排序前:20 30 90 40 70 110 60 10 100 50 80
排序后:10 20 30 40 50 60 70 80 90 100 110