八大经典排序算法基本思想及代码实现(插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，基数排序)

一.插入排序——简单插入排序

基本思想：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

def insertSort(arr):
    if len(arr) <= 1:
        return arr
    for i in range(1, len(arr)):
        tmp = arr[i]
        j = i
        while j > 0 and tmp < arr[j-1]:
            arr[j] = arr[j-1]
            j -= 1
        a[j] = tmp

二.插入排序——希尔排序

基本思想：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

def shellSort(arr):
    if len(arr) <= 1:
        return arr
    Increment = len(arr) / 2
    while Increment > 0:
        for i in range(Increment, len(arr)):
            tmp = arr[i]
            j = i
            while j > 0 and tmp < arr[j-Increment]:
                arr[j] = arr[j-Increment]
                j -= Increment
            arr[j] = tmp
        Increment /= 2

三. 选择排序——简单选择排序

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

过程：
第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推…..
第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，
直到整个序列按关键码有序。

def selectSort(arr):
    if len(arr) <= 1:
        return arr
    for i in range(len(arr)-1):
        min = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min]:
                min = j
        arr[i], arr[min] = arr[min], arr[i]

四.选择排序——堆排序

基本思想：堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置.
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来不动最后一个数据再次重建堆，交换数据，依次下去，就可以排序所有的数据。

def heapSort(arr):
    def precDown(a, i, N):
        child = 2 * i + 1
        tmp = a[i]
        while child < N:
            if child < N-1 and a[child] < a[child+1]:
                child += 1
            if tmp < a[child]:
                a[i] = a[child]
                i = child
            else:
                break
            child = child * 2 + 1
        a[i] = tmp

    if len(arr) <= 1:
        return arr
    N = len(arr)
    for i in range((N-2)//2, -1, -1):
        precDown(arr,i,N)
    for i in range(N-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        precDown(arr,0,i)

五.交换排序——冒泡排序

基本思想：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

def bubbleSort(arr):
    length = len(arr)
    if length <= 1:
        return arr
    while length > 1:
        for i in range(length-1):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
        length -= 1

六.交换排序——快速排序

基本思想：使用一个枢纽元，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比枢纽元小，另外一部分的所有数据都比枢纽元大，然后再按此方法对这两部分数据分别进行快速排序。

def quickSort(arr):
    def Qsort(a, left, right):
        i = left
        j = right
        if i >= j:
            return
        key = Median(a, left, right)
        while i < j:
            while i < j and a[j] >= key:
                j -= 1
            a[i] = a[j]
            while i < j and a[i] <= key:
                i += 1
            a[j] = a[i]
        a[i] = key
        Qsort(a, left, i-1)
        Qsort(a, i+1, right)

    def Median(a, left, right):
        center = (left + right) / 2
        if a[left] > a[center]:
            a[left], a[center] = a[center], a[left]
        if a[center] > a[right]:
            a[center], a[right] = a[right], a[center]
        if a[left] > a[right]:
            a[left], a[right] = a[right], a[left]
        a[center], a[left] = a[left], a[center]
        return a[left]

    if len(arr) <= 1:
        return arr
    Qsort(arr, 0, len(arr)-1)

七.归并排序

基本思想：将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

def mergeSort(arr):
    def Merge(left, right):
        i, j = 0, 0
        result = []
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result += left[i:]
        result += right[j:]
        return result

    if len(arr) <= 1:
        return arr
    center = len(arr) / 2
    left = mergeSort(arr[:center])
    right = mergeSort(arr[center:])
    return Merge(left, right)

八.基数排序

基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

def bucketSort(arr, radix=10):
    if len(arr) <= 1:
        return arr
    K = int(math.ceil(math.log(max(arr), radix)))
    bucket = [[] for i in range(radix)]
    for i in range(1, K+1):
        for element in arr:
            bucket[element%(radix**i)/(radix**(i-1))].append(element)
        del(arr[:])
        for each in bucket:
            arr.extend(each)
        bucket = [[] for i in range(radix)]