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

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

选择排序

思路图解

代码(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



目录
相关文章
|
20天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
63 4
|
17天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
16天前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
16天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
43 1
|
25天前
|
存储 缓存 算法
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
159 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
26 1
|
18天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
40 5
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。

热门文章

最新文章