这里记录一些各种排序算法。

选择排序

首先，找到数组中最小元素， 其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。 再次，在剩下的元素中找到最小元素，将它和数组中的第二个元素交换位置。 如此往复，直到将整个数组排序。 这种排序方法叫选择排序（select sort）。

选择排序的数据移动是最少的， 平均时间复杂度均为 O(n^2)。

def select(xs):
    for i in range(len(xs)-1):
        min = i
        for j in range(i+1, len(xs)):
            if xs[min] > xs[j]:
                min = j
        if min != i:
            xs[i], xs[min] = xs[min], xs[i]

插入排序

通常人们整理扑克牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。 在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。 这种排序方法叫插入排序（inert sort）。

插入排序对于部分有序的数组十分高效，也很适合小规模数组。 平均时间复杂度均为 O(n^2)。

def insert(xs):
    for i in range(len(xs)-1):
        x = xs[i+1]
        j = i
        while j >= 0 and xs[j] > x:
            xs[j+1] = xs[j]
            j -= 1
        xs[j+1] = x

希尔排序

基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高， 即可以达到线性排序的效率；
• 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能， 这样可以让一个元素可以一次性地朝最终位置前进一大步。 然后算法再取越来越小的步长进行排序， 算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

def shell(xs):
    step = len(xs) // 2
    while step > 0:
        for i in range(step, len(xs), step):
            x = xs[i]
            j = i - step
            while j >= 0 and xs[j] > x:
                xs[j+step] = xs[j]
                j -= step
            xs[j+step] = x
        step //= 2

冒泡排序

重复走访要排序的数列， 每一次走访中，要求最大的数跑到数列的末尾， 走访中，一次比较两个元素，如果他们的顺序错误就把他们交换过来，就像冒泡一样， 这种方法就叫冒泡排序（bubble sort）。 平均时间复杂度均为 O(n^2)。

def bubble(xs):
    for i in range(len(xs)):
        for j in range(len(xs)-1-i):
            if xs[j] > xs[j+1]:
                xs[j], xs[j+1] = xs[j+1], xs[j]

快速排序

在未排序序列中随便选一个中间值，然后把数组分成三块， 一块是比这个中间值小的序列， 一块是这个中间值， 一块是比这个中间值大的序列， 然后把其中长度大于 2 的序列再重复以上操作直到排序完毕。 平均时间复杂度在最差情况下的代价是 n^2，平均情况下是 nlogn。

def quick(xs):
    def _partition(low, high):
        key = xs[low]
        while low < high:
            while low < high and key <= xs[high]:
                high -= 1
            if low < high:
                xs[low] = xs[high]
            while low < high and key > xs[low]:
                low += 1
            if low < high:
                xs[high] = xs[low]
        xs[low] = key
        return low
    def _sort(low,high):
        if low < high:
            pos = _partition(low,high)
            _sort(low,pos)
            _sort(pos+1, high)
    _sort(0, len(xs)-1)

归并排序

把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。 时间复杂度为 O(n*logn)。

def merge(xs):
    def _merge(ys, left, right, middle):
        tmp = []
        i = left
        j = middle + 1
        while i <= middle and j <= right:
            if ys[i] < ys[j]:
                tmp.append(ys[i])
                i = i + 1
            else:
                tmp.append(ys[j])
                j = j + 1
        while i <= middle:
            tmp.append(ys[i])
            i = i + 1
        while j <= right:
            tmp.append(ys[j])
            j = j + 1
        ys[left:right+1] = tmp[:]
    def _sort(zs, left, right):
        if left < right:
            middle = (left + right) // 2
            _sort(zs, left, middle)
            _sort(zs, middle + 1, right)
            _merge(zs, left, right, middle)
    _sort(xs, 0, len(xs)-1)

堆排序

用一个数组来表示堆， 对于处在 i 位置的元素，2*i+1 位置上的是其左孩子，2*i+2 是其右孩子。

1. 通过调整数组建立最大堆；
2. 第一个元素为最大值，将第一个元素与最大堆对应数组的最后一个元素交换；
3. 最大堆长度减一，再重复以上步骤直至最大堆长度为 1。

平均时间复杂度为O(n*logn)。

def heap(xs):
    def _max_heapify(xs, i, size):
        left = 2*i+1
        right = 2*i+2
        if left < size and xs[left] > xs[i]:
            largest = left
        else:
            largest = i
        if right < size and xs[right] > xs[largest]:
            largest = right
        if largest != i:
            xs[i], xs[largest] = xs[largest], xs[i]
            _max_heapify(xs, largest, size)
    def _build_max_heap(xs, size):
        for i in range((size-2)//2, -1, -1):
            _max_heapify(xs, i, size)
    def _sort(xs, size):
        _build_max_heap(xs, size)
        for i in range(size-1, -1, -1):
            xs[0], xs[i] = xs[i], xs[0]
            _max_heapify(xs, 0, i)
    _sort(xs, len(xs))