时间戳

首页 > 解决方案 > 冒泡排序功能在数组中途停止工作

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

问题描述

对于我的任务，我需要生成一个随机数组并使用冒泡排序从最小到最大对其进行排序，并在数组中搜索某些数字。我已经完成了大部分任务，但我意识到在数组进行到一半的时候，我的冒泡排序已经停止工作，因为数字乱序了。因此，前几个数字可能是 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;
}

标签： c++arrayssorting

解决方案

在此处输入图像描述

资料来源： 算法：解释和动画

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

在您的代码中，特别是这个

 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]并使用您的逻辑对其进行排序。这在这两种情况下都会发生。

情况1 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]超出界限。这就是为什么我们总是在最终索引之后保持一个索引。

希望这可以帮助。祝你好运。

推荐阅读