数据结构实验之排序二：交换排序

快来打我* 2022-09-25 09:18 166阅读 0赞

## 数据结构实验之排序二：交换排序 ##

####  ####

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

冒泡排序和快速排序都是基于"交换"进行的排序方法，你的任务是对题目给定的N个（长整型范围内的）整数从小到大排序，输出用冒泡和快排对这N个数排序分别需要进行的数据交换次数。

## 输入 ##

连续多组输入数据，每组数据第一行给出正整数N(N ≤ 10^5)，随后给出N个整数，数字间以空格分隔。

## 输出 ##

输出数据占一行，代表冒泡排序和快速排序进行排序分别需要的交换次数，数字间以1个空格分隔，行末不得有多余空格。

## 示例输入 ##

8
    49 38 65 97 76 13 27 49

## 示例输出 ##

15 9

## 提示 ##

注意：数据相等时不做交换

## 来源 ##

xam

#include<bits/stdc++.h>
    using namespace std;
    
    int num;
    void sor(int b[],int l,int r)
    {
    
        int i=l,j=r,key=b[l];
        if(l>=r)
            return ;
        while(i<j)
        {
            while(i<j&&b[j]>=key)j--;
            if(b[i]!=b[j])
            {
                num++;
            }
            b[i]=b[j];
    
            while(i<j&&b[i]<=key)i++;
            if(b[i]!=b[j])
            {
                num++;
            }
            b[j]=b[i];
    
    
        }
        b[i]=key;
        sor(b,l,i-1);
        sor(b,i+1,r);
    }
    int mao(int n,int a[])
    {
        int i,j,t;
        int count=0;
        for(i=0; i<n-1; i++)
        {
            for(j=0; j<n-i-1; j++)
            {
                if(a[j]>a[j+1])
                {
                    t=a[j];
                    a[j]=a[j+1];
                    a[j+1]=t;
                    count++;
    
                }
            }
        }
    
        return count;
    }
    int main()
    {
        int n;
        int a[100009],b[100009];
        while(cin>>n)
        {
            num=0;
            for(int i=0; i<n; i++)
            {
                cin>>a[i];
                b[i]=a[i];
    
            }
            sor(b,0,n-1);
            cout<<mao(n,a)<<" "<<num<<endl;
    
    
        }
        return 0;
    }