排序算法_HeapSort
2024-08-27 19:31:53
大根堆排序的基本思想:
1) 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区;
2) 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,
由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key;
3) 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。
然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,
由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系 R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。
/*
大根堆排序的基本思想:
1) 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区;
2) 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,
由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key;
3) 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。
然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,
由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系 R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。
*/ /*
@brief:
已知L->r[s..len]中记录的关键字除L->r[s]之外均满足堆的定义,
本函数调整L->r[s]的关键字,使L->r[s..len]成为一个大顶堆
@param:
cur: 当前位置 s
len: 当前状态的最大值 m:当前堆的大小
*/
void HeapAdjust(SqList *L, int cur, int len)
{
int temp = L->r[cur];
for(int j = *cur; j <= len; j *= )// 沿关键字较大的孩子结点向下筛选(大根堆)
{
if(j < len && L->r[j] < L->r[j+])
++j; // j为关键字中较大的记录的下标
if(temp >= L->r[j])
break; /* 应插入在位置 cur 上 */ L->r[cur] = L->r[j];
cur = j;
}
L->r[cur] = temp; /* 插入 */
} /* 对顺序表L进行堆排序 */
void HeapSort( SqList* L )
{
for( int i = L->length/; i>; i--) /* 把L中的r构建成一个大根堆 */
HeapAdjust(L, i, L->length); for( int i = L->length; i>; i--)
{
swap(L, , i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
HeapAdjust(L, , i-); /* 将L->r[1..i-1]重新调整为大根堆 */
}
}
最新文章
- c#线程间操作UI-Invoke和BeginInvoke
- MVC UpdateModel的未能更新XXXXX的类型模型
- C#学习笔记之线程 - 同步上下文
- Table显示滚动条
- bzoj1576 3694
- 【原】ubuntu下Mysql的HA(corosync+pacemaker+drbd)
- linux安装Tesseract-OCR
- Spring该讲座
- ssh proxy配置
- Java的成员变量初始化
- 【完整项目】使用Scrapy模拟HTTP POST,获取完美名字
- BZOJ_1369_[Baltic2003]Gem_树形DP
- C#将Dll嵌入到EXE
- socketio server推送
- fastdfs+nginx+image_filter安装与生成缩略图
- ios输出想保留的整数位(占位符)
- NVIDIA NVML Driver/library version mismatch
- python3 安装 #zlib zlibmodule.c -I$(prefix)/include -L$(exec_prefix)/lib -lz
- mysql11---主键普通全文索引
- 016 ppp authentication