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

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

Time Limit:?1000 ms?Memory Limit:?65536 KiB

Submit?Statistic

Problem Description

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

Input

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

Output

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

Sample Input

8

49 38 65 97 76 13 27 49

Sample Output

15 9

#include

using namespace std;

int a[100000],b[100000];

int sum,sum1;

void bsort(int a[],int n)

{

int i,j,t;

for(i=0; i

{

for(j=0; j

{

if(a[j]>a[j+1])

{

t = a[j];

a[j] = a[j+1];

a[j+1] = t;

sum++;

}

}

}

}

void qsort(int a[],int l,int r)

{

int key = a[l];

int i = l,j = r;

while(i < j)

{

while(i=key)

j--;

if(a[i]!=a[j])

{

a[i] = a[j];

sum1++;

}

while(i

i++;

if(a[i]!=a[j])

{

a[j] = a[i];

sum1++;

}

}

a[i] = key;

if(l

{

qsort(a,l,i-1);

qsort(a,i+1,r);

}

}

int main()

{

int i,n;

while(cin>>n)

{

for(i=0; i

{

cin>>a[i];

b[i] = a[i];

}

sum = sum1 = 0;

qsort(a,n-1);

bsort(b,n);

cout<

}

return 0;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!