原理

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
希尔排序是把数据按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

时间复杂度

希尔排序是一种不稳定的排序方法，时间复杂度为：O(n^（1.3—2）)。

Python实现

# -*- coding:utf-8 -*-
# 希尔排序

def shell_sort(list):
    n = len(list)
    step = n // 2
    while step > 0: # 最后的步长为1，此时就是一个标准的插入排序
        for cur in range(step, n):
            i = cur
            while i >= step and list[i-step] > list[i]:
                list[i - step], list[i] = list[i], list[i-step]
                i -= step
        step = step // 2
    return list


list = [54, 26, 93, 17, 77, 3, 31, 44, 55, 20]
print(shell_sort(list))

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

原理

比较相邻的元素，如果第一个比第二个大，就交换。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

时间复杂度

冒泡算法每次都需要对元素进行比较，是一种稳定的排序算法，时间复杂度为：O（n²）

Python实现

# -*- coding:utf-8 -*-
# 冒泡排序

'''
重点：每一轮比较都把最大的数放到最后，第二层循环的循环次数是递减的，
所以j终止的条件是 j = end - i - 1
'''

# while 写法
def bubble_sort(list):
    # if len(list) < 1:
    #     return list

    i = 0
    end = len(list) - 1
    while i < end:
        j = 0
        while j < end - i:
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]
            j = j + 1

        i = i + 1

    return list

# for 写法
def bubble_sort_for(list):
    # if len(list) < 1:
    #     return list

    end = len(list)

    # 外循环次数等于需排序个数减 1，比如3个数字，只需要循环两轮，i初始为0
    for i in range(end - 1):
        for j in range(end - i - 1): # 单趟排序比较的次数要减去已排序好的个数（即 i）
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]
    return list

原理

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
这是一种递归算法，每次将一个列表一分为二，如果列表为空或只有一个元素，那么从定义上来说它就是有序的。如果列表不止一个元素，就将列表一分为二，并对两部分都递归调用归并排序。
该算法1945年由约翰·冯·诺伊曼首次提出。

时间复杂度

归并排序是一种稳定的排序算法，时间复杂度为：O(nlogn)

# -*- coding:utf-8 -*-
# 归并排序

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2 # 向下取整
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        lefthalf = mergeSort(lefthalf)
        righthalf = mergeSort(righthalf)

        i = 0
        j = 0
        k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i = i + 1
            else:
                alist[k] = righthalf[j]
                j = j + 1
            k = k + 1

        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i = i + 1
            k = k + 1

        while j < len(righthalf):
            alist[k] = righthalf[j]
            j = j + 1
            k = k + 1
    return alist

b = [54, 26, 93, 17, 77, 31, 44, 55, 20]
mergeSort(b)

原理

在列表较低的一端维护一个有序的子列表，并逐个将后面每个新元素“插入”这个子列表。

1. 将待排序列表的第一个元素当做已排序序列，第二个元素到最后一个元素当成未排序序列。
2. 取未排序序列中的第一个数据，插入到已排序序列中顺序正确的位置。将未排序的第一个数据与相邻的前一个数据(已排序序列的最后一个数)据进行比较，如果顺序错误则交换位置，交换位置后继续与相邻的前一个数据进行比较，直到不需要交换则插入完成。每次插入数据后，已排序序列都是排好序的。
3. 重复上一步，继续插入下一个数据。每进行一次插入，已排序序列的长度加1，未排序序列的长度减1，直到列表中的所有数据都插入到已排序序列了，则列表排序完成。

时间复杂度

插入排序的时间复杂度也是O(n²)。

Python 实现

# -*- coding: UTF-8 -*-
# 插入排序

def insertionSort(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index

        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position-1]
            position = position-1

        alist[position] = currentvalue
    return alist

基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
下面这个图可以描述算法的实现过程：

时间复杂度

快速排序是一种不稳定的排序方法，平均时间复杂度为O (nlogn)，最坏情况和冒泡排序差不多，为O（n²）。

Python实现

# 简洁的实现方法
def quicksort(array):
  if len(array) < 2:
    return array
  else:
    pivot = array[0]
    less = [i for i in array[1:] if i <= pivot]
    greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3]) # 结果：[2, 3, 5, 10]

# 比较容易理解的实现方法
def quick(list):
    if len(list) < 2:
        return list
    else:
        left = i = 0
        j = len(list) - 1
        
        while i != j:
            while list[j] >= list[left] and i < j:
                j -= 1

            while list[i] <= list[left] and i < j:
                i += 1
            
            if i < j:
                list[i], list[j] = list[j], list[i]
        list[i], list[left] = list[left],  list[i]
        return quick(list[left:i]) + [list[i]] + quick(list[i+1:])

注意理解：上面的第二种方法，挑选了左侧第一个数作为参考，内部循环则从对面，即列表末尾开始查找，因为如果从左侧开始查找，当满足条件i=j退出循环时，list[i]会比list[left]大，交换之后违反了左边小右边大的原则。

该实例中涉及Python的一个称作列表推导表达式的语法糖用法，即在for循环中嵌套使用if和else语句。例如：

oldList = [12, 3, 4, 6, 7, 13, 21]
newList = [x for x in oldList if x%2 == 0]
print newList # 结果：[12, 4, 6]

想了解更多Python语法糖知识，请参考：Python语法糖系列