1.归并排序主要运用到的的思想分治、递归功能1.数组进行排序。2.计算数组中的逆序对的个数。时间复杂度稳定的Onlogn空间复杂度On附上模板代码#includebits/stdc.husingnamespacestd;longlongMerge(inta[],intb[],ints,intm,inte){intis,jm1,ks;longlongans0;while(imje){if(a[i]a[j])b[k]a[i];else{b[k]a[j];//求逆序对ansmid-i1;}}while(im)b[k]a[i];while(je)b[k]a[j];for(intns;ne;n)a[n]b[n];returnans;}voidmergesort(inta[],intb[],ints,inte){longlongans0;if(se){intm(se)/2;mergesort(a,b,s,m);mergesort(a,b,m1,e);ansMerge(a,b,s,m,e);}}inta[100005];intb[100005];intmain(){intn;cinn;for(inti1;in;i){cina[i];}mergesort(a,b,1,n);for(inti1;in;i){couta[i] ;}return0;}2.冒泡排序主要思想不断交换相邻两个逆序的元素。最终将最大排在最后类似于可乐冒泡。时间复杂度On²)空间复杂度On#includebits/stdc.husingnamespacestd;voidbubbleSort(inta[],intn){for(inti1;in;i){//n-1趟for(intj1;jn-i1;j){//除去已经排好的i个所以是枚举n-i1个if(a[j1]a[j]){intta[j1];a[j1]a[j];a[j]t;}}}}inta[100005];intmain(){intn;cinn;for(inti1;in;i){cina[i];}bubbleSort(a,n);for(inti1;in;i){couta[i] ;}return0;}3.选择排序主要思想通过与n次n为数组的长度的选择可以将每次当前为选择的最大最小的元素放在相应位置上。时间复杂度On²)空间复杂度On#includebits/stdc.husingnamespacestd;voidselectSort(inta[],intn){for(inti1;in;i){intMini;for(intji1;jn;j){if(a[j]a[Min]){Minj;}}intta[Min];a[Min]a[i];a[i]t;}return;}inta[100005];intmain(){intn;cinn;for(inti1;in;i){cina[i];}selectSort(a,n);for(inti1;in;i){couta[i] ;}return0;}4.插入排序主要思想两层for循环第一层表示接下来要将前i个排好序第二个for循环用于通过比较判断第i个元素应该放在1~i的哪个位置上时间复杂度On²)空间复杂度On#includebits/stdc.husingnamespacestd;voidInsertSort(vectorinta,intlen){for(inti1;ilen;i){inttempa[i];for(intji-1;j0;--j){if(tempa[j]){a[j1]a[j];}else{a[j1]temp;break;}}}return;}intmain(){intn;cinn;vectorinta(n);for(inti0;in;i){cina[i];}InsertSort(a,n);for(inti0;in;i){couta[i] ;}return0;}5.希尔排序主要思想可以认为是插入排序的plus版内部多了有个增量因子i3*i1作为每轮插入排序中第二个for‘循环每次结束后的增加量时间复杂度On^1.5)左右空间复杂度On#includebits/stdc.husingnamespacestd;typedeflonglongll;constintMAXN100005;inta[MAXN],n;voidinsertionSort(inta[],intn,intg){for(inti1g;in;i){inttempa[i],ji-g;for(;j1;j-g){if(a[j]temp){a[jg]a[j];}elsebreak;}a[jg]temp;}}voidshellSort(inta[],intn){vectorintG;for(inti1;in;){G.push_back(i);i3*i1;}for(intiG.size()-1;i0;i--){insertionSort(a,n,G[i]);}}intmain(){scanf(%d,n);for(inti1;in;i){scanf(%d,a[i]);}shellSort(a,n);for(inti1;in;i){printf(%d ,a[i]);}return0;}
