当前位置:   article > 正文

堆排序_堆排序名词解释

堆排序名词解释

堆排序( Heap Sort )

堆排序要用到堆,那什么是堆呢?可以参考我的一博客什么是堆?

名词解释:堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法。

算法分析

堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。
平均性能:O(N*logN)。
其他性能:由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序,辅助空间为O(1)。
堆排序是不稳定的排序方法(当数组中有相等元素时,堆排序算法对这些元素的处理方法不止一种)。(排序的稳定性是指如果在排序的序列中,存在前后相同的两个元素的话,排序前 和排序后他们的相对位置不发生变化)。

一般步骤

1.将无序序列构建成一个堆,根据升序降序需求选择大顶堆(升序)或小顶堆(降序)。
2.将堆顶元素与末尾元素交换,将最大元素”沉”到数组末端。
3.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

将堆化为数组:
这里写图片描述

具体实现

代码:

void adjust(int arr[], int len, int index)//调整
{
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int maxIdx = index;
    if (left<len && arr[left] > arr[maxIdx]) maxIdx = left;
    if (right<len && arr[right] > arr[maxIdx]) maxIdx = right;  // maxIdx是3个数中最大数的下标
    if (maxIdx != index)                 // 如果maxidx被更新
    {
        swap(arr[maxIdx], arr[index]);//交换
        adjust(arr, len, maxIdx);       // 递归调整其他不满足堆性质的部分
    }

}
void heapSort(int arr[], int size)//堆排序
{
    for (int i = size / 2 - 1; i >= 0; i--)  // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
    {
        adjust(arr, size, i);
    }
    for (int i = size - 1; i >= 1; i--)
    {
        swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
        adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
    }
}

int main()
{
    int array[8] = { 5, 1, 6, 3, 8, 4, 7, 10 };
    heapSort(array, 8);
    /*for (auto it: array)
    {
        cout << it;
    }*/
    for (int i = 0; i <sizeof(array)/sizeof(array[0]); i++)
    {
        cout << array[i] <<" ";
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

结果

这里写图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/407360
推荐阅读
相关标签
  

闽ICP备14008679号