2

这个程序主要由我的教授负责，他留给我的是编写一个数组，该数组将对从文件中扫描的数组执行选择排序。

我在几乎完美运行的教科书的帮助下编写了代码。然而，输出是错误的，因为当数字 0 不在输入文件中时，输出中的前 5 个数字（应该按升序排序）都是 0。数组中的最后 5 个数字（最大的 5 个）也不存在。

输出还以原始、未排序的顺序列出了输入文件中的数字，并且没有显示错误。所有的数字都在那里。

我的方法代码：

private static void selectionSort( int arr[], int cnt)
    {

    int index;
    int minIndex;
    int minValue;

        for (cnt=0; cnt < (arr.length-1); cnt++)
        {
            minIndex = cnt;
            minValue = arr[cnt];
            for (index = cnt + 1; index< arr.length; index++)
            {
                if (arr[index] < minValue)
                {
                    minValue = arr[index];
                    minIndex = index;
                }
            }
            arr[minIndex] = arr[cnt];
            arr[cnt] = minValue;
        }
    }

这是输出：

原始兰特2：75 62 110 144 108 146 121 119 61 164 170 34 78 41 89 84 74 132 156 160 94 55 76 97 48

排序的 rands2：0 0 0 0 0 34 41 48 55 61 62 74 75 76 78 84 89 94 97 108 110 119 121 132 144

我是否犯了任何错误会导致这种情况发生？

4

1 回答 1

1

这似乎不是“延迟替换排序”又名选择排序的典型实现。

重要的是，在内循环完成对新的最低元素的扫描后，您需要查看是否找到了新的最低元素，如果是，则进行交换。您的算法缺少这个关键步骤。外部循环索引处的项目可能已经有序且不需要交换。

此外，如上所述，我不清楚您的排序算法为什么同时存储外部索引及其对应值。你只需要索引，你的集合中的元素不会去任何地方（除非它同时使用，也就是说....但是，整个'蜡球）。

这是延迟替换排序算法的伪代码：

Begin DELAYEDSORT
 For ITEM=1 to maximum number of items in list-1
    LOWEST=ITEM
    For N=ITEM+1 to maximum number of items in list
       Is entry at position N lower than entry at position LOWEST?
          If so, LOWEST=N
    Next N
    Is ITEM different from LOWEST
       If so, swap entry at LOWEST with entry in ITEM
 Next ITEM
End DELAYEDSORT

只是一些关于选择排序的不请自来的注释：

  • 它以 O(n^2) 的时间复杂度运行
  • 冒泡排序也以 O(n^2) 的时间复杂度运行，但在无序集合上，选择排序可以快 50%
  • 选择排序对于具有大量元素的集合非常昂贵
  • 如果执行交换的成本很高，选择排序在某些集合上可以更快，即使有大量元素（选择排序最小化排序集合所需的交换次数）
  • 选择排序是我编写的第一个排序算法。对我来说，它比冒泡排序更容易理解（该算法与我订购集合的方式非常一致）
  • 我所知道的唯一一种时间复杂度比选择排序更差的排序算法是所谓的“Stooge 排序”，它的时间复杂度约为 O(n^2.7)
于 2013-10-03T00:09:35.637 回答