如何正确地将选择排序算法重新设计为冒泡排序？

Question

我试图将选择排序转换为冒泡排序。我成功了吗？如果没有，我需要做些什么来纠正这个问题？

我相信我已正确转换它。

Attempt

// This program demonstrates how to sort and search a
// string vector using selection sort and binary search.
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Function prototypes
void bubbleSort (vector < string > &);
void swap (string &, string &);
int binarySearch (const vector < string > &, string);

int main ()
{
  string searchValue;       // Value to search for
  int position;         // Position of found value

  // Define a vector of strings.
  vector < string > names
  {
  "Lopez", "Smith", "Pike", "Jones",
      "Abernathy", "Hall", "Wilson", "Kimura",
      "Alvarado", "Harrison", "Geddes", "Irvine"};

  // Sort the vector.
  bubbleSort (names);

  // Display the vector's elements.
  cout << "Here are the sorted names:\n";
for (auto element:names)
    cout << element << endl;
  cout << endl;

  // Search for a name.
  cout << "Enter a name to search for: ";
  getline (cin, searchValue);
  position = binarySearch (names, searchValue);

  // Display the results.
  if (position != -1)
    cout << "That name is found at position " << position << endl;
  else
    cout << "That name is not found.\n";

  return 0;
}

//***********************************************************************
// The selectionSort function sorts a string vector in ascending order. *
//***********************************************************************
void bubbleSort (vector < string > &v)
{
  int minIndex;
  string minValue;

  for (int pass = 1; pass < v.size (); ++pass)
    {
      for (int index = 0; (index + 1) < v.size (); ++index)
    {
      if (v[index + 1] < v[index])
        {
          swap (v[index], v[index + 1]);
        }
    }
    }

//***************************************************
// The swap function swaps a and b in memory.       *
//***************************************************
  void swap (string & a, string & b)
  {
    string temp = a;
    a = b;
    b = temp;
  }

//***************************************************************
// The binarySearch function performs a binary search on a      *
// string vector. array, which has a maximum of size elements,  *
// is searched for the number stored in value. If the number is *
// found, its vector subscript is returned. Otherwise, -1 is    *
// returned indicating the value was not in the vector.         *
//***************************************************************

  int binarySearch (const vector < string > &v, string str)
  {
    int first = 0,      // First vector element
      last = v.size () - 1, // Last vector element
      middle,           // Mid point of search
      position = -1;        // Position of search value
    bool found = false;     // Flag

    while (!found && first <= last)
      {
    middle = (first + last) / 2;    // Calculate mid point
    if (v[middle] == str)   // If value is found at mid
      {
        found = true;
        position = middle;
      }
    else if (v[middle] > str)   // If value is in lower half
      last = middle - 1;
    else
      first = middle + 1;   // If value is in upper half
      }
    return position;
  }

目标是从选择排序转换为冒泡排序。我有原始代码，我尝试转换之前，如果这将有所帮助。

Answer 1

冒泡排序仅交换相邻元素，因此在测试非相邻元素的任何地方，您都会与气泡分离。最简单的冒泡形式就是这种形式。

for (int pass = 1; pass < v.size(); ++pass) {
    for (int index = 0; (index + 1) < v.size(); ++index) {
        if (v[index + 1] < v[index]) {
            swap(v[index], v[index + 1]);
        }
    }
}

我们可以注意到，在第一次传递之后，最大值必须在正确的位置，并且类似地在第二次传递之后第二个最大值在它的位置，等等。这允许我们调整内部循环的边界。

for (int pass = 1; pass < v.size(); ++pass) {
    for (int index = 0; (index + pass) < v.size(); ++index) {
        if (v[index + 1] < v[index]) {
            swap(v[index], v[index + 1]);
        }
    }
}