堆排序的最优算法复杂度为什么是O(nlgn)而不是O(n)呢？

Question

想象这样一个场景，如果堆中所有的元素都是相同的，那么每次调整堆的时候进行堆顶元素和堆尾元素交换之后，不需要进行堆的调整，之后的n个元素都这么做就好了，这样的排序时间复杂度不是O(n)吗

Answer 1

https://en.wikipedia.org/wiki...

就是 n，不要太过相信那些网上博文写的，另外代码不同，也可能导致 nlogn。比如维基上的，写的也是nlogn（是n，写错了）。

https://zh.wikipedia.org/zh/%...

/* C++ */
void max_heapify(int arr[], int start, int end) {
    
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { 
        if (son + 1 <= end && arr[son] < arr[son + 1]) 
            son++;
        if (arr[dad] > arr[son]) // 这里加个等号其实更好
            return;
        else { 
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

----------------------------------更改------------------------

被你带坑里了，最佳复杂度的数据是待排序数组就是目标数组（就是若升序排序，恰好数组是升序的），不是元素都是相同的，所以上面的也是n，不是nlogn。

Answer 2

只是省去了调整的时间，元素间的比较次数依然是nlgn