As you probably saw on the dialog, deleting contacts is not reversible.  The only way to recover them is if you previously did an Export to save a copy to your computer.  You could then Import to restore.  Otherwise you'll have to recreate them manually.