数据结构实验之排序二：交换排序 (SDUT 3399)

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//int sum = 0;
int a[100004];  //题目是长整型，不过这里 int 也可以。。
int b[100005];


void qusort(int l, int r, int a[], int &sum)  //这里如果不想传sum，就把sum定义成全局，如注释
{
    int i = l, j = r;
    int x = a[i];
    if(i >= j) return ;
    while(i < j)
    {
        while(i < j && a[j] >= x) j --;
        if(a[j] != a[i]) sum ++;
        a[i] = a[j];
        while(i < j && a[i] <= x) i ++;
        if(a[j] != a[i]) sum ++;
        a[j] = a[i];
    }
    a[i] = x;
    qusort(l,i-1,a,sum);
    qusort(i+1,r,a,sum);
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i = 0; i < n; i ++)
        {
            scanf("%d",&a[i]);
            b[i] = a[i];
        }
        int num = 0; // 冒泡
        int sum = 0; //快排

        for(int i = 0; i < n; i ++)
        {
            for(int j = 0; j < n - i - 1; j ++)
            {
                if(a[j] > a[j +1])
                {
                    int t = a[j];
                    a[j] =  a[j + 1];
                    a[j + 1] = t;
                    num ++;
                }
            }
        }
        qusort(0,n-1,b,sum);
        printf("%d %d\n",num,sum);
    }
    return 0;
}