Expressão Regular Alfanumerico + espaço + acentuação

String s = "Gisele Bündchen da Conceição Nascimento";
String t = funcao (s);
System.out.println (t);

String rua="Av. Andrómêda, 2247 - SP"

import java.util.regex.*;

public class RegexRemoverAcentos
{
    public static void main( String args[] )
    {
        String texto = "Av. Andrómêda, 2247 - SP" ; 
        Pattern regra = Pattern.compile( "[\\p{Alnum} ]" );
        
        String saida = "";
        
        for( int i = 0; i < texto.length(); i++ )
        {
            Matcher mt = regra.matcher( Character.toString( texto.charAt( i ) ) );
            if( mt.matches() )
            {
                saida += mt.group();
            }else{
                if( !( Character.isLetter( texto.charAt( i ) ) ) )
                {
                    continue;
                }
                
                String aux = Character.toString( texto.charAt( i ) );
                boolean upperCaseFlag = false;
                
                if( Character.isUpperCase( aux.charAt( 0 ) ) )
                {
                    upperCaseFlag = true;
                    aux = aux.toLowerCase();
                }
                
                aux = aux.replace( 'à', 'a' );
                aux = aux.replace( 'è', 'e' );
                aux = aux.replace( 'ì', 'i' );
                aux = aux.replace( 'ò', 'o' );
                aux = aux.replace( 'ù', 'u' );
                
                aux = aux.replace( 'á', 'a' );
                aux = aux.replace( 'é', 'e' );
                aux = aux.replace( 'í', 'i' );
                aux = aux.replace( 'ó', 'o' );
                aux = aux.replace( 'ú', 'u' );
                
                aux = aux.replace( 'â', 'a' );
                aux = aux.replace( 'ê', 'e' );
                aux = aux.replace( 'î', 'i' );
                aux = aux.replace( 'ô', 'o' );
                aux = aux.replace( 'û', 'u' );
                
                aux = aux.replace( 'ã', 'a' );
                aux = aux.replace( 'õ', 'o' );

                aux = aux.replace( 'ä', 'a' );
                aux = aux.replace( 'ë', 'e' );
                aux = aux.replace( 'ï', 'i' );
                aux = aux.replace( 'ö', 'o' );
                aux = aux.replace( 'ü', 'u' );
                
                aux = aux.replace( 'ç', 'c' );
                
                
                if( upperCaseFlag )
                {
                    
                    aux = aux.toUpperCase();
                    
                }
                
                saida += aux;                
            }
        }
        System.out.println( saida );
    }
}

// Remove todos . da string
		ret = ret.replaceAll("\\.?", "");
		// Remove todas , da string
		ret = ret.replaceAll(",?", "");
		// Remove todas - da string
		ret = ret.replaceAll("-?", "");
		// Remove todas : da string		
		ret = ret.replaceAll(":?", "");
		// Remove todas ( da string
		ret = ret.replaceAll("\\(?", "");
		// Remove todas ) da string
		ret = ret.replaceAll("\\)?", "");
		// Remove todas ª da string
		ret = ret.replaceAll("ª?", "");
		// Remove todas | da string
		ret = ret.replaceAll("\\|?", "");
		// Remove todas \ da string		
		ret = ret.replaceAll("\\\\?", "");
		// Remove todas º da string
		ret = ret.replaceAll("º?", ""); // ESSE NAO CONSEGUI FAZER FUNCIONAR
		
		// Passar o nome para maiúsculas
		//ret = endereco.toUpperCase();
		
		// Trocar os espaços duplicados, tabulações etc. por um espaço
		ret = ret.replaceAll("\\s+", " ");
		// Remover o espaço no início
		ret = ret.replaceAll("^\\s+", "");
		// Remover o espaço no fim
		ret = ret.replaceAll("\\s+$", "");

class RemoverAcentos {
    static String acentuado = "çÇáéíóúýÁÉÍÓÚÝàèìòùÀÈÌÒÙãõñäëïöüÿÄËÏÖÜÃÕÑâêîôûÂÊÎÔÛ";
    static String semAcento = "cCaeiouyAEIOUYaeiouAEIOUaonaeiouyAEIOUAONaeiouAEIOU";
    static char[] tabela;
    static {
        tabela = new char[256];
        for (int i = 0; i < tabela.length; ++i) {
	    tabela [i] = (char) i;
        }
        for (int i = 0; i < acentuado.length(); ++i) {
            tabela [acentuado.charAt(i)] = semAcento.charAt(i);
        }
    }
    public static String remover (final String s) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt (i);
            if (ch < 256) { 
                sb.append (tabela [ch]);
            } else {
                sb.append (ch);
            }
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        String s = "Gisele Bündchen da Conceição e Silva foi batizada assim em homenagem à sua conterrânea de Horizontina, RS.";
        s = RemoverAcentos.remover (s);
        System.out.println (s);
    }
}

/**
 * @author Fnascimento
 *
 * Classe de normalização de String.
 * Remove acentuação, caracteres especiais, 
 *  espaços duplicado, espaços do inicio e fim da string.
 *  
 */

public class NormalizaString {
	
	public String normalizar(String str) {
		
		/** Troca os caracteres acentuados por não acentuados **/
		String[][] caracteresAcento = {
				{"Á", "A"}, {"á", "a"},
				{"É", "E"}, {"é", "e"},
				{"Í", "I"}, {"í", "i"},
				{"Ó", "O"}, {"ó", "o"},
				{"Ú", "U"}, {"ú", "u"},
				{"À", "A"}, {"à", "a"},
				{"È", "E"}, {"è", "e"},
				{"Ì", "I"}, {"ì", "i"},
				{"Ò", "O"}, {"ò", "o"},
				{"Ù", "U"}, {"ù", "u"},
				{"Â", "A"}, {"â", "a"},
				{"Ê", "E"}, {"ê", "e"},
				{"Î", "I"}, {"î", "i"},
				{"Ô", "O"}, {"ô", "o"},
				{"Û", "U"}, {"û", "u"},
				{"Ä", "A"}, {"ä", "a"},
				{"Ë", "E"}, {"ë", "e"},
				{"Ï", "I"}, {"ï", "i"},
				{"Ö", "O"}, {"ö", "o"},
				{"Ü", "U"}, {"ü", "u"},
				{"Ã", "A"}, {"ã", "a"}, 
				{"Õ", "O"}, {"õ", "o"},
				{"Ç", "C"}, {"ç", "c"},
		};
		
		for (int i = 0; i < caracteresAcento.length; i++) {
			str = str.replaceAll(caracteresAcento[i][0], caracteresAcento[i][1]);
        }
		
		/** Troca os caracteres especiais da string por "" **/
		String[] caracteresEspeciais = {"\\.", ",", "-", ":", "\\(", "\\)", "ª", "\\|", "\\\\", "°"};
		
		for (int i = 0; i < caracteresEspeciais.length; i++) {
			str = str.replaceAll(caracteresEspeciais[i], "");
        }

		/** Troca os espaços no início por "" **/
		str = str.replaceAll("^\\s+", "");
		/** Troca os espaços no início por "" **/
		str = str.replaceAll("\\s+$", "");
	    /** Troca os espaços duplicados, tabulações e etc por  " " **/
		str = str.replaceAll("\\s+", " ");
	    
		return str;
	}
}

public String removerAcentos(String acentuada) {
        CharSequence cs = new StringBuilder(acentuada);
        return Normalizer.normalize(cs, Normalizer.Form.NFKD).replaceAll("\\p{InCombiningDiacriticalMarks}+", "");
    }