c++ - 带有修改(偏移)的冒泡排序

Question

我的任务是编写冒泡排序修改，其中比较次数减少了大约一半。

我已经编写了我的标准冒泡排序算法:

void bubble_sort(int* tab, int roz)
{
    int test;
    for (int i = 0; i < roz; i++)
    {
        for (int j = 1; j < roz; j++)
        {
            if (tab[j - 1] > tab[j])
            {
                test = tab[j - 1];
                tab[j - 1] = tab[j];
                tab[j] = test;
            }
        }
    }
}

以及如何修改才能共同完成任务？代码会是什么样子？

Answer 1

您可以使用以下方法优化您的解决方案:

在算法的第一次迭代中，您确定最后一个元素是最大的。所以它已经是有序的。无需在内部循环中循环到数组末尾。

在每次新的迭代中，都会有一个元素按顺序排列。因此，您可以将下一个内部循环计数减少 1。

我冒昧地修改了一下你的解决方案。

int lastUnsorted = n - 1;
bool isSorted = false;

while (!isSorted)
{
    isSorted = true;
    for (int i = 0; i < lastUnsorted; i++)
    {
        if (arr[i] > arr[i + 1])
        {
            isSorted = false;
            int temp = arr[i + 1];
            arr[i + 1] = arr[i];
            arr[i] = temp;
        }
    }
    lastUnsorted--;
}