首页 > 其他分享 >堆排序

堆排序

时间:2023-12-03 12:02:36浏览次数:24  
标签:10 arr int 元素 堆排序 largest

目录

本文主要介绍堆排序的原理、例子以及代码实现。

1.基本原理

堆排序(Heap Sort)是一种基于比较的排序算法,它的工作原理是首先将待排序的序列构造成一个大顶堆或小顶堆,然后交换堆顶元素和最后一个元素,然后将剩余元素重新调整为大顶堆或小顶堆,再交换堆顶元素和最后一个元素,如此反复,直到所有元素都排好序。

堆排序的步骤如下:

  1. 构造大顶堆(或小顶堆),对于每一个非叶子节点,保证其值大于(或小于)其子节点的值。
  2. 将堆顶元素与最后一个元素交换,然后将剩余元素重新调整为大顶堆(或小顶堆)。
  3. 重复步骤2,直到所有元素都排好序。

堆排序的时间复杂度为O(nlogn),空间复杂度为O(1)。

2.例子

假设我们有一个待排序的数组 [4, 10, 3, 5, 1],我们想要对其进行升序排序,可以使用堆排序,具体步骤如下:

  1. 首先,我们将数组构造成一个大顶堆。大顶堆是一种满足父节点的值大于或等于其子节点值的二叉树。构造大顶堆后,数组变为 [10, 5, 3, 4, 1]。
  2. 然后,我们将堆顶元素(即当前最大的元素10)与最后一个元素1交换位置,然后将剩余的元素(即除去最后一个元素的其他元素)重新调整为大顶堆。交换并调整后,数组变为 [5, 4, 3, 1] 和 [10]。
  3. 我们再次将堆顶元素5与最后一个元素1交换位置,然后将剩余的元素重新调整为大顶堆。交换并调整后,数组变为 [4, 1, 3]、[5, 10]。
  4. 重复上述步骤,直到所有元素都排好序,最终得到的数组为 [1, 3, 4, 5, 10]。

以上就是一个堆排序的具体例子。

3.代码实现

以下是堆排序的C语言实现:

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i=n-1; i>=0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

void printArray(int arr[], int n) {
    for (int i=0; i<n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array is \n");
    printArray(arr, n);
}

在这段代码中,heapify 函数用于构造大顶堆,heapSort 函数用于进行堆排序,swap 函数用于交换两个元素的值,printArray 函数用于打印数组。

标签:10,arr,int,元素,堆排序,largest
From: https://www.cnblogs.com/lanyangsh/p/17872767.html

相关文章

  • 堆排序
    堆是一种特殊的树形数据结构,它满足以下两个性质:完全二叉树:堆是一棵完全二叉树,即除了最底层之外,其他每一层的节点都被完全填满,且最底层的节点都尽可能地集中在左侧。堆属性:对于最大堆(大顶堆)来说,父节点的值总是大于或等于任何一个子节点的值;对于最小堆(小顶堆)来说,父节点的值总是小于或......
  • 堆以及堆的应用--堆排序
    堆定义:什么是堆?从堆的定义上我们可以看出,堆在物理结构上是一维数组,逻辑结构上,可以把堆理解为一棵完全二叉树,因为堆满足ki<=k2i+1,ki<=k2i+2(ki>=k2i+1,ki>=k2i+2),而我们了解对于完全二叉树,父结点和孩子结点存储在一维数组中有如下的下标关系:leftchild=parent*2+1rightchild=parent*2......
  • 在思想方面讨论堆排序(考研自用,按非递减方式排序)
     目录1.什么是排序2.关于堆排序的几个问题3.问题求解首先:排序的定义  拿冒泡排序(递增)来讲,在一个给定的数组序列中,若A[i+1]<A[i],则将其两个的数值进行交换,排好序的序列应该是递增的,类似于[1,2,3,4,5...];所以排序是在数组中进行的,物理......
  • 09-堆排序
    9.堆排序9.1完全二叉树在满二叉树路上的树。如果二叉树是完全二叉树,并且用数组表示,则:位置i的左右孩子节点为2i+1和2i+2位置i的父节点为(i-1)/29.2堆堆是完全二叉树堆有大根小根之分他的每颗子树都必须满足大根/小根堆9.3堆排序1.题目​ 堆排序......
  • 最大堆最小堆及堆排序
    堆这个数据结构在我大学的教材上没有讲解,但平时听说过堆排序什么的,无疑是要用到这个数据结构,所以本篇文章主要是总结下堆的概念和实现。堆概念在维基百科中,是这样定义堆的:堆(英语:Heap)是计算机科学中的一种特别的树状数据结构。若是满足以下特性,即可称为堆:“给定堆中任意节点P......
  • 堆排序
    时间复杂度为O(n)voidheapify(vector<int>&nums,intn,inti){intlargest=i;//假设为父节点intlson=i*2+1;intrson=i*2+2;//找到最大值if(lson<n&&nums[lson]>nums[largest])swap(nums[lson],nums[largest]);if(rson<......
  • 深入了解堆排序算法
    堆排序(HeapSort)是一种高效的、基于堆数据结构的排序算法,它具有稳定性和可预测的性能,适用于各种数据规模。本文将详细介绍堆排序的工作原理,提供示例和Python、Go、Java以及C语言的实现代码。堆排序的基本思想堆排序的核心思想是通过构建一个二叉堆,将待排序的数组转换为一个堆,然后反......
  • 并查集 堆排序 (9/10)
    并查集模板 注意查找到后查找的节点直接连接根节点#include<iostream>usingnamespacestd;constintN=100010;intp[N];//关键记住find函数intfind(inta){if(p[a]!=a)p[a]=find(p[a]);//不等于根节点就往头结点走,并且等于returnp[a];}intma......
  • Java 堆排序
    思路从最后的非叶子节点开始,从后向前构建一个堆(大顶堆/小顶堆);即最后的非叶子节点和其下的叶子节点构成一个大顶堆,然后再找前面一个非叶子节点继续此时根节点是最大的数据,然后将根节点和最后一位进行交换交换后,排除最后一位最大值,再从根节点开始构建大顶堆重复2,3步骤代码......
  • c++ 堆排序
    堆排序主要分为两个函数:1、构建堆2、元素调整#include<iostream>usingnamespacestd;voidmaxHeap(inttree[],intn,inti){ if(i>=n) return; intlchild=i*2+1; intrchild=i*2+2; intmax=i; if(lchild<n&&tree[lchild]>t......