基本排序算法

根据搜索算法的内容，我们在列表中查找一个目标项的时候，如果是在一个排序好的列表中查找，相对一个乱序的列表而言，有更高的效率。因此，如果需要在列表中查询目标项，我们首先考虑是否将列表进行排序操作，然后在进行查找目标项的操作。

比较数据项

在排序中，默认列表中的所有项目都是可比较的，在python中，意味着列表中的元素都是相同的类型，且都可以识别==、<和>操作符。对于这个要求，内建的数据类型都是支持的，如果需要对一个新对象的类使用以上运算符，那么需要在定义类的时候实现__eq__、__lt__和__gt__方法。

def __lt__(self, other):
    pass

如果self小于other，该方法返回True，否则返回False。比如说:

class Person:
    def __init__(self, name, age):
        self._name = name
        self._age = age

    def __lt__(self, other):
        return self._name < other._name

上述__lt__方法对两个Person对象的_name字段调用了<运算符,然后根据逻辑判断返回结果。

基本排序算法

选择排序(select sort)

最简单的排序逻辑就是，搜索整个列表，查找最小的项，如果该位置不是列表的第一个位置，则交换这两个项的位置。接着，从列表的第二个位置在再次进行同样的操作。这个算法就叫做选择排序(select sort)。具体实现代码如下：

def selectionSort(lyst):
    i = 0
    while i < len(lyst) - 1:
        minIndex = i
        j = i + 1
        while j < len(lyst):
            if lyst[j] < lyst[minIndex]:
                minIndex = j
            j += 1
        if minIndex != i:
            swap(lyst, minIndex, i)
        i += 1

对于代码中的swap函数，这篇笔记中都要使用到，具体实现如下：

def swap(lyst, i, j):
    temp = lyst[i]
    lyst[i] = lyst[i]
    lyst[j] = temp

# 可以直接写成lyst[i], lyst[j] = lyst[j], lyst[i]
# 但是为了方便理解，使用上述方式进行描述

对于selectionSort函数中的逻辑，在循环开始的时候，默认列表的第一项是最小项，然后循环进行比较，如果发现有更小的项，则交换位置，知道完成整个列表项的遍历。从上述代码可以看出，完成整个列表的排序，需要进行(n-1) + (n-2) + ... + 1 = n(n-1)/2次循环，对于较大的n，我们一般选择影响最大的项，则选择排序的算法复杂度为O(n^2^)。

冒泡排序(buddle sort)

冒泡排序的策略是从列表的开头处开始，比较一对数据项，直到移动到列表的结尾。当互相比较的一对数据项顺序不正确的时候，算法就交换其位置，列表中最大的项就移动到了列表的结尾处。然后在从头开始进行比较，移动到列表的倒数第二项，以此类推，直到完成列表的排序。代码如下：

def bubbleSort(lyst):
    n = len(lyst)
    while n > 1:
        i = 1
        while i < n:
            if lyst[i] < lyst[i - 1]:
                swap(lyst, i, i-1)
            i += 1
        n -= 1

代码中的逻辑很好理解，对于大小为n的列表，内部的循环执行了n(n - 1)/2次，所以可以得出的结论是，冒泡排序的时间复杂度也是O(n^2^)。

插入排序(insert sort)

插入排序的策略如下：

从第一个项开始，默认该项已经完成排序；
取下一个项，在已经排序好的序列中从后往前扫描；
如果已排序的项大于取到的新项，则将该项移动到下一个位置；
重复步骤3，直到找到已排序的项小于或者等于新项的位置；
将新项插入到这个位置；
重复步骤2~5直到完成排序。

代码实现如下：

def insertionSort(lyst):
    i = 1
    while i < len(lyst):
        itemToInsert = lyst[i]
        j = i - 1
        while j >= 0:
            if itemToInsert < lyst[j]:
                lyst[j+1] = lyst[j]
                j -= 1
            else:
                break
        lyst[j+1] = itemToInsert
        i += 1

在上述代码中，外层循环遍历从1到n-1的位置，对于这个循环中的每一个位置i,我们都保存并从位置i-1开始内部循环。在内部循环中，从i-1处开始循环，设置为j，对于每一个位置j，我们都将项移动到j+1的位置，直到找到了给保存的项(第i项)的插入位置。根据实现代码，可以看出，插入排序的平均复杂度仍然是O(n^2^)。