空元素冒泡排序的逆序
Reverse order of bubble sort of null elements
我正在尝试反转我的冒泡排序,以便所有 null 元素都被推到数组的末尾而不是开始,因为它们现在正在排序。关于如何实现这一点有什么建议吗?
for (int outerLoop = 0; outerLoop < students.Length-1; outerLoop++)
{
for (int innerLoop = 0; innerLoop < students.Length-1; innerLoop++)
{
if (students[outerLoop+1] == null)
{
var tempObject = students[outerLoop+1];
students[outerLoop+1] = students[innerLoop];
students[innerLoop] = tempObject;
}
}
}
有一种更快、更简单、更稳定的方法,时间复杂度为 O(n)
:
int at = 0;
for (int i = 0; i < students.Length; ++i)
if (students[i] != null)
students[at++] = students[i];
for (int i = at; i < students.Length; ++i)
students[i] = null;
但是,如果您坚持使用冒泡排序:我们可以用稍微不同的方式来实现它
for (bool wrongOrder = true; wrongOrder;) {
wrongOrder = false;
for (int i = 1; i < students.Length; i++) {
if (students[i - 1] == null && students[i] != null) {
// At least 2 items has wrong order, swap them
var temp = students[i - 1];
students[i - 1] = students[i];
students[i] = temp;
wrongOrder = true;
}
}
}
更正后的代码:
for (int outerLoop = 0; outerLoop < students.Length-1; outerLoop++)
{
for (int innerLoop = 0; innerLoop < students.Length-1; innerLoop++)
{
if (students[innerLoop] == null)
{
var tempObject = students[innerLoop+1];
students[innerLoop+1] = students[innerLoop];
students[innerLoop] = tempObject;
}
}
}
这不会对您的数组进行排序,只会删除底部的空值。
事实上你可以取消临时变量:
for (int outerLoop = 0; outerLoop < students.Length-1; outerLoop++)
{
for (int innerLoop = 0; innerLoop < students.Length-1; innerLoop++)
{
if (students[innerLoop] == null)
{
students[innerLoop] = students[innerLoop+1];
students[innerLoop+1] = null;
}
}
}
注意:
C# 7 introduced tuples 可以在没有临时变量的情况下交换两个变量:
int a = 10;
int b = 2;
(a, b) = (b, a);
这会将 b
分配给 a
,将 a
分配给 b
。
试试看。您必须测试外部是否为 null 而内部是否为 null :
for (int outerLoop = 0; outerLoop < students.Length - 1; outerLoop++)
{
for (int innerLoop = outerLoop + 1; innerLoop < students.Length; innerLoop++)
{
if ((students[outerLoop] == null) && (students[innerLoop] != null))
{
var tempObject = students[outerLoop];
students[outerLoop] = students[innerLoop];
students[innerLoop] = tempObject;
}
}
}
我正在尝试反转我的冒泡排序,以便所有 null 元素都被推到数组的末尾而不是开始,因为它们现在正在排序。关于如何实现这一点有什么建议吗?
for (int outerLoop = 0; outerLoop < students.Length-1; outerLoop++)
{
for (int innerLoop = 0; innerLoop < students.Length-1; innerLoop++)
{
if (students[outerLoop+1] == null)
{
var tempObject = students[outerLoop+1];
students[outerLoop+1] = students[innerLoop];
students[innerLoop] = tempObject;
}
}
}
有一种更快、更简单、更稳定的方法,时间复杂度为 O(n)
:
int at = 0;
for (int i = 0; i < students.Length; ++i)
if (students[i] != null)
students[at++] = students[i];
for (int i = at; i < students.Length; ++i)
students[i] = null;
但是,如果您坚持使用冒泡排序:我们可以用稍微不同的方式来实现它
for (bool wrongOrder = true; wrongOrder;) {
wrongOrder = false;
for (int i = 1; i < students.Length; i++) {
if (students[i - 1] == null && students[i] != null) {
// At least 2 items has wrong order, swap them
var temp = students[i - 1];
students[i - 1] = students[i];
students[i] = temp;
wrongOrder = true;
}
}
}
更正后的代码:
for (int outerLoop = 0; outerLoop < students.Length-1; outerLoop++)
{
for (int innerLoop = 0; innerLoop < students.Length-1; innerLoop++)
{
if (students[innerLoop] == null)
{
var tempObject = students[innerLoop+1];
students[innerLoop+1] = students[innerLoop];
students[innerLoop] = tempObject;
}
}
}
这不会对您的数组进行排序,只会删除底部的空值。
事实上你可以取消临时变量:
for (int outerLoop = 0; outerLoop < students.Length-1; outerLoop++)
{
for (int innerLoop = 0; innerLoop < students.Length-1; innerLoop++)
{
if (students[innerLoop] == null)
{
students[innerLoop] = students[innerLoop+1];
students[innerLoop+1] = null;
}
}
}
注意: C# 7 introduced tuples 可以在没有临时变量的情况下交换两个变量:
int a = 10;
int b = 2;
(a, b) = (b, a);
这会将 b
分配给 a
,将 a
分配给 b
。
试试看。您必须测试外部是否为 null 而内部是否为 null :
for (int outerLoop = 0; outerLoop < students.Length - 1; outerLoop++)
{
for (int innerLoop = outerLoop + 1; innerLoop < students.Length; innerLoop++)
{
if ((students[outerLoop] == null) && (students[innerLoop] != null))
{
var tempObject = students[outerLoop];
students[outerLoop] = students[innerLoop];
students[innerLoop] = tempObject;
}
}
}