时间戳

首页 > 解决方案 > 空元素冒泡排序的逆序

c# - 空元素冒泡排序的逆序

问题描述

我正在尝试反转我的冒泡排序，以便所有空元素都被推到数组的末尾而不是开头，因为它们现在正在排序。关于如何实现这一点的任何建议？

            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;
                    }
                }
            }

标签： c#arrayssortingbubble-sort

解决方案

有一种更快、更简单、更稳定的方法，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;
      }
    }
  }

推荐阅读