[セットトップ]もう一つのプログラミング面接問題

タイトルと要求:1つの文字列の大文字を文字列の後ろに置いて、各文字の相対的な位置は変わらず、追加の空間を申請することはできません. 
私の実装はバブルソートに似ています.

#include <stdio.h>
#include <string.h>

//	Author: 397090770
//	E-mail:[email protected]
//	Date:  2012/09/29
 
//      ：                   ，
//           ，         。 


//          
int isUpperAlpha(char c){
	if(c >= 'A' && c <= 'Z'){
		return 1;
	}
	return 0; 
}

//       
void swap(char *a, char *b){
	char temp = *a;
	*a = *b;
	*b = temp;
} 

char * mySort(char *arr, int len){
	if(arr == NULL || len <= 0){
		return NULL;
	}
	
	int i = 0, j = 0, k = 0;
	for(i = 0; i < len; i++){
		for(j = len - 1 - i; j >= 0; j--){
			if(isUpperAlpha(arr[j])){
				for(k = j; k < len - i - 1; k++){
					swap(&arr[k], &arr[k + 1]);
				}
				break;
			}
			//        ，         ，          
			if(j == 0 && !isUpperAlpha(arr[j])){
				//goto over;
                           return arr;
			}
		}
	}
	
	//over: 
	return arr;
}

int main(){
	char arr[] = "aaaaaaaaaaaaaaaaaaaaaaaAbcAdeBbDc";
	printf("%s
", mySort(arr, strlen(arr)));
	return 0;
}

運転結果:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcdebcAABD
後で考えて、コードを最適化しました(最適化されていないようで、上との差は多くありません).以下のようにします.

#include <stdio.h>
#include <string.h>

//	Author: 397090770
//	E-mail:[email protected]
//	Date:  2012/09/29
 
//      ：                   ，
//           ，         。 


//          
int isUpperAlpha(char c){
	if(c >= 'A' && c <= 'Z'){
		return 1;
	}
	return 0; 
}

//       
void swap(char *a, char *b){
	char temp = *a;
	*a = *b;
	*b = temp;
} 

char * mySort(char *arr, int len){
	if(arr == NULL || len <= 0){
		return NULL;
	}
	
	int i = 0, j = 0, k = 0;
	//for(i = 0; i < len; i++){
		for(j = len - 1 - i; j >= 0; j--){
			if(isUpperAlpha(arr[j])){
				for(k = j; k < len - i - 1; k++){
					swap(&arr[k], &arr[k + 1]);
				}
				i++;
				j = len - 1 - i; 
				//break;
			}
			//        ，         ，          
			if(j == 0 && !isUpperAlpha(arr[j])){
				//goto over;
                           return arr;
			}
		}
	//}
	
	//over: 
	return arr;
}

int main(){
	char arr[] = "GaaaaBGaaaaaaaaaaaaaaaaaAbcAdeBbDc";
	printf("%s
", mySort(arr, strlen(arr)));
	return 0;
}

2番目のforループでは、毎回末尾から開始され、時間がかかります.そのため、大文字を見つけた位置を保存する変数を設定しました.これにより、次のループでは、ここから前へループする必要があります.

int tempIndex = len - 1; 
	for(i = 0; i < len; i++){
		for(j = tempIndex; j >= 0; j--){
			if(isUpperAlpha(arr[j])){
				tempIndex = j - 1;
				for(k = j; k < len - i - 1; k++){
					swap(&arr[k], &arr[k + 1]);
				} 
				break;
			}
			//        ，         ，          
			if(j == 0 && !isUpperAlpha(arr[j])){
				return arr;
			}
		}
	}

しかし、時間の複雑さが高いようで、どの牛がもっと良い方法があるか分かりません.指導を求める...