冒泡排序所需的交换次数，而不实际排序[重复]

Question

这个问题在这里已有答案：

• How to find number of expected swaps in bubble sort in better than O(n^2) time 2回答

如果有一种方法可以在冒泡排序算法中实际找到数组所需的交换次数，那我只是在徘徊。我知道你们中的一些人可能会认为使用冒泡排序实际排序数组有什么危害，并且每当我们交换时增加计数。但我认为为什么不必要地增加程序的复杂性，因为我只需要对数组进行排序所需的交换次数。我需要降低下面代码的复杂性。

void minimumBribes(vector<int> q) {
    int count=0;
    //returns Too chaotic if the element is farther then two positions to the left.
    for(int i=0;i<q.size();i++){
        if(q[i]-(i+1)>2){
            cout<<"Too chaotic"<<endl;
            return;
        }
    }
    //counts the number of swaps required
    for(int i=0;i<q.size();i++){
        for(int j=0;j<q.size()-i-1;j++){
            if(q[j]>q[j+1]){
                swap(q[j],q[j+1]);
                count++;
            }
        }
    }
    cout<<count<<endl;

}

一个小的代码片段会很好，因为我在这方面不是很好。

Answer 1

要知道交换的数量，只需要知道已排序元素的最终位置。排序本身可以使用更好的算法来完成，因此总体成本将是更有效的排序。

Answer 2

独立于实际执行这些交换计算交换数量是不可行的。

计算复杂性通常用Big-O Notation表示有几个原因，一个重要原因是事先很难对排序算法需要执行多少工作进行精确计算。

使用Big-O表示法来表示有关排序算法速度的指标。如果您需要精确测量，请为其提供一些类似于您希望在应用程序中看到的输入的样本输入，并跟踪完全对输入进行排序所需的交换数量。

Answer 3

正如用户463035818在评论中指出的那样，计算所需交换的数量与实际进行交换的数量相同，即您正在尝试解决您没有的问题。如果您正在寻找效率，那么您无法为冒泡排序做更多的事情。我唯一能想到进一步优化的是添加一个标志，指示交换是否发生。如果通过内部循环的单次传递没有发生交换，则排序完成，您可以在到达结束之前退出外部循环。请注意，如果仍然需要执行所有传递（最坏情况），则此解决方案的性能略差于原始解决方案。但是，对于已经排序的矢量的最佳情况，它应该在O（n）处运行。

int bubbleSortSwaps(std::vector<int> q)
{
    int count=0;
    for(size_t i=0; i<q.size(); i++)
    {
        bool swapped = false;
        for (size_t j=0; j<q.size()-i-1; j++)
        {
            if(q[j]>q[j+1])
            {
                swapped = true;
                std::swap(q[j],q[j+1]);
                count++;
            }
        }
        if (!swapped) // if no swap happened, it's sorted
        {
            break;
        }
    }
    return count;
}