BubbleSort 做了一些奇怪的事情

Question

我正在慢慢摸索冒泡排序的实现，这个概念很容易理解。基本上我已经做到了：

<?php

namespace TeamRock;

class BubbleSort
{

public function sort(array $integers)
{
    if (count ($integers) > 0)
    {
        //if value of array is over one do this-->
        for ($i = 0; $i<count($integers); $i++) //iterating through the array
        {
            for($j = 1; $j<count($integers);$j++)
            {
                //where the sorting happens
                $holder = $integers[$j];
                if ($integers[$j] < $integers[$j-1]){
                        $integers[$i] = $integers[$j-1];
                        $integers[$j-1] = $holder;
                }
            }
        }
        return $integers;
    }
    else{
        return $integers;
    }
}
}

Sudo Code-

//For each element in array
//Look at the element to direct right
//If the element on the left is greater than the element to the direct   right
//Then we should swap these elements positions
//
//restart at start of loop until all numbers are numbered

好的，这就是函数，我想自己编写函数而不是使用内置的 php 函数。我也在使用 phpspec 来测试这些并在此处定义我的变量 spec:

<?php

namespace phpspec\TeamRock;

use PhpSpec\ObjectBehavior;


class BubbleSortSpec extends ObjectBehavior
{
function it_is_initializable()
{
    $this->shouldHaveType('TeamRock\BubbleSort');
}

function it_can_sort_an_array_of_four_integers()
{
    $integers = [8, 4, 6, 2];

    $this->sort($integers)->shouldReturn(['2, 4, 6, 8']);
}
function it_can_sort_an_array_of_five_integers()
{
    $integers = [6, 11, 0, 9, 3];

    $this->sort($integers)->shouldReturn([0, 3, 6, 9, 11]);
}
}

当我运行规范时，这就是我得到的：

TeamRock/BubbleSort                                                               
15  - it can sort an array of four integers
  expected [array:1], but got [array:4].

  @@ -1,3 +1,6 @@
     [
  -    0 => ""2, 4, 6, 8"...",
  +    0 => 2,
  +    1 => 2,
  +    2 => 2,
  +    3 => 2,
     ]


    17         $integers = [8, 4, 6, 2];
    18 
    19         $this->sort($integers)->shouldReturn(['2, 4, 6, 8']);
    20     }
    21     function it_can_sort_an_array_of_five_integers()
    22     {


   0 vendor/phpspec/phpspec/src/PhpSpec/Matcher/IdentityMatcher.php:78
     throw new PhpSpec\Exception\Example\NotEqualException("Expected [array:1]...")
   1 [internal]
     phpspec\TeamRock\BubbleSortSpec->it_can_sort_an_array_of_four_integers()


TeamRock/BubbleSort                                                             
21  - it can sort an array of five integers
  expected [array:5], but got [array:5].

  @@ -1,7 +1,7 @@
     [
       0 => 0,
  -    1 => 3,
  -    2 => 6,
  -    3 => 9,
  -    4 => 11,
  +    1 => 0,
  +    2 => 0,
  +    3 => 3,
  +    4 => 3,
     ]


    23         $integers = [6, 11, 0, 9, 3];
    24 
    25         $this->sort($integers)->shouldReturn([0, 3, 6, 9, 11]);
    26     }
    27 }


   0 vendor/phpspec/phpspec/src/PhpSpec/Matcher/IdentityMatcher.php:78
     throw new PhpSpec\Exception\Example\NotEqualException("Expected [array:5]...")
   1 [internal]
     phpspec\TeamRock\BubbleSortSpec->it_can_sort_an_array_of_five_integers()


                       71%                                     28%              7
   2 specs
   7 examples (5 passed, 2 failed)
   19ms

任何帮助或指点将不胜感激

我确实有一个插入排序工作正常，这就是为什么有一些通过了，失败的是为了冒泡。

我又一次对此很陌生，所以让我喘口气 space 因为我遗漏了任何基本的东西。我想把这个记在脑子里 :P

Answer 1

首先使用冒泡排序不是一个好主意。它的复杂度为 O(n^2)。你应该使用php usort，它实际上是一个合并排序实现 O(n*log(n)) 复杂度或者你可以自己实现。

无论如何，你的冒泡排序是错误的，你混淆了索引。

试试这个：

public function bubbleSort(array $numbers)
{
    for ( $i = 0; $i < count($numbers); $i++ ) {  
        for ($j = 0; $j < count($numbers) $j++ ) {  
            if ($numbers[$i] < $numbers[$j]) {  
                 $temp = $numbers[$i];  
                 $numbers[$i] = $numbers[$j];  
                 $numbers[$j] = $temp;  
            }  
         }  
     }
     return $numbers; 
}

Answer 2

您的代码中存在一些错误。一、算法：

            $holder = $integers[$j];
            if ($integers[$j] < $integers[$j-1]){
                    $integers[$i] = $integers[$j-1];
                    $integers[$j-1] = $holder;
            }

上面的第二个作业应该是：

                    $integers[$j] = $integers[$j-1];

因为如果顺序错误，您将 $integers[$j] 与 $integers[$j-1] 交换（我确定这只是一个错字）。
此错误可能导致规范中的第二个测试用例失败。

第一个测试用例：

function it_can_sort_an_array_of_four_integers()
{
    $integers = [8, 4, 6, 2];

    $this->sort($integers)->shouldReturn(['2, 4, 6, 8']);
}

应改为：

    $this->sort($integers)->shouldReturn([2, 4, 6, 8]);

请注意，这是一个包含四个整数的数组，而您的代码会根据包含一个字符串的数组检查结果。

进一步改进：

您运行 count($integers) 通过数组检查顺序错误的相邻值对。虽然这是所需的最大传递次数，但很多时候它会提前完成。

更好的实现是保留一个标志，在每次传递后记住是否有交换完成并在有 none 时退出循环（因为数组已经排序）。

像这样：

public function sort(array $integers)
{
    // Call count() only once before the loop because it doesn't change
    $count = count($integers);

    do {
        // Didn't swap any neighbour values yet in this loop
        $swapped = FALSE;
        // Run through the list, swap neighbour values if needed
        for ($j = 1; $j < $count; $j ++)
        {
            // Check neighbour values
            // Initialize $holder only when it is needed (to swap values)
            if ($integers[$j] < $integers[$j - 1]) {
                // Swap the values
                $holder = $integers[$j];
                $integers[$i] = $integers[$j - 1];
                $integers[$j - 1] = $holder;
                // Remember we did at least one swap on this pass
                $swapped = TRUE;
            }
        }
    // Keep passing through the array while at least one swap was done
    // When there was no swap then the values are in the desired order
    } while ($swapped);

    // Return the sorted array
    return $integers;
}

BubbleSort 做了一些奇怪的事情

BubbleSort doing something weird

php

bubble-sort