全球设计网分站/网络app推广是什么工作

冒泡排序

题目链接：http://47.96.116.66/problem.php?cid=2082&pid=9

题目大意：对n个数排序

排序思想：每次操作吧最大的数移到最后，然后之后不管那个数，处理前n-1个。重复此操作

代码：

/*
我的想法是从小到大排，总共进行n次，首先处理0~n-1将最大数逐渐换到最后一位，然后处理0~n-2，将第二大的数放到倒数第二位....依此类推对于每一层，比方说第一层，我们是怎么把最大的数放到最后一位的呢？
我们从左开始遍历，每次处理相邻的两个数，如果右边比左边小，就把左边的数换到右边，这样是不是就能把最大的数换到右边了？冒泡最坏情况：排序 5 4 3 2 1，
*/#include<stdio.h>int main()
{int n;while (scanf("%d",&n)!=EOF){int a[100];for (int i=0;i<n;i++) scanf("%d",&a[i]);//输入for (int i=0;i<n;i++){//i表示进行第几次for (int j=0;j<n-1-i;j++){//表示需要遍历到的位置if (a[j]>a[j+1]){int t = a[j];a[j] = a[j+1];a[j+1] = t;}}}for (int i=0;i<n;i++){printf("%d ",a[i]);}printf("\n");}return 0;
}

直接插入排序

题目链接：http://47.96.116.66/problem.php?cid=2082&pid=13

题目大意：对n个数从小到大插入排序，并输出排序过程中的比较次数。

排序思想：每新增一个数，在已有数组中找到对应位置（即比前一个大比后一个小的位置）并放入。

代码：

/*
本题插入排序的思路：当前要插入的数x，去遍历当前数组，从右往左（当然可以从左往右但是题目样例的三次是从右往左才能计算出来）
找到第一个大于等于的位置把这个位置之后（不包括该位置）的元素往后挪一个，把当前x放进去
*/#include<stdio.h>int main()
{int t,n,a[2000];scanf("%d",&t);for (int tt=1;tt<=t;tt++){scanf("%d",&n);scanf("%d",&a[0]);int ans = 0;for (int i=1;i<n;i++){int x,idx = 0;//idx表示当前x要在的位置,由于下一个数在已有数组中从右往左找，所以初始化为最坏情况0scanf("%d",&x);for (int j=i-1;j>=0;j--){ans++;if (x>=a[j]) {//找要找到第一个>=的位置，那么插在这个数后面即可。找到位置并直接退出idx = j+1;break;}}for (int j=i-1;j>=idx;j--){//都右移，把idx这个位置腾出来a[j+1] = a[j]; }a[idx] = x;}printf("%d\n",ans);for (int i=0;i<n;i++) printf("%d ",a[i]);printf("\n");}return 0;
}