代码之家  ›  专栏  ›  技术社区  ›  mvaldetaro

冒泡排序算法的这个变种叫什么名字?

  •  -5
  • mvaldetaro  · 技术社区  · 7 年前

    下面的gif中显示的排序算法的名称是什么?

    Sort Algorithm

    更新:

    最简单的形式每次都会遍历整个列表:

    伪代码:

    procedure cocktailShakerSort( A : list of sortable items ) defined as:
      do
        swapped := false
        for each i in 0 to length( A ) - 2 do:
          if A[ i ] > A[ i + 1 ] then // test whether the two elements are in the wrong order
            swap( A[ i ], A[ i + 1 ] ) // let the two elements change places
            swapped := true
          end if
        end for
        if not swapped then
          // we can exit the outer loop here if no swaps occurred.
          break do-while loop
        end if
        swapped := false
        for each i in length( A ) - 2 to 0 do:
          if A[ i ] > A[ i + 1 ] then
            swap( A[ i ], A[ i + 1 ] )
            swapped := true
          end if
        end for
      while swapped // if no elements have been swapped, then the list is sorted
    end procedure
    
    2 回复  |  直到 7 年前
        1
  •  2
  •   sahushivam    7 年前

    看起来像是鸡尾酒,是泡泡酒的变种。气泡排序算法总是从左侧遍历元素,并在第一次迭代中将最大的元素移动到正确的位置,在第二次迭代中将第二大的元素移动到正确的位置,以此类推。鸡尾酒排序交替地在两个方向上遍历给定的数组。

    算法 : 算法的每次迭代分为两个阶段:

    第一阶段从左到右遍历数组,就像气泡排序一样。在循环过程中,将比较相邻项,如果左侧的值大于右侧的值,则交换值。在第一次迭代结束时,最大的数字将驻留在数组的末尾。

    2—第二阶段以相反的方向在数组中循环—从最近排序的项之前的项开始,然后移回数组的开头。在这里,相邻的项目也会被比较,如果需要的话会被交换。

    算法需要在不进行任何交换的情况下完成整个过程才能知道它已排序。

    时间的复杂性是一样的,但鸡尾酒的表现比泡泡更好。一般来说,鸡尾酒排序比泡泡排序快不到两倍。考虑这个例子(2,3,4,5,1)。对于本例,冒泡排序需要四次遍历数组,而鸡尾酒排序只需要两次遍历。

        2
  •  1
  •   paxdiablo    7 年前

    (一) . 从左到右移动一个元素(通过与其后续元素交换),直到找到一个更大的元素,然后继续移动该元素。

    话虽如此,假设你没有自己制作动画,那么你从哪个网站上得到的动画肯定会有一些关于它是什么的指示,是吗?:-)


    哪个是 显然地 被称为鸡尾酒类(指你摇鸡尾酒的方式),虽然,在我看来 长的 职业生涯,我从来没听过这样的说法。