在不进行冒泡排序的情况下，计算数组中冒泡排序交换的次数

Question

你好，我正在尝试计算大小为N的数组中的bubblesort交换数量，但我想在不进行bubblesort.我听说过合并排序，有人已经告诉我这是某种合并排序修改。。。我不想使用这个基本算法>

void bubbleSort(int * array, int size){
    for(int i = 0; i < size - 1; i++){
        for(int j = 0; j < size - i - 1; j++){
            if(array[j+1] < array[j]){
                int tmp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = tmp;
            }   
        }   
    }   
}  

你们有人知道吗？

Answer 1

似乎可以使用以下函数来计算掉期的总数：

int calcSwaps(int *array, int size) {
    int cnt = 0;
    for (int i = 0; i + 1 < size; ++i) {
        for (int j = i + 1; j < size; ++j) {
            if (array[j] < array[i]) {
                ++cnt;
            }
        }
    }
    return cnt;
}

主要思想是，在这种类型的排序中，每个元素array[i]将与所有元素array[j]、j > i、array[j] < array[i]交换。

编辑

我会尽量更仔细地解释，以免引起误解。解决方案相当简单。考虑冒泡排序算法。让我们看看初始的未排序数组。如果我们有array[i]元素，它会被交换多少次？好的，如果array[j] > array[j + 1]，我们交换元素array[j]和array[j + 1]。根据所选择的排序算法，每两个元素最多可以交换一次。此外，如果array[i] > array[j], i < j，它们将被交换，因为我们希望最终得到一个排序的数组。很容易看出，在这种情况下，我们只需要得到每个元素array[i]，计算array[j], array[j] < array[i], j > i的数量（这将是在排序过程中与array[i]交换的元素数量），最后将每个array[i]的所有这些数字相加即可得到答案。

Answer 2

修改合并排序，以便除了对其输入进行排序外，还可以计算该数组中的反转数。让我们用归纳法来证明它。

基本情况：如果阵列大小小于或等于1 ，则容易返回0反转

一般情况：让我们一步一步地分析这个问题。

我们有两个数组要合并。可能存在什么样的反转？反转（i，j）可以在同一半（左半或右半），或者i可以在左半，j可以在右半（i不能在右半，因为我们有约束i<j）。然而，根据归纳假设，数组左半部分和右半部分内的反转次数将由对数组每一半的递归调用返回，因此我们只需要计算两半的反转次数（i在左，j在右）。

我们如何计算左右数组的反转次数？在合并排序的合并步骤中，我们得到了一个两个排序的数组（左和右）。对于左数组中的每个元素left[i]，我们想知道右数组中有多少元素right[j]严格小于left[i]请注意，当我们将left[i]插入合并数组时，我们知道j左边的每个元素都小于left[i]（因为它们是在left[i]之前插入合并数组的）。因此，每次将left[i]插入合并数组时，计数器都会增加j。

#include <stdio.h>
long long int MS(int a[],int temp[],int left,int right);
long long int Merge(int a[],int temp[],int left,int mid,int right);
long long int MS(int a[],int temp[],int left,int right)
{
    long long int cnt=0;
    int mid;
    if(right>left)
    {
        mid=(right+left)/2;
        cnt=MS(a,temp,left,mid);
        cnt+=MS(a,temp,mid+1,right);
        cnt+=Merge(a,temp,left,mid+1,right);
    }
    return cnt;
}
long long int Merge(int a[],int temp[],int left,int mid,int right)
{
    int i,j,k;
    long long int cnt=0;
    i=left;
    j=mid;
    k=left;
    while(i<=mid-1 && j<=right)
    {
        if(a[i]<=a[j])
            temp[k++] = a[i++];
        else
        {
            temp[k++] = a[j++];
            cnt+=(mid-i);
        }
    }
    while (i<=mid-1)
        temp[k++]=a[i++];
    while(j<=right)
        temp[k++]=a[j++];
    for(i=left;i<=right;i++)
        a[i]=temp[i];
    return cnt;
}
int main()
{
    int *a,*tmp,t,n;
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%d",&n);
        a=new int [n];
        tmp=new int [n];
        for(int j=0;j<n;j++)
            scanf("%d",&a[j]);
        printf("%lldn",MS(a,tmp,0,n-1));
    }
    return 0;
}

Answer 3

注意：这似乎有效，但我不确定我的方法是否正确！

让我们举一个数组的例子：

{3, 5, 1, 4, 2}

找到最小元素的index。要将其移动到数组的开头，需要index交换。在我的示例中，1是最小的元素，1和index 2是最小的元件，因此需要2次交换才能将其放置在正确的位置。之后，我们有：

{1, 3, 5, 4, 2}

1现在位于正确的位置，因此我们可以将注意力集中在阵列的其余部分以保持简单：

{3, 5, 4, 2}

代码：

#include <algorithm>
#include <vector>
unsigned swaps(std::vector<double>& data) {
    unsigned result = 0;
    while (!data.empty()) {
        auto smallest = std::min_element(data.begin(), data.end());
        result += smallest - data.begin();
        data.erase(smallest);
    }
    return result;
}

看到它工作（希望正确）在线

Answer 4

您可以执行三个简单的步骤。复制输入数组，然后每次交换时递增一个计数器并返回该计数。比如：

int bubbleSort(int * array, int size){
    std::vector<int> temp_array(array, array + size);
    int count{0};
    for(int i = 0; i < size - 1; i++){
        for(int j = 0; j < size - i - 1; j++){
            if(temp_array[j+1] < temp_array[j]){
                int tmp = temp_array[j + 1];
                temp_array[j + 1] = temp_array[j];
                temp_array[j] = tmp;
                count++;
            }
        }
    }
    return count;
}