标签: bubble-sort

为什么你会选择冒泡排序而不是其他排序算法？

我正在尝试使用Tardis monad 在任何可遍历的容器上实现冒泡排序.

{-# LANGUAGE TupleSections #-}

module Main where

import Control.DeepSeq
import Control.Monad.Tardis
import Data.Bifunctor
import Data.Traversable
import Data.Tuple
import Debug.Trace

newtype Finished = Finished { isFinished :: Bool }

instance Monoid Finished where
  mempty = Finished False
  mappend (Finished a) (Finished b) = Finished (a || b)

-- | A single iteration of bubble sort over a list.
-- If the list is unmodified, return 'Finished' 'True', else 'False'
bubble :: Ord a => [a] -> (Finished, …

我正在为考试做修改.

想知道在什么条件下插入排序比O(N ^ 2)的相同平均情况复杂度的冒泡排序更好.

我确实找到了一些相关的文章,但我无法理解它们.

有人会介意以简单的方式解释它吗？

可以设想对冒泡排序进行修改，其中“交换”以概率随机发生p，而不是通过执行比较。结果可以称为“泡沫洗牌”。靠近前面的元素可能会保留在那里，但有机会移到列表的后面。

修改从互联网上窃取的冒泡排序，您可以想出以下内容：

import random

def bubble_shuffle(arr, p):
    arr = copy.copy(arr)
    n = len(arr) 
  
    # Traverse through all array elements 
    for i in range(n-1): 
    # range(n) also work but outer loop will repeat one time more than needed. 
  
        # Last i elements are already in place 
        for j in range(0, n-i-1): 
  
            # traverse the array from 0 to n-i-1 
            # Swap if random number [0, 1] is less than p
            if random.random() < p:
                arr[j], arr[j+1] = arr[j+1], arr[j] …

请问您能告诉我在JavaScript中实现冒泡排序算法有什么问题吗？

for (var i=1; i<records.length; i++){
        for (var j=records.length; j<1; j--){
            if (parseInt(records[i-1]) < parseInt(records[i])){
                var temp = records[i-1];
                records[i-1] = records[i]
                records[i] = temp;
            }   
        }    
    }

根据ALGORITHMS 2.2中使用的方法,我在最佳情况下推导出了冒泡排序的时间复杂度.但结果却是O(n ^ 2).

这是我的推导,希望有人能帮我找出错误的地方:

public void bubbleSort(int arr[]) {
for(int i = 0, len = arr.length; i < len - 1; i++) {
    for(int j = 0; j < len - i - 1; j++) {
        if(arr[j + 1] < arr[j])
            swap(arr, j, j + 1);
    }
}

}

Statements                      cost    times
i = 0,len = arr.length          c1          1
i < len - 1                     c2          n
i++                             c3          n - 1
j = 0                           c4          n - 1 …

如果以随机顺序给出数组,则必须输出转换为循环排序数组所需的最小交换数.

例如,给出的阵列是3 5 4 2 1

所以第一次交换将是5 < - > 4结果:3 4 5 2 1秒交换将是2 < - > 1结果:3 4 5 1 2(最终)

输出:2

我无法理解这个问题背后的逻辑.

添加更多: 只能在相邻元素之间进行交换,数字在1到N之间

我做了一些研究关于JavaScript的排序算法的性能比较,发现意想不到的效果.冒泡排序提供了比其他更好的性能,如Shell排序,快速排序和本机Javascript功能.为什么会这样？也许我的性能测试方法错了？

你可以在这里找到我的研究结果.

以下是一些算法实现示例:

  /**
   * Bubble sort(optimized)
   */
  Array.prototype.bubbleSort = function ()
  {
     var n = this.length;
     do {
        var swapped = false;
        for (var i = 1; i < n; i++ ) {
           if (this[i - 1] > this[i]) {
              var tmp = this[i-1];
              this[i-1] = this[i];
              this[i] = tmp;
              swapped = true;
           }
        }
     } while (swapped);
  }

  /**
   * Quick sort
   */
  Array.prototype.quickSort = function ()
  {
      if (this.length <= 1)
          return this; …

I wrote the bubble sort algorithm in JavaScript and Wasm using Rust and the JS code is faster than Rust code. How is this possible?

JavaScript code

import * as wasm from "wasm-comparision-sort-algorithms";

function main() {
  const arr = generateRandomArray({size: 50000, min: 1, max: 1000})
  const arr2 = [...arr]
  console.time("Bubble Sort JS")
  bubbleSort(arr)
  console.timeEnd("Bubble Sort JS")
  wasm.handle_bubble_sort(arr2)
}

/**
 * Algorithm to sort an array of numbers using the bubble sort algorithm.
 * @param {Number[]} arr - The array of …

我最近读了一篇文章,讨论了算法的计算复杂性.作者提到"为什么插入排序比小型案例的快速排序和冒泡排序更快".有人可以为此做出一些解释吗？

有人知道我上面提到的每种排序算法的实际复杂性吗？