Long time I wanted to write about it. One of the hot topic on the Android mailing lists is JNI. JNI is the technology that allows to bind Java code with native code. In our case, this is going to be C/C++.
On Android, the Java VM (Dalvik) is not what you would call a performance monster. Even official presentations by Google agree with that. But what they also say, it's that you can use JNI if you want performances.
That is, write the hot parts in C or C++, and the rest in Java. And then interface both parts with JNI.