大寫字母后排的解決算法

1、一道編程賽題大寫字母后排題目以及要求：把一個(gè)字符串的大寫字母放到字符串的后面，各個(gè)字符的相對(duì)位置不變，不能申請(qǐng)額外的空間。 以下是我的算法：/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：需要字符串排序的數(shù)組，f，左下表，r：右下標(biāo)int mySort(char*cs,int f,int r);void swap(char*,char*);int test(TFUN

2、 t);/測(cè)試程序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部分翻轉(zhuǎn)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)/返回大寫字母?jìng)€(gè)數(shù)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);/后半部分排序,小寫字母?jìng)€(gè)數(shù)if(k1>0&&k2>0)/如果前半部分有大寫字符串或者后半部分有小寫字符串，則兩者交換位置int b=m-k1+1;/交換起始點(diǎn)int e=m+k2;/交換終點(diǎn)sum+=e-b+1;reverse_ex(cs,b,e);/csb:e翻轉(zhuǎn)，前部分是大寫字母，后半部分是小寫字母 reverse_ex(cs,b,b+k2-1);/cs小寫字母翻轉(zhuǎn)reverse_ex(cs,b+k2,e);/cs大寫字母翻轉(zhuǎn)

5、return k1+tr-m-k2;/檢查排序前后元素是否相對(duì)位置保持一致/cs：排序后數(shù)組，cp原數(shù)組/len，字符串長(zhǎng)度，upn，大寫字符個(gè)數(shù)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+)/生成一個(gè)隨機(jī)數(shù)組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;/查看算法的時(shí)間復(fù)雜度，由結(jié)果可以看出復(fù)雜度是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 這是另一個(gè)人給出的算法，就暫時(shí)冒犯一下版權(quán)，借用一下哈#include <stdio.h> #include <string.h> #include"test_char_exchange.h" / Author: 397090770 / E-mail:wyphao.2007 / Date: 2012/09/29 /題目以及要求：把一個(gè)字符串的大寫字母放到字符串的后面， /各個(gè)字符的相對(duì)位置不變，不能申請(qǐng)額外的空間。 /判斷是不是大寫字母 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; /遍歷完了字符數(shù)組，但是沒發(fā)現(xiàn)大寫字母，所以沒必要再遍歷下去 if(j = 0 && !isUpperAlpha(arrj) return 0; return 0; 好了，貼了那么多代碼，該看看效果了啊這是1000個(gè)字母的結(jié)果：從上圖可以看到，完成這個(gè)排序用了4655個(gè)單位時(shí)間再來看看10000個(gè)字母的排序結(jié)果咯：哇，這個(gè)字母可是太多了，只好一個(gè)個(gè)張貼了媽呀，終于貼完了，真的是太多了，這個(gè)一萬個(gè)字母真不是蓋的啊，我們看看結(jié)果：用

11、了62478個(gè)單位時(shí)間，和1000個(gè)字母相比，數(shù)量是后者的十倍，而所用時(shí)間，也差不多是十倍，再多十倍的字母，所用時(shí)間也差不多就是十倍，這個(gè)足以說明O（nlogn）和線性相差多接近了。這點(diǎn)時(shí)間，可以說忽略不計(jì)，就是轉(zhuǎn)眼間完成。我們?cè)倏纯戳硪粋€(gè)算法這個(gè)算法復(fù)雜度是O(n3)，看看所用時(shí)間吧由于這個(gè)復(fù)雜度太高，我們先用100字母試試：嗯，這個(gè)計(jì)算時(shí)間是26420個(gè)單位時(shí)間，這才100個(gè)字母，用的時(shí)間就已經(jīng)不少了，再看看500個(gè)字母吧這時(shí)間就已經(jīng)飆升到5822562個(gè)單位時(shí)間了，可以想象，如果數(shù)量再多點(diǎn)，就會(huì)什么結(jié)果了。現(xiàn)在來看看我的算法是怎么做到幾乎線性時(shí)間排序的（實(shí)際上是O(nlogn)）思路是這樣的：將一段要排序的字母串分成兩半，分別排序，然后的問題就是如何把這兩半字母串合并起來成為一個(gè)排好序的字母串。其實(shí)這里要做