万一添加破到冒泡排序阵列已经排序

我现在有一个（有点杂乱）冒泡排序的对象阵列的所谓的“排序”，代码如下万一添加破到冒泡排序阵列已经排序

object storage = 0; 
for (int i = 0; i < sorted.Length; i++) 
{ 
    for (int c = 0; c < sorted.Length - 1; c++) 
    { 
     if (sorted[c].ToString().CompareTo(sorted[c + 1].ToString()) > 0) 
     { 
      storage = sorted[c + 1]; 
      sorted[c + 1] = sorted[c]; 
      sorted[c] = storage; 
     } 
    } 
    return sorted;

问题是无论如何这个函数总是循环遍历数组。假设“排序”数组可能是一个大数组，并且恰好恰好已经被排序，在这种情况下，该函数仍然会扫描数组并且工作一段时间，这是我想要阻止的。所以问题是，如果数组已被排序，我该如何正确地停止循环？

来源

2017-09-01 c-shark

没有内置函数来检查数组是否排序或不是。在每种情况下，您都需要访问数组的每个元素。排序数组的最佳时间复杂度为O（n）。 –

插入排序是否适合您？它对于已排序的数组具有O（n）时间复杂度。 – jumper0x08

有一个更一般的优化，你可以限制内循环到最后一次迭代进行交换的位置。 –

气泡排序会将数组的最大（最小）元素向数组的最后冒泡。这是你的内在循环所做的。首先，您可以利用n次迭代后最后n个元素已经排序的知识，这意味着您的内部循环不需要检查（n + 1）个元素中的最后n个元素，迭代。其次，如果内部循环没有改变任何东西，那么这些元素必须已经在序列中，这对于外部循环的中断是一个好的点。

既然你这样做是为练习练习，我将离开编码给你:-)

来源

2017-09-01 08:14:36 Ronald

更好，但仍然不是'最佳'的气泡排序。这是矛盾的。 –

是的，关于更优化优化的评论会让它更好。理所当然的。这是我第二点的概括。 – Ronald

为什么不使用OrderBy而不是自己排序呢？

sorted = sorted.OrderBy(s=> s).ToArray();

如果你坚持使用冒泡排序，你可以这样做：

bool changed; 
for (int i = 0; i < sorted.Length; i++) 
{ 
    changed = false; 
    for (int c = 0; c < sorted.Length - 1; c++) 
    { 
     if (sorted[c].ToString().CompareTo(sorted[c + 1].ToString()) > 0) 
     { 
      changed = true; 
      storage = sorted[c + 1]; 
      sorted[c + 1] = sorted[c]; 
      sorted[c] = storage; 
     } 
     if(!changed) break; 
    }

我在第一循环设置更改为false各一次。如果最后没有改变，那么数组已经排序。

来源

2017-09-01 08:05:13

只需练习不同的东西，泡沫排序是其中之一:) –

看看我编辑的答案 –

-1

试试这个：

object storage = 0; 
for (int i = 0; i < sorted.Length; i++) 
{ 
    bool swapped = false; 
    for (int c = 0; c < sorted.Length - 1; c++) 
    { 
     if (sorted[c].ToString().CompareTo(sorted[c + 1].ToString()) > 0) 
     { 
      storage = sorted[c + 1]; 
      sorted[c + 1] = sorted[c]; 
      sorted[c] = storage; 
      swapped = true; 
     } 
    } 
    if (!swapped) 
    { 
     break; 
    } 
}

如果它获得通过没有通过交换，然后对数组进行排序，因此会break。

来源

2017-09-01 08:13:36 Enigmativity

万一添加破到冒泡排序阵列已经排序

回答

相关问题