大写字母后排的解决算法

1、一道编程赛题大写字母后排题目以及要求：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，不能申请额外的空间。 以下是我的算法：/test_char_exchange.h#ifndef _TEST_EXCHANGE_#define _TEST_EXCHANGE_typedef int (*TFUN)(char*,int,int);int exchange(char*cs,int f,int r);/cs：需要字符串排序的数组，f，左下表，r：右下标int mySort(char*cs,int f,int r);void swap(char*,char*);int test(TFUN

2、 t);/测试程序int test2();extern long sum;#endif/test_char_exchange.cpp#include"test_char_exchange.h"#include<stdlib.h>#include<stdio.h>#include<math.h>int isup(char c)return c>='A'&&c<='Z'?1:0;void swap(char *c1,char *c2)int t=*c1;*c1=*c2;*c2=t;/

3、csb:e部分翻转void reverse_ex(char*cs,int b,int e)while(b<e)swap(&csb+,&cse-);long sum=0;int exchange(char*cs,int f,int r)/返回大写字母个数if(f=r)return isup(csf);while(f<r&&(!isup(csf)f+;if(f=r)return isup(csf);int tr=r;while(r>f&&isup(csr)r-;if(f=r)return isup(csf)+tr-r;int m=(

4、f+r)/2;int k1=exchange(cs,f,m);/前半部分排序int k2=r-m-exchange(cs,m+1,r);/后半部分排序,小写字母个数if(k1>0&&k2>0)/如果前半部分有大写字符串或者后半部分有小写字符串，则两者交换位置int b=m-k1+1;/交换起始点int e=m+k2;/交换终点sum+=e-b+1;reverse_ex(cs,b,e);/csb:e翻转，前部分是大写字母，后半部分是小写字母 reverse_ex(cs,b,b+k2-1);/cs小写字母翻转reverse_ex(cs,b+k2,e);/cs大写字母翻转

5、return k1+tr-m-k2;/检查排序前后元素是否相对位置保持一致/cs：排序后数组，cp原数组/len，字符串长度，upn，大写字符个数int issorted(char*cs,char*cp,int len,int upn)int p=0;/检查小写字母for(int k=0;k<len-upn;k+)while(p<len&&cpp!=csk)p+;if(p=len)return 0;p=0;/检查大写字母for(;k<len;k+)while(p<len&&cpp!=csk)p+;if(p=len)return 0;ret

6、urn 1;#define MLEN 1000int test(TFUN t)char csMLEN+1=""char cpMLEN+1;for(int k=0;k<1;k+)/生成一个随机数组for(int j=0;j<MLEN;j+)int m=rand()%100;if(m>50)csj=m%25+'a'elsecsj=m%25+'A'cpj=csj;printf("n %s n",cs);char c;printf("任意输入则开始!n");scanf("%c&quo

7、t;,&c);int bg;bg=0;while(!isup(csbg)bg+;int len=(*t)(cs,bg,MLEN-1);int p=0,q=MLEN-1;/检查是否所有大写字母都后排while(!isup(csp)&&p<MLEN)p+;while(isup(csq)&&q>=0)q-;if(p-q!=1)return 0;/查看算法的时间复杂度，由结果可以看出复杂度是O(nlogn)printf("%ld,%lfn",sum,(double)sum/(MLEN*log(MLEN);if(!issorted(

8、cs,cp,MLEN,len)return 0;return 1;/test_ex2.cpp 这是另一个人给出的算法，就暂时冒犯一下版权，借用一下哈#include <stdio.h> #include <string.h> #include"test_char_exchange.h" / Author: 397090770 / E-mail:wyphao.2007 / Date: 2012/09/29 /题目以及要求：把一个字符串的大写字母放到字符串的后面， /各个字符的相对位置不变，不能申请额外的空间。 /判断是不是大写字母 int isUppe

9、rAlpha(char c) if(c >= 'A' && c <= 'Z') return 1; return 0; int mySort(char *arr,int bg, int slen) if(arr = NULL | slen <= 0) return 0; int len=slen+1;sum=0; int i = 0, j = 0, k = 0; for(j = len - 1 - i; j >= 0; j-) if(isUpperAlpha(arrj) for(k = j; k < len - i

10、- 1; k+) swap(&arrk, &arrk + 1); sum+=len-i-j; i+; j = len - 1 - i; /遍历完了字符数组，但是没发现大写字母，所以没必要再遍历下去 if(j = 0 && !isUpperAlpha(arrj) return 0; return 0; 好了，贴了那么多代码，该看看效果了啊这是1000个字母的结果：从上图可以看到，完成这个排序用了4655个单位时间再来看看10000个字母的排序结果咯：哇，这个字母可是太多了，只好一个个张贴了妈呀，终于贴完了，真的是太多了，这个一万个字母真不是盖的啊，我们看看结果：用

11、了62478个单位时间，和1000个字母相比，数量是后者的十倍，而所用时间，也差不多是十倍，再多十倍的字母，所用时间也差不多就是十倍，这个足以说明O（nlogn）和线性相差多接近了。这点时间，可以说忽略不计，就是转眼间完成。我们再看看另一个算法这个算法复杂度是O(n3)，看看所用时间吧由于这个复杂度太高，我们先用100字母试试：嗯，这个计算时间是26420个单位时间，这才100个字母，用的时间就已经不少了，再看看500个字母吧这时间就已经飙升到5822562个单位时间了，可以想象，如果数量再多点，就会什么结果了。现在来看看我的算法是怎么做到几乎线性时间排序的（实际上是O(nlogn)）思路是这样的：将一段要排序的字母串分成两半，分别排序，然后的问题就是如何把这两半字母串合并起来成为一个排好序的字母串。其实这里要做