怎样给网站做排名优化,百度一下你就知道了主页,做展会怎么引流到自己的网站,网站分析及推广方案归并排序
题目1#xff1a;归并排序
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式 输入共两行#xff0c;第一行包含整数 n。
第二行包含 n 个整数#xff08;所有整数均在 1∼109 范围…归并排序
题目1归并排序
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式 输入共两行第一行包含整数 n。
第二行包含 n 个整数所有整数均在 1∼109 范围内表示整个数列。
输出格式 输出共一行包含 n 个整数表示排好序的数列。
数据范围 1≤n≤100000 输入样例 5 3 1 2 4 5 输出样例 1 2 3 4 5
#includeiostream
#includecstring
#includealgorithmusing namespace std;const int N 100010;int q[N],tmp[N];int n;void merge_sort(int q[], int l, int r){if(lr) return;int mid lr 1;merge_sort(q,l,mid)merge_sort(q,mid1,r);//i和j相当于一个双指针指向当前需要排序的数组的两个部分。int il,jmid1;int k0;while(imid jr){if(q[i]q[j]) tmp[k] q[i];else tmp[k] q[j];}while(imid) tmp[k] q[i];while(jr) tmp[k] q[j];//注意这里的l和r是相对于原始的q数组的位置而tmp保存的值只是当前指针指向的这两个部分的排好序的值。for(int il,j0;ir;i,j) q[i]tmp[j];
}int main(){int n;cinn;for(int i0;in;i) scanf(%d, q[i]);merge_sort(q,0,n-1);for(int i0; in;i) printf(%d ,q[i]);return 0;}
算法思想 归并排序也是基于分治的思想但是与快速排序不同的是归并排序是先分治再排序先递归再比较。而快速排序是先排序再分治先比较再递归从总体来说归并排序的计算是自底向上的而快速排序的计算是自顶向下的。由于归并排序在排序的过程中对数组的划分是固定的快速排序不是固定的与选择的基准点有关所以归并排序的复杂度是固定的。 复杂度分析归并排序Merge Sort是一种典型的分治算法其时间复杂度和空间复杂度如下 时间复杂度最好情况下归并排序的时间复杂度为O(nlogn)最坏和平均情况下归并排序的时间复杂度也为O(nlogn)。 空间复杂度归并排序的空间复杂度为O(n)因为在合并过程中需要额外的空间存储左右两个子序列的元素。 具体的分析过程如下 1.归并排序首先将待排序序列均分为两个子序列然后分别对这两个子序列进行排序最后将排序好的子序列进行合并。这个过程可以递归进行直到子序列的长度为1此时可以认为子序列已经排好序。 2.在最好情况下即待排序序列已经排好序时每次递归的两个子序列都是有序的。这时归并排序的时间复杂度为O(n)。因为无论序列长度为多少都只需要进行一次合并操作。 3.在最坏和平均情况下即待排序序列完全无序或部分有序时每次递归的两个子序列都需要进行排序。这时归并排序的时间复杂度为O(nlogn)。因为每次递归都需要将序列均分为两个子序列然后对这两个子序列进行排序。这个过程可以看作是对元素数量的对数级别的递归调用。 在空间复杂度方面由于归并排序需要额外的空间存储左右两个子序列的元素因此空间复杂度为O(n)。
题目2归并排序的应用-逆序对的数量
给定一个长度为 n 的整数数列请你计算数列中的逆序对的数量。
逆序对的定义如下对于数列的第 i 个和第 j 个元素如果满足 ij 且 a[i]a[j]则其为一个逆序对否则不是。
输入格式 第一行包含整数 n表示数列的长度。
第二行包含 n 个整数表示整个数列。
输出格式 输出一个整数表示逆序对的个数。
数据范围 1≤n≤100000 数列中的元素的取值范围 [1,109]。
输入样例 6 2 3 4 5 6 1 输出样例 5
//在分治后的每一层合并中顺便求出逆序对数量是这个题想法的由来归并排序分治我们求的是从小到
//大的顺序我们所求的逆序对恰好是逆序数量与归并排序不谋而合。#includeiostream
#includecstring
#includealgorithm
#includecstdiousing namespace std;const int N 100000;int q[N],f[N];long long res0;long long merge_sort(int l,int r){if(lr) return 0;int mid(lr)1;resmerge_sort(l,mid)merge_sort(mid1,r);int k0,il,jmid1;while(imidjr){if(q[i]q[j]) f[k]q[i];else{//当前i后面的数都比j大而且每个数组段在排序的过程中都是排好序的由更小的数组段合并来的所以逆序数加上mid-i1。resmid-i1;f[k]q[j];}}while(imid) f[k]q[i];while(jr) f[k]q[j];for(int il,j0;ir;i,j) q[i]f[j];return res;
}int main(){int n;cinn;for(int i0;in;i) scanf(%d,q[i]);merge_sort(0,n-1);printf(%lld,res);return 0;
}
