这是什么排序算法？

Question

更新:好的我看到它是一个冒泡排序,但效率较低,因为当特定运行没有交换时它不会停止？它运行直到first为null.

嗨,我有一个排序算法如下.我的问题是,哪种排序算法是这样的？我认为这是冒泡排序,但它没有多次运行.任何的想法？谢谢!

//sorting in descending order
struct node
{
    int value;
    node* NEXT;
}
//Assume HEAD pointer denotes the first element in the //linked list
// only change the values…don’t have to change the //pointers

Sort( Node *Head)
{
    node* first,second,temp;
    first= Head;
    while(first!=null)
    {
        second=first->NEXT;
        while(second!=null)
        {
            if(first->value < second->value)
            {
                temp = new node();
                temp->value=first->value;
                first->value=second->value;
                second->value=temp->value;
                delete temp;
            }
            second=second->NEXT;
        }

        first=first->NEXT;
    }
}

Answer 1

让我们使算法更清晰:

Sort {
   first = head;
   while (first ? NULL) {
      next = first.next
      while (next ? NULL) {
         if (first.value < next.value)
            swap first.value and next.value
         advance next
      }
      advance first
   }
}

这是一种非常低效的插入排序实现.

示例运行显示插入排序特征:

5 ? 2 ? 3 ? 1 ? nil
^   ^
f   n [swap]

2 ? 5 ? 3 ? 1 ? nil
^       ^
f       n

2 ? 5 ? 3 ? 1 ? nil
^           ^
f           n [swap]

1 ? 5 ? 3 ? 2 ? nil
^               ^
f               n

1 ? 5 ? 3 ? 2 ? nil   // insert the minimum value 1 to the beginning of the sublist
    ^   ^
    f   n [swap]

1 ? 3 ? 5 ? 2 ? nil
    ^       ^
    f       n [swap]

1 ? 2 ? 5 ? 3 ? nil  // insert the minimum value 2 to the beginning of the sublist
    ^           ^
    f           n

1 ? 2 ? 5 ? 3 ? nil
        ^   ^
        f   n [swap]

1 ? 2 ? 3 ? 5 ? nil  // insert the minimum value 3 to the beginning of the sublist
        ^       ^
        f       n

1 ? 2 ? 3 ? 5 ? nil  // insert the minimum value 5 to the beginning of the sublist
            ^   ^
            f   n

1 ? 2 ? 3 ? 5 ? nil
                ^
                f

Answer 2

这是一种"经典"冒泡排序和选择排序之间的混合- 但更接近于经典的冒泡排序.

在经典的冒泡排序中,内循环在遍历列表/数组时交换相邻的对.

在经典选择排序中,内循环跟踪它在列表的剩余部分中找到的最大值,并将其与内循环当前正在考虑的列表部分中的第一个值交换.

问题中发布的排序类似于Selection排序,因为始终使用内循环正在考虑的子列表中的第一个值执行交换.它与Selection排序(与经典冒泡排序类似)的不同之处在于,只要找到大于内循环子列表的当前第一个成员的值,它就会执行交换.

然而,它与经典的Bubble排序不同之处在于它不会交换相邻的对.在经典冒泡排序中,当内循环完成圆形工作时,列表中最大的元素已过滤到列表的底部,但在此变体中,最小元素已过滤到内循环的子顶部-list.

我将此标记为经典冒泡排序的变体而不是选择排序,因为问题中排序的性能特征与经典冒泡排序(O(n^2)比较和O(n^2)交换)相同,而选择排序具有O(n)交换.

但是,经典冒泡排序与此之间的另一个区别是经典的冒泡排序是稳定的,而问题中的排序则不是.通过排序运行时,请考虑以下项目列表.在比较中仅使用数字 - 字母仅用于区分具有相同等级的元素.图表显示了执行的交换操作(为简洁起见,未显示比较):

3.a  3.b   3.c   2.a   2.b   1.a
 ^                ^
 +----------------+


2.a  3.b   3.c   3.a   2.b   1.a
 ^                            ^
 +----------------------------+


1.a  3.b   3.c   3.a   2.b   2.a
      ^                 ^
      +-----------------+


1.a  2.b   3.c   3.a   3.b   2.a
            ^                 ^
            +-----------------+


1.a  2.b   2.a   3.a   3.b   3.c

请注意,在排序结束时,项目2.a和2.b的相对位置已更改,表示不稳定的排序.