八大排序算法(4/6)

本篇文章主要介绍了" 八大排序算法"，主要涉及到方面的内容，对于其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下： 八大排序算法标签：算法 查找和排序1. 插入排序—直接插入排序 ( 稳定的 O(nlogn) )基本思想: 将一个记录插入到已排序好的有序表中，从而得到一个...

堆的存储

一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2i+1和2i+2。如第0个结点左右子结点下标分别为1和2。

小顶堆的插入

// 新加入i结点  其父结点为(i - 1) / 2  void MinHeapFixup(vector<int> &a, int i)  
{  
    int j = (i - 1) / 2, temp = a[i];  
    while (j >= 0 && i != 0)  
    {   //把较大的子结点往下移动,替换它的子结点if (a[j] <= temp)  break; 
        a[i] = a[j];       
        i = j;  
        j = (i - 1) / 2;  
    }  
    a[i] = temp;  
}  
// 更简短的表达：void MinHeapFixup2(vector<int> &a, int i)  
{  
    for (int j = (i - 1) / 2; (j >= 0 && i != 0)&& a[i] > a[j]; i = j, j = (i - 1) / 2)  
        Swap(a[i], a[j]);  
}  
// 在最小堆中加入新的数据nNum  void MinHeapAddNumber(vector<int>, int nNum)  
{  
    a.push_back(nNum);  
    MinHeapFixup(a, a.size()-1);  
}  

堆的删除

堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。