冒泡排序和快速排序都是基于"交换"进行的排序方法，你的任务是对题目给定的N个（长整型范围内的）整数从小到大排序，输出用冒泡和快排对这N个数排序分别需要进行的数据交换次数。
连续多组输入数据，每组数据第一行给出正整数N(N ≤ 10^5)，随后给出N个整数，数字间以空格分隔。
输出数据占一行，代表冒泡排序和快速排序进行排序分别需要的交换次数，数字间以1个空格分隔，行末不得有多余空格。
#include <stdio.h> #include <string.h> int count1=0,count2=0; //计数count1-快排 count2-冒泡 /* int sort(int r,int l,int key) //快速查找 {int i=r,j=l;int mid=(i+j)/2;while(r<=l){mid = (i+j)/2;if(a[mid]==key)return mid;else if(a[mid]>key){return sort(i,mid-1,key);}else{return sort(mid+1,j,key);}}return -1; } void qsort1(int a[],int l,int r) //快速排序 { int x=a[l],i=l,j=r;if(l>=r)return ;while(i<j){while(i<j && a[j]>=x){j--;}a[i] = a[j];while(i<j && a[i]<=x){i++;}a[j] = a[i];count1++;}a[i] = x;qsort1(a,l,i-1);qsort1(a,i+1,r); } */ void Bubble_sort(int a[],int n) {int i,j,t;for(i=0;i<n-1;i++){for(j=0;j<n-1-i;j++){if(a[j]>a[j+1]){t = a[j];a[j] = a[j+1];a[j+1] = t;count2++;}}} } void sort(int *a,int left,int right) { if(left<right) { int i=left; int j=right; int key=a[left]; while(i<j) { while(i<j&&key<=a[j]) { j--; } if(a[i]!=a[j]) count1++; a[i]=a[j]; while(i<j&&key>=a[i]) { i++; } if(a[i]!=a[j]) count1++; a[j]=a[i]; } a[i]=key; sort(a,left,i-1); sort(a,i+1,right); } } int main() {int n,i,j,m; int a[10002],b[10002];int count=0; //记录查找次数int t,k;int flag=1;while(scanf("%d",&m)!=EOF){flag=1; count2 = count1=0;//初始化for(i=0;i<m;i++){scanf("%d",&a[i]);b[i] = a[i];}//b[i]='\0';sort(a,0,m-1);Bubble_sort(b,m);printf("%d %d\n",count2,count1); //代表冒泡排序和快速排序进行排序分别需要的交换次数}return 0; }
转载于:https://www.cnblogs.com/CCCrunner/p/6444621.html
相关资源：JAVA上百实例源码以及开源项目