声明：此文参考自 https://facert.gitbooks.io/python-data-structure-cn；

一、冒泡排序

冒泡排序需要多次遍历列表。它比较相邻的项并交换那些无序的项。每次遍历列表将下一个最大的值放在其正确的位置。实质上，每个项“冒泡”到它所属的位置。

下图展示了冒泡排序的第一次遍历。阴影项正在比较它们是否乱序。如果在列表中有 n 个项目，则第一遍有 n-1 个项需要比较。重要的是要注意，一旦列表中的最大值是一个对的一部分，它将不断地被移动，直到遍历完成。

def bubble_sort(arr):
    count = len(arr)
    for i in range(count):
        for j in range(count - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
    print arr
    return arr

二、选择排序

选择排序改进了冒泡排序，每次遍历列表只做一次交换。为了做到这一点，一个选择排序在他遍历时寻找最大的值，并在完成遍历后，将其放置在正确的位置。与冒泡排序一样，在第一次遍历后，最大的项在正确的地方。 第二遍后，下一个最大的就位。遍历 n-1 次排序 n 个项，因为最终项必须在第（n-1）次遍历之后。

def selection_sort(arr):
    count = len(arr)
    # max_position = 0
    for i in range(count):
        max_position = 0
        for location in range(count - i - 1, 0, -1):
            if arr[location] > arr[max_position]:
                max_position = location
        tmp = arr[count - i - 1]
        arr[count - i - 1] = arr[max_position]
        arr[max_position] = tmp
    return arr

三、插入排序

插入排序，尽管仍然是 O(n^2 )，工作方式略有不同。它始终在列表的较低位置维护一个排序的子列表。然后将每个新项 “插入” 回先前的子列表，使得排序的子列表称为较大的一个项。Figure 4 展示了插入排序过程。 阴影项表示算法进行每次遍历时的有序子列表。

def insert_sort(arr):
    count = len(arr)
    for i in range(1, count):
        key = arr[i]
        # 就是从第一个元素作为初始列表，第二个元素与第一个元素比，形成一个2元素列表，之后第三个元素和2元素列表比，形成三元素列表。。。。
        # 把arr里的值往形成的短序列里插
        j = i - 1
        while j >= 0:
            if key < arr[j]:
                arr[j+1], arr[j] = arr[j], key
            j -= 1
    print arr
    return arr

希尔排序（有时称为“递减递增排序”）通过将原始列表分解为多个较小的子列表来改进插入排序，每个子列表使用插入排序进行排序。 选择这些子列表的方式是希尔排序的关键。不是将列表拆分为连续项的子列表，希尔排序使用增量i（有时称为 gap），通过选择 i 个项的所有项来创建子列表。

这可以在下图中看到。该列表有九个项。如果我们使用三的增量，有三个子列表，每个子列表可以通过插入排序进行排序。完成这些排序后，我们得到如下图所示的列表。虽然这个列表没有完全排序，但发生了很有趣的事情。 通过排序子列表，我们已将项目移动到更接近他们实际所属的位置。

def shell_sort(arr):
    sub_arr_count = len(arr)//2
    while sub_arr_count > 0:
        for start_position in range(sub_arr_count):
            gap_insert_sort(arr, start_position, sub_arr_count)
        sub_arr_count = sub_arr_count//2
    return arr


def gap_insert_sort(arr, start, gap):
    for i in range(start+gap, len(arr), gap):
        current_value = arr[i]
        position = i
        while position >= gap and arr[position-gap] > current_value:
            arr[position] = arr[position-gap]
            position = position - gap
        arr[position] = current_value

五、归并排序

我们现在将注意力转向使用分而治之策略作为提高排序算法性能的一种方法。 我们将研究的第一个算法是归并排序。归并排序是一种递归算法，不断将列表拆分为一半。 如果列表为空或有一个项，则按定义（基本情况）进行排序。如果列表有多个项，我们分割列表，并递归调用两个半部分的合并排序。 一旦对这两半排序完成，就执行称为合并的基本操作。合并是获取两个较小的排序列表并将它们组合成单个排序的新列表的过程。

我们现在将注意力转向使用分而治之策略作为提高排序算法性能的一种方法。 我们将研究的第一个算法是归并排序。归并排序是一种递归算法，不断将列表拆分为一半。 如果列表为空或有一个项，则按定义（基本情况）进行排序。如果列表有多个项，我们分割列表，并递归调用两个半部分的合并排序。 一旦对这两半排序完成，就执行称为合并的基本操作。合并是获取两个较小的排序列表并将它们组合成单个排序的新列表的过程。

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_arr = arr[:mid]
        right_arr = arr[mid:]
        merge_sort(left_arr)
        merge_sort(right_arr)
        i = 0
        j = 0
        k = 0
        while i < len(left_arr) and j < len(right_arr):
            if left_arr[i] < right_arr[j]:
                arr[k] = left_arr[i]
                i += 1
            else:
                arr[k] = right_arr[j]
                j += 1
            k += 1
        while i < len(left_arr):
            arr[k] = left_arr[i]
            i += 1
            k += 1
        while j < len(right_arr):
            arr[k] = right_arr[j]
            j += 1
            k += 1
    return arr

六、快排

快速排序使用分而治之来获得与归并排序相同的优点，而不使用额外的存储。然而，作为权衡，有可能列表不能被分成两半。当这种情况发生时，我们将看到性能降低。

快速排序首先选择一个值，该值称为 枢轴值。虽然有很多不同的方法来选择枢轴值，我们将使用列表中的第一项。枢轴值的作用是帮助拆分列表。枢轴值属于最终排序列表（通常称为拆分点）的实际位置，将用于将列表划分为快速排序的后续调用。

下图展示 54 将作为我们的第一个枢纽值。由于我们已经看过这个例子几次，我们知道 54 最终将会在当前持有 31 的位置。接下来将发生分区过程。它将找到拆分点，同时将其他项移动到列表的适当侧，小于或大于枢轴值。

分区从通过在列表中剩余项目的开始和结束处定位两个位置标记（我们称为左标记和右标记）开始（下图中的位置 1 和 8 ）。分区的目标是移动相对于枢轴值位于错误侧的项，同时也收敛于分裂点。 下图展示了我们定位54的位置的过程。

我们首先增加左标记，直到我们找到一个大于枢轴值的值。 然后我们递减右标，直到我们找到小于枢轴值的值。我们发现了两个相对于最终分裂点位置不适当的项。 对于我们的例子，这发生在 93 和 20。现在我们可以交换这两个项目，然后重复该过程。

在右标变得小于左标记的点，我们停止。右标记的位置现在是分割点。枢轴值可以与拆分点的内容交换，枢轴值现在就位（下图）。 此外，分割点左侧的所有项都小于枢轴值，分割点右侧的所有项都大于枢轴值。现在可以在分割点处划分列表，并且可以在两半上递归调用快速排序。

def quick_sort(arr):
    """
    需要选择一个比较值key，此方法不算是严格的快排，需要较多的额外空间
    """
    count = len(arr)
    if count <= 1:
        return arr
    key = arr[count // 2]
    left = [x for x in arr if x < key]
    mid = [x for x in arr if x == key]
    right = [x for x in arr if x > key]
    return quick_sort(left) + mid + quick_sort(right)

def quickly_sort(arr, left, right):
    if len(arr) <= 1:
        return arr
    key = arr[left]
    low = left
    high = right
    while left < right:
        while arr[right] <= key:
            right -= 1
        arr[left] = arr[right]
        while arr[right] >= key:
            left += 1
        arr[right] = arr[left]
    arr[left] = key
    quickly_sort(arr, low, left-1)
    quickly_sort(arr, left+1, high)
    return arr