los contactos se guardan online, no importa cuantas veces formatees el teléfono, siempre volverás a tener los contactos.
si quieres cambiarlos, la manera más sencilla en mi opinión es que entres en
www.gmail.com, arriba a la izquierda pulsas en contactos, y allí los gestionas a tu gusto.