C#中最优雅的冒泡排序方法是什么？

Question

这个能整理一下吗？

using System;  
class AscendingBubbleSort 
{     
    public static void Main()
    {
        int i = 0,j = 0,t = 0;
        int []c=new int[20];
        for(i=0;i<20;i++)
        {
            Console.WriteLine("Enter Value p[{0}]:", i);
            c[i]=int.Parse(Console.ReadLine());
        }
        // Sorting: Bubble Sort
        for(i=0;i<20;i++)
        {
            for(j=i+1;j<20;j++)
            {
                if(c[i]>c[j])
                {
                    Console.WriteLine("c[{0}]={1}, c[{2}]={3}", i, c[i], j, c[j]);
                    t=c[i];
                    c[i]=c[j];
                    c[j]=t;
                }
            }
        }
        Console.WriteLine("bubble sorted array:");
        // sorted array output
        for(i=0;i<20;i++)
        {
            Console.WriteLine ("c[{0}]={1}", i, c[i]);
        }
    }
}

- Kaiser Advisor

---

在我看来，“Elegant”（优美）和“Bubble Sort”（冒泡排序）不应该出现在同一个句子中。 - Sinan Ünür

如果这是一项作业任务，我会尽可能使代码变得丑陋，并在其中添加注释，比如“有意向代码中添加不良因素以反映我对该算法的厌恶”……老师会因你的原则而尊重你。 - Dan Tao

那不是冒泡排序... - Jon Skeet

@Ian：学习如何将算法描述转化为代码是很有价值的。 - Jon Skeet

我认为，大多数排序讨论都提到冒泡排序这个事实表明它相当相关，即使仅涉及排序方面。虽然它在商业环境中通常不适用，但这并不意味着它不值得讨论。 - Brian

Answer 1

你复制的那段不是冒泡排序。这是一种“暴力”排序，但并非冒泡排序。这里有一个通用的冒泡排序示例。它使用任意比较器，但允许您省略它，在这种情况下，相关类型将使用默认比较器。它将对任何（非只读）IList<T>实现进行排序，包括数组。阅读上面的链接（到维基百科），以更好地了解冒泡排序的工作原理。请注意，在每次循环中，我们从开头到结尾遍历，但仅将每个项与其相邻项进行比较。它仍然是一个O（n²）排序算法，但在许多情况下，它将比您给出的版本更快。

public void BubbleSort<T>(IList<T> list)
{
    BubbleSort<T>(list, Comparer<T>.Default);
}

public void BubbleSort<T>(IList<T> list, IComparer<T> comparer)
{
    bool stillGoing = true;
    while (stillGoing)
    {
        stillGoing = false;
        for (int i = 0; i < list.Count-1; i++)
        {
            T x = list[i];
            T y = list[i + 1];
            if (comparer.Compare(x, y) > 0)
            {
                list[i] = y;
                list[i + 1] = x;
                stillGoing = true;
            }
        }
    }
}

- Jon Skeet

---

@Ian：并不是每个来这里的人都在做作业。通过这个答案，他们可以找到他们想要的东西，并继续解决下一个问题。 :) - Sam Harwell

我（真的）很困惑，为什么你认为这个“更真实”的冒泡排序比原来的好。两者都是冒泡排序，只是优化不同。你的版本忽略了缩小范围。 - H H

@Henk：看一下维基百科的文章。那里描述的算法是否与原始算法相似？特别是，原帖中的代码比较任意一对数，违反了算法描述中“比较相邻项对”的部分。它肯定是一种暴力交换排序，但它不是冒泡排序。 - Jon Skeet

Jon，你是对的，我误读了 if(c[i]>c[j]) 这部分。我见过类似的循环，执行 if(c[j]>c[j+1]) 就是冒泡排序。 - H H

Answer 2

在C#中最优雅的排序方式是

Array.Sort( object[] )

除了作业问题中老师要求您实现非优雅的冒泡排序算法之外，这个方法将适用于任何地方。;-)

- Michael Dillon

Answer 3

总的来说，你的冒泡排序实现没有什么问题。如果我进行真正的代码审查，我会做出以下更改：

选择更具描述性的变量名

为什么你的数组只叫做c？

最小化变量作用域

你的所有变量都在函数顶部声明。除非这是一个作业要求或编码标准，否则更符合惯例的做法是将变量“靠近”它们被使用的位置声明，最好使它们的作用域尽可能小。

因此，消除第一行int i = 0, j = 0, t = 0;。内联声明循环计数器：

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

在使用它的地方声明临时变量：

                Console.WriteLine("c[{0}]={1}, c[{2}]={3}", i, c[i], j, c[j]);
                int t=c[i];
                c[i]=c[j];
                c[j]=t;

消除硬编码的数组边界。

改为：

for(i=0;i<20;i++)

变成这样：

for(i = 0; i < c.Length; i++)

- Juliet

Answer 4

大多数人不会费心去让冒泡排序变得优雅。然而，一般来说，我发现这样做：

for (int i = 0; i < items.Length; i++) {
    Item item = items[i];
    // do something with item
}

比起这样做，使用此方法既更优雅，也更易于维护：

Item item;
int i;
for (i = 0; i < items.Length; i++) {
    item = items[i];
    // do something with item
}

换句话说，在最小适用范围内声明变量。否则，在代码的其他位置使用i或item，然后再次在不应该使用它们的地方使用它们。

- Dan Tao

Answer 5

• 我会使用一个交换方法来交换这两个数组项。（如何编写交换方法的详细说明留作作业！）

• 你应该考虑当项目已经按顺序排列的情况。

• 你应该阅读有关插入排序的更多信息，以获取更高的分数 :-)

• 不要从键盘读取测试数据，看看是否可以学习如何使用nUnit。

- Ian Ringrose

---

Ian，我投了赞成票，因为你关于交换方法的观点是正确的。只是顺便说一下，有人添加了作业标签，但我提出这个问题是为了在工作中表达一个观点。 - Kaiser Advisor

Answer 6

我相信Jon Skeet提出的答案有所改进。每次循环后，迭代次数应该排除上一次迭代中处理的最后一个项目。因此，这是代码：

public void BubbleSortImproved<T>(IList<T> list)
{
    BubbleSortImproved<T>(list, Comparer<T>.Default);
}

public void BubbleSortImproved<T>(IList<T> list, IComparer<T> comparer)
{
    bool stillGoing = true;
    int k = 0;
    while (stillGoing)
    {
        stillGoing = false;
        //reduce the iterations number after each loop
        for (int i = 0; i < list.Count - 1 - k; i++)
        {
            T x = list[i];
            T y = list[i + 1];
            if (comparer.Compare(x, y) > 0)
            {
                list[i] = y;
                list[i + 1] = x;
                stillGoing = true;
            }
        }
        k++;
    }
}

- Alex Filipovici

Answer 7

我个人更喜欢这个：

string foo [] = new string[] {"abc", "def", "aaa", "feaf", "afea" };
Array.Sort(foo);

但这只是我的看法。排序是一个已经解决的问题，为什么要重新发明轮子呢？

- Randolpho

---

当我写这个答案的时候还没有那个。但是，很可能是作业。 - Randolpho

这实际上是错误的。如果您查看MS文档，Array.Sort使用的是快速排序而不是冒泡排序 :) - BFree

当问题特别询问冒泡排序时，这很重要。 - bcat

Answer 8

    public int[] BubbleSortInAesc(int[] input)
    {
        for (int i = input.Length; i > 0; i--)
        {
            for (int j = 0; j < i-1; j++)
            {
                if (input[j] > input[j + 1])
                {
                    //Swap the numbers
                    input[j] = input[j + 1]+input[j];
                    input[j + 1] = input[j] - input[j + 1];
                    input[j] = input[j] - input[j + 1];
                }
            }
        }
        return input;
    }

- Soosai Alexander

Answer 9

int[] array = {4,5,7,1,8};           

int n1, n2;
bool stillgoing = true;

while (stillgoing)
{
    stillgoing = false;
    for (int i = 0; i < (array.Length-1); i++)
    {                  
        if (array[i] > array[i + 1])
        {
            n1 = array[i + 1];
            n2 = array[i];

            array[i] = n1;
            array[i + 1] = n2;
            stillgoing = true; 
        }
    }
}
for (int i = 0; i < array.Length; i++)
{
    Console.WriteLine(array[i]);
}

从Jon Skeet那里得到了一些想法...

- Saad Qureshi

Answer 10

我认为你的算法还不错，但我会将排序功能放在一个单独的类和方法中。

- Maximilian Mayerl