常见排序算法

from random import randint
import time

辅助函数：生成测试数据

def generate_data(max_num):
    return [randint(-max_num, max_num) for x in range(max_num)]

arr = generate_data(10000)

辅助函数：测试排序是否正确

def check_sorted(arr):
    return all(arr[i] <= arr[i+1] for i in range(len(arr)-1))

辅助函数：测试用时

def time_it(function, arr):
    start = time.clock()
    function(arr)
    end = time.clock()
    if not check_sorted(arr):
        print('sort result is not correct! ')
    print('time span = %f' % (end - start))

选择排序

从左往右，固定当前未排序部分的第一个元素，在余下部分寻找最小元素，与当前未排序部分的第一个元素交换。

def selection_sort(arr):
    for i in range(0, len(arr)):
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

arr1 = arr[:]
time_it(selection_sort, arr1)

time span = 3.742788

选择排序是不稳定的，例如 5 3 5 2 9，第一次会将5和2交换位置，则两个5的前后位置就改变了。

插入排序

左边是已排序的列表，右边读到的新元素，依次与它左边的元素逐个比较，如果左边元素较大，则将左边元素往后挪一格，直到左边元素较小，或者到达列表最左端，就是找到合适的插入位置，将新元素放在此处。例如

8| 5, 9, 3
5, 8| 9, 3
5, 8, 9| 3
5, 8, ?, 9
5, ?, 8, 9
?, 5, 8, 9
3, 5, 8, 9|

插入排序是稳定的。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        position = i
        current = arr[i]
        while (arr[position-1] > current) and (position > 0):
            arr[position] = arr[position-1]
            position -= 1
        arr[position] = current
    return arr 

arr2 = arr[:]
time_it(insertion_sort, arr2)

time span = 4.236959

冒泡排序

从右往左冒泡，如果两个元素前大后小，则把他俩交换过来，经过第一趟冒泡之后，最左边的就是最小的元素了；然后再第二次冒泡，直到右端只剩一个元素。

也可以从左往右沉底，如果两个元素前大后小，则交换，最右边的就是最小的元素了。

带短路的冒泡排序：标记一下，如果一趟中未发生任何交换，则已经排序完成，终止后面的冒泡

冒泡排序是稳定的。

def bubble_sort(arr):
    exchange = False
    for i in range(0, len(arr)-1):
        for j in range(len(arr)-1, i, -1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
                exchange = True
        if not exchange:
            break
    return arr

arr3 = arr[:]
time_it(bubble_sort, arr3)

time span = 8.539343

希尔排序

将数据划分组，每一组内采用直接插入排序；组数越来越少，直到最后划分成一个组，完成排序。优点是开始时划分较多的组，每一组内排序之后，下一次划分较少的组时，有不少数据已经是有序的了，可以减少一些挪动次数吧。

def shell_sort(arr):
    gap = len(arr) // 2
    while gap > 0:
        for start_pos in range(0, gap):
            gapInsertionSort(arr, start_pos, gap)
        gap = gap // 2
    return arr

def gapInsertionSort(arr, start_pos, gap):
    #希尔排序的辅助函数
    for i in range(start_pos + gap, len(arr), gap):
        position = i
        current = arr[i]
        while position >= gap and arr[position-gap] > current:
            arr[position] = arr[position-gap]
            position -= gap
        arr[position] = current 
    return arr

arr4 = arr[:]
time_it(shell_sort, arr4)

time span = 0.059824