萝卜的冒泡排序

题目描述

萝卜上次已经说过要给各位同学出一道冒泡排序，那么此题就以冒泡排序为主吧，可是实验室的学长学姐觉得学弟学妹们都很厉害，所以就加了各种各样的条件，最 终萝卜还是选择加一些条件，比如：让你直接排序输出结果就体现不出冒泡排序了。所以萝卜决定必须要用冒泡排序才能做出来的题目才叫冒泡排序的题目嘛？所以 这里只需要你在使用冒泡排序的时候统计交换的次数，在定义一个规则，如果存在相同的数，那么出现较早的那个数就排在后面。请帮萝卜解决这个问题吧。
输入
只有一组数据。
第一行一个n。（n<100）
接下来有n个数，表示要排序的数（不超过100）。
输出
输出交换的次数。

分析：此题绝对没有看上去那么简单，我们会发现，如果直接用一个冒泡是无法得到正确的答案的，因为，在判断时，我们不能把相同的数，一起判断，否则，就会重复多次。

代码如下：

#include"stdio.h"
int main()
{
    int n,a[101],i,j,m,t,q;
    scanf("%d",&n);
    {
        m=0;
        for(i=0; i<n; i++)
            scanf("%d",&a[i]);
        for(i=n-1; i>0; i--)
            for(j=0; j<i; j++)
            {
                if(a[j]>a[j+1])//在这里，我们没有将相等进行判断。
                {
                    t=a[j];
                    a[j]=a[j+1];
                    a[j+1]=t;
                    m++;
                }


            }
       
        q=1;//表示有几个相等的数。
        j=0;
        while(j!=n-1)//这里是针对相等的判断。
        {
            for(q=1; j<n-1; j++)//注意表达式1，我们将q=1。以保证每次能得到最好的结果。
                if(a[j]==a[j+1])//相等q++；
                {
                    q++;
                }
                else
                {
                    j++;
                    break;
                }
            while(q--)//如果有3个数相等，则要交换2+1次。四个数，则交换3+2+1次
            {
                m=m+q;
            }
        }
    }

    printf("%d\n",m);
}