带有修改（偏移）的冒泡排序

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--;
}

Answer 2

您可以将 for (int j = 1; j < roz; j++) 更改为 for (int j = 1; j < roz-i; j++) 以仅遍历数组中未排序的元素。这将步骤从 88 步减少到 68 步，大约减少了四分之一。

带有修改（偏移）的冒泡排序

Bubble sort with modification (offset)

c++

bubble-sort

offset