Como posso ordenar um dicionário por chave?

Os dicionários Python padrão são desordenados. Mesmo se você classificasse os pares (chave, valor), você não seria capaz de armazená-los em um "dicionário" de uma forma que preservaria a ordenação.

A maneira mais fácil é utilizar OrderedDict, que se lembra da ordem em que os elementos foram inseridos:

In [1]: import collections

In [2]: d = {2:3, 1:89, 4:5, 3:0}

In [3]: od = collections.OrderedDict(sorted(d.items()))

In [4]: od
Out[4]: OrderedDict([(1, 89), (2, 3), (3, 0), (4, 5)])

Não importa a forma como o od é impresso; vai funcionar como esperado:

In [11]: od[1]
Out[11]: 89

In [12]: od[3]
Out[12]: 0

In [13]: for k, v in od.iteritems(): print k, v
   ....: 
1 89
2 3
3 0
4 5

Python 3

Para usuários do Python 3, é necessário utilizar o .items() em vez de .iteritems():

In [13]: for k, v in od.items(): print(k, v)
   ....: 
1 89
2 3
3 0
4 5

Os próprios dicionários não têm itens encomendados como tal, se você quiser imprimi-los etc para alguma encomenda, aqui estão alguns exemplos:

Em Python 2.4 e superior:

mydict = {'carl':40,
          'alan':2,
          'bob':1,
          'danny':3}

for key in sorted(mydict):
    print "%s: %s" % (key, mydict[key])

dá:

alan: 2
bob: 1
carl: 40
danny: 3

(Python abaixo de 2.4:)

keylist = mydict.keys()
keylist.sort()
for key in keylist:
    print "%s: %s" % (key, mydict[key])

Fonte: http://www.saltycrane.com/blog/2007/09/how-to-sort-python-dictionary-by-keys/[2]

Como outros já mencionaram, os dicionários são intrinsecamente desordenados. Entretanto, se a questão for apenas **dicionários em exibição*** de forma ordenada, você pode substituir o método __str__ em uma subclasse de dicionário, e utilizar esta classe de dicionário em vez de construir o dicto'. Por exemplo, o métodostr'.

class SortedDisplayDict(dict):
   def __str__(self):
       return "{" + ", ".join("%r: %r" % (key, self[key]) for key in sorted(self)) + "}"

>>> d = SortedDisplayDict({2:3, 1:89, 4:5, 3:0})
>>> d
{1: 89, 2: 3, 3: 0, 4: 5}

Note que isto não muda nada sobre como as chaves são armazenadas, a ordem em que voltarão quando você iterar sobre elas etc, apenas como elas são exibidas com impressão ou no console python.