堆排序问题

Question

我现在正在研究堆排序。到目前为止，我的代码输出错误。例如，我输入了 4 3 5 2 1，我输入的第一个数字始终位于最后一个索引上。输出将为 1 2 3 5 4。任何想法我的代码有什么问题。

    int[] nums = new int[100];
    int SizeNum;
    int x;
    int currentPass;
    int nPass = 1;

    private void ExeButton_Click(object sender, EventArgs e)
    {
            nPass = 1;
            string[] numsInString = EntNum.Text.Split(' ');   //split values in textbox
            for (int j = 0; j < numsInString.Length; j++)
            {
                nums[j] = int.Parse(numsInString[j]);
            }
            if (SizeNum == numsInString.Length)
            {
                SortArray(currentPass);
                ResultText.AppendText("\n\n");
            }
        }
    }

    public void SortArray(int currentPass)
    {
        int i;
        int temp;
        for (i = (SizeNum / 2) - 1; i >= SizeNum; i--)
            {
                siftDown(i, x, currentPass + 1);
            }

            for (i = SizeNum - 1; i >= 1; i--)
            {
                temp = nums[0];
                nums[0] = nums[i];
                nums[i] = temp;
                siftDown(0, i - 1, currentPass + 1);
                Display(currentPass);
            }
            Display(currentPass); 
        }        

    public void siftDown(int root, int bottom, int currentPass)
    {
        bool done = false;
        int maxChild;
        int temp;

        while ((root * 2 <= bottom) && (!done))
        {
            if (root * 2 == bottom)
                maxChild = root * 2;
            else if (nums[root * 2] > nums[root * 2 + 1])
                maxChild = root * 2;
            else
                maxChild = root * 2 + 1;
            Display(currentPass);
            if (nums[root] < nums[maxChild])
            {
                temp = nums[root];
                nums[root] = nums[maxChild];
                nums[maxChild] = temp;
                root = maxChild;
            }                
            else
            {
                done = true;
            }             
        }
        Display(currentPass);
    }

    public void Display(int currentPass)
    {
        int i;
        String numbers = "";
        ResultText.AppendText("Pass " + nPass + ":    ");
        for (i = 0; i < SizeNum; i++)
        numbers += nums[i].ToString() + " , ";
        ResultText.AppendText(numbers + "\n");
        nPass++;
    }

Answer 1

问题出在这一行：

if (SizeNum == numsInString.Length)

由于 SizeNum 字段未初始化，其值为默认值，即 0。
因此，当您插入 "5 4 3 2 1" 时，numsInString.Length 将等于 5，然后该 if 中的代码未达到。
事实上，如果您设置 SizeNum = numsInString.Length 您的代码似乎可以工作。

无论如何，正如其他用户所指出的，如果您使用的是 Visual Studio 或 Sharp-Develop 这样的 IDE，您应该使用调试器，它对于查找代码问题确实非常有帮助。

以下是 Visual Studio 的操作方法： http://msdn.microsoft.com/ en-us/library/sc65sadd.aspx

Answer 2

SortArray 的第一个 for 循环应该是

for (i = (SizeNum / 2) - 1; i >= 0; i--)

This isbuilding you heap。您将从子级的第二层到最后一层开始，一直移动到树的顶部节点。