计算堆排序对数组进行排序所需的步骤数

Question

所以我一直在尝试实现 "famous" 排序算法，看看它们对数组进行排序需要多少步骤。但是我被 Heapsort 困住了，我不知道如何正确计算步数。在我的实现中，对一个 128 长的数组进行排序平均需要 630 步——这比 nlog(n) 多得多。当用快速排序对同一个数组进行排序时，大约是 260-280，这几乎正好是 nlogn，这告诉我堆排序的计数器是错误的。这是我当前的代码：

    public static int heapify(double[] heap, int size, int index, bool asc, int steps)
    {
        int left = (index + 1) * 2 - 1;
        int right = (index + 1) * 2;
        int largest = 0;
        int stepCounter = steps;
        //For ascending sorting
        //Note: ideally there should be a maxHeapify for ascending and minHeapify for descending sorting seperately
        //however in this case it is easy to see what is happening
        if(asc)
        {
            if (left < size && heap[left] > heap[index])
            {
                largest = left;
            }
            else
            {
                largest = index;
            }

            if (right < size && heap[right] > heap[largest])
            {
                largest = right;
            }
        } else
        {//For descending sorting
            if (left < size && heap[left] < heap[index])
            {
                largest = left;
            }
            else
            {
                largest = index;
            }

            if (right < size && heap[right] < heap[largest])
            {
                largest = right;
            }
        }

        if (largest != index)
        {
            double temp = heap[index];
            heap[index] = heap[largest];
            heap[largest] = temp;
            stepCounter++;
            stepCounter = heapify(heap, size, largest, asc, stepCounter);
        }
        return stepCounter;
    }
    public static void heapSort(double[] heap, bool asc, int steps = 0)
    {
        int size = heap.Length;
        int i;
        int stepCounter = steps;
        //Build heap
        for (i = (size - 1) / 2; i >= 0; i--)
        {
            stepCounter = heapify(heap, size, i, asc, stepCounter);
        }

        for(i = heap.Length - 1; i > 0; i--)
        {
            double temp = heap[i];
            heap[i] = heap[0];
            heap[0] = temp;
            size--;
            stepCounter = heapify(heap, size, 0, asc, stepCounter);
        }
        Console.WriteLine("Heap sort has taken {0} steps", stepCounter);
    }

谢谢。明确一点：我最后只想要一个语句，打印所有步骤的数量，而不是每个 2-3 个步骤的大量消息。

编辑：我像这样更改了代码：

    public static int heapify(double[] heap, int size, int index, bool asc, int steps)
    {

        int stepCounter = 0;

        if (largest != index)
        {
            double temp = heap[index];
            heap[index] = heap[largest];
            heap[largest] = temp;
            stepCounter++;
            heapify(heap, size, largest, asc, stepCounter);
        }
        return stepCounter;
    }
    public static void heapSort(double[] heap, bool asc, int steps = 0)
    {
        int stepCounter = steps;
        //Build heap
        for (i = (size - 1) / 2; i >= 0; i--)
        {
            stepCounter += heapify(heap, size, i, asc, stepCounter);
        }

        for(i = heap.Length - 1; i > 0; i--)
        {
            double temp = heap[i];
            heap[i] = heap[0];
            heap[0] = temp;
            size--;
            stepCounter += heapify(heap, size, 0, asc, stepCounter);
        }
        Console.WriteLine("Heap sort has taken {0} steps", stepCounter);
    }

（删除不相关位）。这样，对于 128 个长度的数组，我平均得到 160-170，对于长度约为 1000 的数组，我得到大约 1300 步。我认为这听起来很合理。谢谢@jdweng

Answer 1

但是我被 Heapsort 困住了，我不知道如何正确地计算步数。在我的实现中，对一个 128 长的数组进行排序平均需要 630 步——这比 nlog(n) 多得多。当用快速排序对同一个数组进行排序时，它大约是 260-280，几乎正好是 nlogn，这告诉我堆排序的计数器是错误的。

这段话表示您不理解big-O符号。

当我们说 f(n) = O(g(n)) 时，我们的意思是存在一个常数 k 和一个 N 使得如果 N < n 则 |f(n)| < k |g(n)|。换句话说，"the growth pattern is no worse than g(n)"。它没有提到常数。与小数字的性能无关。

现在堆排序和快速排序都是O(n log(n))。但是它们有不同的常数。快速排序之所以得名，是因为它平均比合并排序和快速排序等替代方法快得多。您看到的持续差异反映了这一点。

但在 n 上收集数个值和图表的数据 f(n)/(n log(n))。

计算堆排序对数组进行排序所需的步骤数

Count number of steps heap sort takes to sort an array

c#

sorting

algorithm

heap

heapsort