c++ - 冒泡排序功能在数组中途停止工作

Question

对于我的作业，我需要生成一个随机数组并使用冒泡排序按从小到大的顺序对其进行排序，并在数组中搜索某些数字。我已经完成了大部分作业，但我意识到在数组进行到一半时我的冒泡排序已经停止工作，因为数字乱序了。因此，前几个数字可能是 44、50、50、56、65，然后是 20 个数字数组中的大约 10-11 个数字，它开始变得随机。这是我第一次使用冒泡排序，所以这可能是我不认识的一个小错误。

搜索功能也没有显示，因为在程序中到达该点之前顺序显示错误，但该功能也可以正常工作。

int const MAX = 20;
int bubbleSort(int arr[], int length, int arrSelect);
void search(bool found, int arrayCheck[], int x1);
void swap(int *swap1, int *swap2);

int main()
{
    //Variables

    int original[MAX];
    int sorted[MAX];
    int quantity = 0;
    int sum = 0;
    int x = 0;
    bool find = false;
    double avg = 0;
    bool found = false;
    srand(time(NULL));

    for(int i = 0; i < MAX;)
    {
        original[i] = ((rand() % 89) + 10);

        sorted[i] = original[i];

        sum += original[i];

        i++;
    }

    for (int k = 0; k < MAX;)
    {
        sorted[k] = bubbleSort(sorted, MAX, k);
        cout << sorted[k] << endl;
        k++;
    }
    search(find, sorted, x);



}

int bubbleSort(int arr[], int length, int arraySelect)
{
    int r = 0;
    int c = 0;
    for(r = 0; r <= MAX - 1; r++)
    {
        for (c = 0; c <= MAX - r - 1; c++) 
        {
            if (arr[c] > arr[r])
            {
                swap(&arr[c], &arr[r]);
            }

        }
    }

    return arr[arraySelect];
}

void swap(int *swap1, int *swap2)
{
    int temp = *swap1;
    *swap1 = *swap2;
    *swap2 = temp;
}

Answer 1

来源: Algorithms: Explained and Animated

正如您在上面的模拟中看到的那样，在数组的单次传递中，冒泡排序比较每对连续的索引，如果一个大于另一个，则交换它们。这样一来，每次将最小值或最大值(取决于您的交换条件)冒泡到数组的一端。

在你的代码中特别是这个

 if (arr[c] > arr[r])
 {
     swap(&arr[c], &arr[r]);
 }

r 的值对于内循环的每次完整迭代都保持不变。这意味着您不会像上面的模拟那样比较两个连续的索引，而是将一个索引与数组的其余部分一个一个地进行比较，这不是冒泡排序的工作方式。你应该比较过arr[c]与 arr[c+1]

即使您的代码逻辑有点缺陷，但运行您的代码会在您更改后给出正确的输出

for (c = 0; c <= MAX - r - 1; c++)

与

for (c = 0; c <= MAX - 1; c++)

正如 Fab 已经在他的回答中强调的那样。原因是您迭代和比较 c 的方式和 r要求您内部循环始终运行数组的全长以使输出正确。在正确的冒泡排序算法中，这种修改是不必要的，因为您将在下面的正确解决方案中看到。

即便如此，您的代码仍然不是冒泡排序，最糟糕的是，如果给定一个已经排序的数组，您的代码将重新排列它(交换一些索引)然后将其排序回来，这显然不应该发生。

这是一个例子。假设我有一个数组 [1 , 2 , 3]并使用您的逻辑对其进行排序。这两种情况都会发生。

案例一 for (c = 0; c <= MAX - r - 1; c++)

1 2 3 (initial array)
-----
3 1 2 (1st pass)
1 3 2 (2nd pass)
1 3 2 (3rd pass / final output)

案例2 for (c = 0; c <= MAX - 1; c++)

1 2 3 (initial array) 
-----
3 1 2 (1st pass)
1 3 2 (2nd pass)
1 2 3 (3rd pass / final output)

如您所见，在这两种情况下，排序良好的数组仍在交换和求助，这显然没有必要，我们绝对不希望这样。

这是您的 bubbleSort 的正确版本方法

int bubbleSort(int arr[], int length, int arraySelect)
{
    int r = 0;
    int c = 0;
    for(r = 0; r < MAX - 1; r++)
    {
        for (c = 0; c < MAX - r - 1; c++) 
        {
            if (arr[c] > arr[c+1])
            {
                swap(&arr[c], &arr[c+1]);
            }

        }
    }

    return arr[arraySelect];
}

我所做的就是替换 arr[r]与 arr[c+1]所以现在它比较连续的索引并替换了 <=只有 <因为我们正在比较连续的索引，所以我们不想要 arr[c+1]出界。这就是为什么我们总是在最终索引之后保留一个索引。

希望这对您有所帮助。祝你好运。