3

我有一些关于在 C# 中对数组进行排序的任务。我一直在尝试我能想到的一切——没有运气。

任务是通过已知的排序算法（插入、选择、冒泡、快速）对整数数组进行排序。问题是，我必须只对最小的M元素进行排序。

示例：我有一个包含 7 个元素的数组，2 9 8 3 4 15 11我需要对最小的 3 个元素进行排序，以便我的数组变为2 3 4 9 8 15 11.

请帮忙，我似乎无法在 SO 中找到任何东西，也无法通过 Google 找到任何东西。我不要求为我做所有的算法，我只需要其中一个来掌握这怎么可能。

E：谢谢你的想法。我已经查看了您的所有建议，并完成了这样的插入排序：

static int[] insertSort(int[] arr, out int swaps, out int checks) {
    int step = 0;
    swaps = 0;
    checks = 0;
    for (int i = 0; i < arr.Length; i++) {
        int min = arr[i], minind = i;
        for (int j = i + 1; j < arr.Length; j++) {
            checks++;
            if (arr[j] < min) {
                min = arr[j];
                minind = j;
            }
        }
        int temp = arr[minind];
        if (step < M) {
            for (int j = minind; j > i; j--) {
                swaps++;
                arr[j] = arr[j - 1];
            }
            arr[i] = temp;
            swaps++;
            step++;
        }
    }
    return arr;
}

交换和检查 - 我的应用程序的要求。

PS我多次看到SO不喜欢为某人做作业。这就是为什么我没有要求提供代码，我只是询问了如何实现这一点的想法。

再次感谢那些在这里帮助过我的人。

4

7 回答 7

3

没有看到你的实现，这很难回答。有很多方法可以做到这一点，而且大多数都是直截了当的。

不过，这里有一些想法：

  1. 创建一个“临时”数组，仅保存要排序的数字，对其进行排序，然后替换为原始数组（可能是次优解决方案）
  2. 使用 for 循环迭代您需要的次数（3 或其他）。这可能是最好的解决方案
  3. 在 SO 上发布您的代码，一些天真的人可能会给您一个解决方案，这样您就不必自己做功课。（这是一个懒惰且不合时宜的解决方案）
于 2012-11-26T15:53:11.240 回答
3

由于没有效率限制：

  1. 将 i 设置为 0。
  2. 在未排序的元素中寻找最小值。
  3. 将其插入位置 i，移动数组。
  4. 增量 i。
  5. 重复 M 次。

复杂度为 O(N * M)。

于 2012-11-26T15:55:57.337 回答
1

我认为这就是您要查找的内容，这是基于特定索引的数组升序排序示例。

        int startIndex=2;
        int endIndex=5;
        int[] elements=new int[7];
        elements[0]=2; 
        elements[1]=9;
        elements[2]=8;
        elements[3]=3;
        elements[4]=4;
        elements[5]=15;
        elements[6]=11;
        for (int a=startIndex-1;a<endIndex;a++){
            for(int b=startIndex-1;b<endIndex;b++){
                if (elements[a]<elements[b]){
                    int temp =elements[a];
                    elements[a]=elements[b];
                    elements[b]=temp;
                }
            }
        }
        for (int c=0;c<elements.Length;c++){
            Console.Write(elements[c]+",");
        }

如果要对它进行降序排序，只需将“<”更改为“>”。

于 2012-11-26T16:16:13.210 回答
0

你想看看你需要使用什么排序算法。例如，我们正在使用一个使用 for 循环的方法。大多数情况下你会看到这样的东西

for(int i = 0; i < arrayName.length(); i++) {}

在您的情况下，只需更改 for 循环的参数

for(int i = 0; i < M; i++) {}

其中 M 小于 arrayName.length(); 并且是您想要排序的从头开始的位置数。

阵列的其余部分，未触及，应该保持不变。

于 2012-11-26T15:54:11.730 回答
0

夫妇的事情。大多数排序算法使用 array.length 作为最大范围。你可以用 m 代替吗？IE

for (int i = 0; i < m; i++)

此外，您可以使用前 m 个字符的临时数组，对其进行排序，然后重新分配。

int[] temp; 
for (int i = 0; i < m; i++)
{
    temp[i] = realArray[i]; 
}
//sort, then
for (int i = 0; i < m; i++)
{
    realArray[i] = temp[i]; 
}
于 2012-11-26T15:57:36.043 回答
0

我会对整个数组进行排序并将其放入另一个数组中。

截断新数组以仅保留最小的 x 元素。从该数组中获取最大的数字（在您的示例中为 4）。

循环遍历初始数组并附加所有更高的数字。

输入：2 9 8 3 4 15 11
全部排序：2 3 4 8 9 11 15
截断：2 3 4

从此数组中获取最大值 (4)
循环遍历原始数组并追加

2 比 4 高吗？否
9 是否高于 4？是的，追加（我们现在有：2 3 4 9）
8 比 4 高吗？是的，追加（我们现在有：2 3 4 9 8）
3 比 4 高吗？否
4 是否高于 4？否
15 比 4 高吗？是的，追加（我们现在有：2 3 4 9 8 15）
11 比 4 高吗？是的，追加（我们现在有：2 3 4 9 8 11）

*这不是最有效的方法，如果您有重复的号码，可能会导致问题

于 2012-11-26T16:27:07.610 回答
-2

关于使用 LINQ 的任何处方？

int a[] = new int[] {2, 9, 8, 3, 4, 15, 11}; 
const int M = 5;
a = a.Take(M).OrderBy(e => e).ToArray(); // EDIT: Added .ToArray()
于 2012-11-26T16:02:21.500 回答