堆排序:顾名思义,将待排序数组构造成一个堆,将堆顶的元素取出,重复该过程直到堆中只有一个元素

特点

将数组构造成一棵完全二叉树,对于递增排序将完全二叉树转换成最大堆(每个节点的值都大于其子节点的值),对于递减排序将完全二叉树转换成最小堆(每个节点的值都小于其子节点),然后将树的根节点的值与其最后一个节点的值互换,认为堆的节点数量减一,重复构建最大堆,值互换的过程,直到堆的大小为一

基本逻辑

  1. 将数组解释为一棵完全二叉树,将树转化为最大(或最小)堆
  2. 将最大堆的根节点的值与堆的最后一个节点互换,然后认为堆的大小减一
  3. 互换后堆的状态被改变,调整堆使其满足最大堆的性质,在调整时只需要调整值改变的节点其余节点不需要调整,因此可以重复获得值被交换的节点,进行判断,直到到了叶子节点
  4. 当堆的大小为一时排序完成

该算法的关键在于将数组构建成最大堆,在每次节点值交换的时候都会导致最大堆的结构的破坏,因此需要在每次交换值后去重新构建最大堆,每次只需要把改变的节点相关的子节点进行构建,然后重复此操作直到完成排序

在写这个算法的时候,老是超时,但是看别人写的却不会超时,苦思冥想,然后发现我在交换根节点的值的时候是重新调整了整个堆的所有节点,但是实际并不需要怎么做,因为其它节点没变化。。。。

以递增排序为例


C语言实现

Leetcode上917.排序数组中测试通过(效率还行
Dsort_1

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    *returnSize=numsSize;
    int Len = numsSize - 1;
    int Fnode = (Len - 1) / 2;

    while (Fnode >= 0)
    {
        for (size_t i = Fnode; 2 * i + 1 <= Len;)
        {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int Max = (right <= Len && nums[right] > nums[left]) ? right : left;
            if (nums[Max] > nums[i])
            {
                nums[Max]=nums[Max]^nums[i];
                nums[i]=nums[Max]^nums[i];
                nums[Max]=nums[Max]^nums[i];
                i = Max;
            }
            else
            {
                break;
            }        
        }
        Fnode--;
    }

    while (Len)
    {
        nums[0]=nums[0]^nums[Len];
        nums[Len]=nums[0]^nums[Len];
        nums[0]=nums[0]^nums[Len];
        Len--;
        for (size_t i = 0; 2 * i + 1 <= Len;)
        {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int Max = (right <= Len && nums[right] > nums[left]) ? right : left;
            if (nums[Max] > nums[i])
            {
                nums[Max]=nums[Max]^nums[i];
                nums[i]=nums[Max]^nums[i];
                nums[Max]=nums[Max]^nums[i];
                i = Max;
            }
            else
            {
                break;
            }
        }    
    }
    return nums;
}

C++实现

Leetcode上917.排序数组中测试通过(效率还行
Dsort_2

vector<int> sortArray(vector<int>& nums)
{
    int Len = nums.size() - 1;
    int Fnode = (Len - 1) / 2;

    while (Fnode+1)
    {
        for (size_t i = Fnode; 2 * i + 1 <= Len;)
        {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int Max = (right <= Len && nums[right] > nums[left]) ? right : left;
            if (nums[Max] > nums[i])
            {
                swap(nums[Max], nums[i]);
                i = Max;
            }
            else
            {
                break;
            }        
        }
        Fnode--;
    }

    while (Len)
    {
        swap(nums[0], nums[Len]);
        Len--;
        for (size_t i = 0; 2 * i + 1 <= Len;)
        {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int Max = (right <= Len && nums[right] > nums[left]) ? right : left;
            if (nums[Max] > nums[i])
            {
                swap(nums[Max], nums[i]);
                i = Max;
            }
            else
            {
                break;
            }
        }    
    }
    return nums;
}
Last modification:April 15th, 2020 at 09:11 am