数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)

简介: 数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)

选择排序

思路图解

代码(C语言)

void Selection_Sort(ElementType A[], int N)
{
    for(i = 0; i < N; i++)
    {
        MinPosition = ScanForMin(A,i,N-1);
        //从A[i]到A[N-1]中找最小元,并将其位置赋给MinPosition
        Swap( A[i], A[MinPosition] );
        //将未排序部分的最小元换到有序部分的最后位置
    }
}

时间复杂度

要提高时间效率,关键在于如何快速找到最小元,所以引入堆排序:

堆排序

算法1

先看第一种算法:

void Heap_Sort(ElementType A[], int N)
{
    BuildHeap( A );    /*  o(N)  */
    for( i = 0; i < N; i++)
        TmpA[ i ] = DeleteMin( A );    /*  O(logN)  */
    for( i = 0; i < N; i++)      /*   O(N)   */
        A[ i ] = TmpA[ i ];  
}

它的思路是:

先将序列A建成堆,然后重复地从堆中提取最小元素,并将其存储在临时数组中,实现了堆排序算法。最后,它将排序后的元素复制回原始数组A。

时间复杂度:

空间上,需要额外O(N)的内存占用,并且复制元素需要时间。

(在内存足够的情况下,一般没有问题;但如果在固定内存中使用这种算法的堆排序,就会出现无法完成排序的情况;例如:2GB满内存的情况下,要对该序列进行排序,那么实际就需要4GB的内存来进行堆排序。)

所以这种算法是不太好的。

算法2

void Heap_Sort(ElementType A[], int N)
{
    for(i = N/2 - 1; i >= 0; i--)
        PercDown(A ,i ,N);
    for(i = N - 1; i > 0; i--)
    {
        Swap(&A[0], &A[i] );
        PercDown(A ,0 ,i);
    }
}

算法2的思路是:

定理:

堆排序处理N个不同元素的随机排序的平均比较次数是

虽然堆排序给出最佳平均时间复杂度,但实际效果不如用Sedgewick增量序列的希尔排序。

 

堆排序代码

void Swap( ElementType *a, ElementType *b )
{
     ElementType t = *a; *a = *b; *b = t;
}
 
void PercDown( ElementType A[], int p, int N )
{ 
  /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
    int Parent, Child;
    ElementType X;
 
    X = A[p]; /* 取出根结点存放的值 */
    for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
        Child = Parent * 2 + 1;
        if( (Child!=N-1) && (A[Child]<A[Child+1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if( X >= A[Child] ) break; /* 找到了合适位置 */
        else  /* 下滤X */
            A[Parent] = A[Child];
    }
    A[Parent] = X;
}
 
void HeapSort( ElementType A[], int N ) 
{ /* 堆排序 */
     int i;
      
     for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 */
         PercDown( A, i, N );
     
     for ( i=N-1; i>0; i-- ) {
         /* 删除最大堆顶 */
         Swap( &A[0], &A[i] ); 
         PercDown( A, 0, i );
     }
}

end



目录
相关文章
|
12天前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
16 1
【数据结构】算法的复杂度
|
5天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
10 1
|
6天前
|
搜索推荐
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
|
9天前
|
存储 算法 大数据
Python算法高手的必修课:深入理解分治法、贪心算法、动态规划,让你的代码更智能!
【7月更文挑战第9天】在Python算法学习中,分治法(如归并排序)将大问题分解为小部分递归解决;贪心算法(如货币找零)在每步选择局部最优解尝试达到全局最优;动态规划(如斐波那契数列)通过存储子问题解避免重复计算,解决重叠子问题。掌握这三种方法能提升代码效率,解决复杂问题。
|
10天前
|
算法 安全 调度
逆天改命!Python高级数据结构堆(Heap)与优先队列,让你的算法效率飙升至宇宙级!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue实现了堆和优先队列,提供高效算法解决方案。堆用于Dijkstra算法求解最短路径,例如在图论问题中;PriorityQueue则在多线程下载管理中确保高优先级任务优先执行。这两个数据结构提升效率,简化代码,是编程中的强大工具。
12 0
|
10天前
|
算法 搜索推荐 Java
在Java中实现高效的算法与数据结构
在Java中实现高效的算法与数据结构
|
2天前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
|
4天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
17 7
|
1天前
|
算法
基于粒子群优化的图像融合算法matlab仿真
这是一个基于粒子群优化(PSO)的图像融合算法,旨在将彩色模糊图像与清晰灰度图像融合成彩色清晰图像。在MATLAB2022a中测试,算法通过PSO求解最优融合权值参数,经过多次迭代更新粒子速度和位置,以优化融合效果。核心代码展示了PSO的迭代过程及融合策略。最终,使用加权平均法融合图像,其中权重由PSO计算得出。该算法体现了PSO在图像融合领域的高效性和融合质量。