面试题之中的一个。

s=[

{"name":"Axx","score":"90"},

{"name":"Bxx","score":"91"},

{"name":"Cxx","score":"20"},

]

请用一行代码对上述list，依照score排序。

s=[

{"name":"Axx","score":"90"},

{"name":"Bxx","score":"91"},

{"name":"Cxx","score":"20"},

]

print "original s: ",s

new_s = sorted(s,key = lambda e:e.__getitem__('score'))

print "new s: ",new_s

结果：

original s:  [{'score': '90', 'name': 'Axx'}, {'score': '91', 'name': 'Bxx'}, {'score': '20', 'name': 'Cxx'}]

new s:  [{'score': '20', 'name': 'Cxx'}, {'score': '90', 'name': 'Axx'}, {'score': '91', 'name': 'Bxx'}]

吐槽：print字典的排序和我s的定义顺序貌似不一样，我定义是name,score，print出来是score再name。貌似也无关紧要，dic本来就无序。

假设我想多级排序呢，先用score排序。再用name排序：

s=[

{"name":"Exx","score":"90"},

{"name":"Axx","score":"90"},

{"name":"Bxx","score":"91"},

{"name":"Cxx","score":"20"},

{"name":"Dxx","score":"90"},

]

print "original s: ",s

new_s = sorted(s,key = lambda e:e.__getitem__('score'))

print "new s: ",new_s

new_s_2 = sorted(new_s,key = lambda e:(e.__getitem__('score'),e.__getitem__('name')))

print "new_s_2: ",new_s_2

结果：

original s:  [{'score': '90', 'name': 'Exx'}, {'score': '90', 'name': 'Axx'}, {'score': '91', 'name': 'Bxx'}, {'score': '20', 'name': 'Cxx'}, {'score': '90', 'name': 'Dxx'}]

new s:  [{'score': '20', 'name': 'Cxx'}, {'score': '90', 'name': 'Exx'}, {'score': '90', 'name': 'Axx'}, {'score': '90', 'name': 'Dxx'}, {'score': '91', 'name': 'Bxx'}]

new_s_2:  [{'score': '20', 'name': 'Cxx'}, {'score': '90', 'name': 'Axx'}, {'score': '90', 'name': 'Dxx'}, {'score': '90', 'name': 'Exx'}, {'score': '91', 'name': 'Bxx'}]

这里key = lambda e:(e.__getitem__('score'),e.__getitem__('name'))。lambda函数返回值就是个元组，元组的比較都是先比較第一个，第一个同样再比較第二个，以此类推。

元组的比較，有代码为证：

>>> aa = (1,3)

>>> bb = (1,2)

>>> cc = (2,3)

>>> aa > bb

True

>>> aa > cc

False

>>> bb < cc

True

>>>

面试题目消化完了，是时候表演下真正的技术了，额，不正确，是时候看下python sorted这个函数了。

sorted(iterable,cmp=None,key=None,reverse=False)

第一个參数那里放一个iterable对象。比方list。

第三个參数那里放一个keyword函数，让sorted()知道我们要比較元素的什么。

额，就仅仅用到这两个就够了。

尝试去读sorted源码。在C:\Python-2.7.2\Python\bltinmodule.c中：

static PyObject *

builtin_sorted(PyObject *self, PyObject *args, PyObject *kwds)

{

    PyObject *newlist, *v, *seq, *compare=NULL, *keyfunc=NULL, *newargs;

    PyObject *callable;

    static char *kwlist[] = {"iterable", "cmp", "key", "reverse", 0};

    int reverse;

    /* args 1-4 should match listsort in Objects/listobject.c */

    if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|OOi:sorted",

        kwlist, &seq, &compare, &keyfunc, &reverse))

        return NULL;

    newlist = PySequence_List(seq);

    if (newlist == NULL)

        return NULL;

    callable = PyObject_GetAttrString(newlist, "sort");//居然是用list.sort()

    if (callable == NULL) {

        Py_DECREF(newlist);

        return NULL;

    }

    newargs = PyTuple_GetSlice(args, 1, 4);

    if (newargs == NULL) {

        Py_DECREF(newlist);

        Py_DECREF(callable);

        return NULL;

    }

    v = PyObject_Call(callable, newargs, kwds);

    Py_DECREF(newargs);

    Py_DECREF(callable);

    if (v == NULL) {

        Py_DECREF(newlist);

        return NULL;

    }

    Py_DECREF(v);

    return newlist;

}

不看了，那个sorted()代码事实上新建一个list，然后用list.sort()。所以我们看list.sort()就好了。

转战C:\Python-2.7.2\Objects\listobject.c中的list.sort()，受到一万点伤害，不看了。去死吧。手贱看什么源代码，直接会用即可了。

static PyObject *

listsort(PyListObject *self, PyObject *args, PyObject *kwds)

{

    MergeState ms;

    PyObject **lo, **hi;

    Py_ssize_t nremaining;

    Py_ssize_t minrun;

    Py_ssize_t saved_ob_size, saved_allocated;

    PyObject **saved_ob_item;

    PyObject **final_ob_item;

    PyObject *compare = NULL;

    PyObject *result = NULL;            /* guilty until proved innocent */

    int reverse = 0;

    PyObject *keyfunc = NULL;

    Py_ssize_t i;

    PyObject *key, *value, *kvpair;

    static char *kwlist[] = {"cmp", "key", "reverse", 0};

    assert(self != NULL);

    assert (PyList_Check(self));

    if (args != NULL) {

        if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OOi:sort",

            kwlist, &compare, &keyfunc, &reverse))

            return NULL;

    }

    if (compare == Py_None)

        compare = NULL;

    if (compare != NULL &&

        PyErr_WarnPy3k("the cmp argument is not supported in 3.x", 1) < 0)

        return NULL;

    if (keyfunc == Py_None)

        keyfunc = NULL;

    if (compare != NULL && keyfunc != NULL) {

        compare = build_cmpwrapper(compare);

        if (compare == NULL)

            return NULL;

    } else

        Py_XINCREF(compare);

    /* The list is temporarily made empty, so that mutations performed

     * by comparison functions can't affect the slice of memory we're

     * sorting (allowing mutations during sorting is a core-dump

     * factory, since ob_item may change).

     */

    saved_ob_size = Py_SIZE(self);

    saved_ob_item = self->ob_item;

    saved_allocated = self->allocated;

    Py_SIZE(self) = 0;

    self->ob_item = NULL;

    self->allocated = -1; /* any operation will reset it to >= 0 */

    if (keyfunc != NULL) {

        for (i=0 ; i < saved_ob_size ; i++) {

            value = saved_ob_item[i];

            key = PyObject_CallFunctionObjArgs(keyfunc, value,

                                               NULL);

            if (key == NULL) {

                for (i=i-1 ; i>=0 ; i--) {

                    kvpair = saved_ob_item[i];

                    value = sortwrapper_getvalue(kvpair);

                    saved_ob_item[i] = value;

                    Py_DECREF(kvpair);

                }

                goto dsu_fail;

            }

            kvpair = build_sortwrapper(key, value);

            if (kvpair == NULL)

                goto dsu_fail;

            saved_ob_item[i] = kvpair;

        }

    }

    /* Reverse sort stability achieved by initially reversing the list,

    applying a stable forward sort, then reversing the final result. */

    if (reverse && saved_ob_size > 1)

        reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);

    merge_init(&ms, compare);

    nremaining = saved_ob_size;

    if (nremaining < 2)

        goto succeed;

    /* March over the array once, left to right, finding natural runs,

     * and extending short natural runs to minrun elements.

     */

    lo = saved_ob_item;

    hi = lo + nremaining;

    minrun = merge_compute_minrun(nremaining);

    do {

        int descending;

        Py_ssize_t n;

        /* Identify next run. */

        n = count_run(lo, hi, compare, &descending);

        if (n < 0)

            goto fail;

        if (descending)

            reverse_slice(lo, lo + n);

        /* If short, extend to min(minrun, nremaining). */

        if (n < minrun) {

            const Py_ssize_t force = nremaining <= minrun ?

                              nremaining : minrun;

            if (binarysort(lo, lo + force, lo + n, compare) < 0)

                goto fail;

            n = force;

        }

        /* Push run onto pending-runs stack, and maybe merge. */

        assert(ms.n < MAX_MERGE_PENDING);

        ms.pending[ms.n].base = lo;

        ms.pending[ms.n].len = n;

        ++ms.n;

        if (merge_collapse(&ms) < 0)

            goto fail;

        /* Advance to find next run. */

        lo += n;

        nremaining -= n;

    } while (nremaining);

    assert(lo == hi);

    if (merge_force_collapse(&ms) < 0)

        goto fail;

    assert(ms.n == 1);

    assert(ms.pending[0].base == saved_ob_item);

    assert(ms.pending[0].len == saved_ob_size);

succeed:

    result = Py_None;

fail:

    if (keyfunc != NULL) {

        for (i=0 ; i < saved_ob_size ; i++) {

            kvpair = saved_ob_item[i];

            value = sortwrapper_getvalue(kvpair);

            saved_ob_item[i] = value;

            Py_DECREF(kvpair);

        }

    }

    if (self->allocated != -1 && result != NULL) {

        /* The user mucked with the list during the sort,

         * and we don't already have another error to report.

         */

        PyErr_SetString(PyExc_ValueError, "list modified during sort");

        result = NULL;

    }

    if (reverse && saved_ob_size > 1)

        reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);

    merge_freemem(&ms);

dsu_fail:

    final_ob_item = self->ob_item;

    i = Py_SIZE(self);

    Py_SIZE(self) = saved_ob_size;

    self->ob_item = saved_ob_item;

    self->allocated = saved_allocated;

    if (final_ob_item != NULL) {

        /* we cannot use list_clear() for this because it does not

           guarantee that the list is really empty when it returns */

        while (--i >= 0) {

            Py_XDECREF(final_ob_item[i]);

        }

        PyMem_FREE(final_ob_item);

    }

    Py_XDECREF(compare);

    Py_XINCREF(result);

    return result;

}