冒泡排序

从第一个数开始，相邻两个数比较，前一个大于后一个，则调换，重复这个过程。代码实现：
python:

def bubbling_sort(array):
    if not array or len(array) <= 1:
        return
    array_len = len(array)

    for i in range(0, array_len):
        swap_flag = True
        for j in range(0, array_len - i - 1):
            if array[j] > array[j+1]:
                temp = num[j]
                num[j] = num[j+1]
                num[j+1] = temp
                swap_flag = False
        if swap_flag:
            return

嵌套循环，时间复杂度为。

其次，介绍算法稳定性概念，比如一个数组，，使用排序算法后，如果二者位置没有交换，则算法稳定。

因此，冒泡算法稳定。

选择排序

从数组第一个开始，从下一个元素开始遍历找到最小元素，然后和第一个交换，以此类推，代码实现：
python:

def chose_sort(array):
    if not array or len(array) <= 1:
        return
    array_len = len(array)

    for i in range(0, array_len):
        min = array[i]
        temp_index = i
        for j in range(i+1, array_len):
            if array[j] < min:
                min = array[j]
                temp_index = j
        if i != temp_index:
            temp = array[i]
            array[i] = array[temp_index]
            array[temp_index] = temp

时间复杂度为，不过算法不稳定，比如，第一个2会和1交换。

插入排序

从数组第一个元素开始，如果第二个元素小于第一个元素，则放到第一个元素的位置，如果第三个元素小于第二个元素，则放到第二个元素的位置，其它元素的索引加1，依次类推。代码实现：
python:

def insert_sort(array):
    if not array or len(array) <= 1:
        return
    array_len = len(array)

    for i in range(1, array_len):
        for j in range(0, i + 1):
            if array[i] < array[j]:
                break
            if j <= i:
                temp_index = i
                current = array[i]
                while temp_index > j:
                    temp = array[temp_index]
                    array[temp_index] = array[temp_index - 1]
                    array[temp_index - 1] = current
                    temp_index -= 1
                array[j] = current

快速排序

将第一个元素作为基准参考，将其保存到临时变量中，然后start和end指定数组开头序号+1和数组末尾序号，从end开始和临时变量比较，如果array[end]>=临时变量，end向前移一位，然后继续比较，否则较其作为临时变量，然后从start那里开始比较，重复上面过程，直到start成为临时变量，然后换到end那里，直到start>=end结束，结果就是以当前临时变量为基准，小于或等于该值的都在左边，其它的在右边，然后对两边执行上述操作即可，代码实现：
python:

def quick_sort(array, start=0, end=0):
    if not array or len(array) <= 1 or start > end:
        return

    if start ==0 and end == 0:
        end = len(array) - 1

    start_temp = start
    end_temp = end
    temp = array[start_temp]
    while start_temp < end_temp:
        while start_temp < end_temp and array[end_temp] >= temp:
            end_temp -= 1
        if start_temp < end_temp:
            array[start_temp] = array[end_temp]
            start_temp += 1
        while start_temp < end_temp and array[start_temp] <= temp:
            start_temp += 1
        if start_temp < end_temp:
            array[end_temp] = array[start_temp]
            end_temp -= 1
    array[start_temp] = temp
    quick_sort(array, start, start_temp - 1)
    quick_sort(array, start_temp + 1, end);

算法时间复杂度为，不过这是平均复杂度，极端情况可能为，其次算法稳定性也很差。

归并排序

先递归分解数组，然后合并有序数组，代码实现：
python:

def merge_array(array, first, middle, last, array_temp):
    i = first
    j = middle + 1
    temp = 0
    while i <= middle and j <= last:
        if array[i] <= array[j]:
            array_temp[temp] = array[i]
            i += 1
        else:
            array_temp[temp] = array[j]
            j += 1
        temp += 1
    while i <= middle:
        array_temp[temp] = array[i]
        i += 1
        temp += 1
    while j <= last:
        array_temp[temp] = array[j]
        j += 1
        temp += 1
    for k in range(0, temp):
        array[first + k] = array_temp[k]

def rec_merge_sort(array, first, last, array_temp):
    if first < last:
        middle = (first + last) / 2
        rec_merge_sort(array, first, middle, array_temp)
        rec_merge_sort(array, middle + 1, last, array_temp)
        merge_array(array, first, middle, last, array_temp)

def merge_sort(array):
    if not array or len(array) <= 1:
        return
    array_len = len(array)
    array_temp = [0] * array_len
    rec_merge_sort(array, 0, array_len - 1, array_temp)

时间复杂度为，算法稳定。

堆排序

先将数组最大堆初始化，然后将最大堆的顶部数和最后面的待交换数交换，然后进行最大堆调整，调整后最大的数位于顶部，持续交换到根部位置。

最大堆的概念是节点要大于等于左右子节点的值。同时，堆中，如果父节点索引为，则左子节点为，右子节点为，若子节点为，则父节点为。调整最大堆就是从第一个非叶子节点开始，使用相关函数调整，一直调整到根节点。

调整最大堆，对于索引，则和它的左右子节点比较，如果左右子节点的值大于该节点，则交换，然后继续下去。代码实现：
python:

def swap(array, array_a, array_b):
    temp = array[array_a]
    array[array_a] = array[array_b]
    array[array_b] = temp

def max_heap_down(array, current, last):
    max = current
    while True:
        if 2 * current + 1 <= last and array[2 * current + 1] > array[max]:
            max = 2 * current + 1
        if 2 * current + 2 <= last and array[2 * current + 2] > array[max]:
            max = 2 * current + 2
        if max != current:
            swap(array, current, max)
            current = max
        else:
            return

def initial_max_heap(array, array_len):
    for i in range((array_len - 1) / 2, -1, -1):
        max_heap_down(array, i, array_len - 1)


def heap_sort(array):
    if not array or len(array) <= 1:
        return
    array_len = len(array)
    initial_max_heap(array, array_len)
    swap(array, 0, array_len - 1)
    for i in range(array_len - 2, 0, -1):
        max_heap_down(array, 0, i)
        swap(array, 0, i)

算法复杂度为，算法不太稳定。

计数排序

适合有特性的数组，比如正整数排序。设最大范围为m，建立一个m+1长的数组，用于记录某个正整数有几个，然后遍历要排序数组，把对应数字的个数记录下来，再通过该数组进行排序。代码实现：
python:

def counting_sort(array, max):
    if not array or len(array) <= 1:
        return
    array_len = len(array)
    temp_array = [0] * (max + 1)
    for i in range(0, array_len):
        temp_array[array[i]] += 1
    temp = 0
    for i in range(0, max + 1):
        if temp >= array_len:
            break
        while temp_array[i] > 0:
            array[temp] = i
            temp_array[i] -= 1
            temp += 1

算法时间复杂度为，算法比较稳定。

桶排序

将一段区间分为n等分，比如100个数字，设置10个桶，1-10再第一个桶，依次类推。然后遍历数组，将对应的数字放在对应桶中，对每个桶中的数组进行排序，然后回到原数组。代码实现：
python:

def bucket_sort(array):
    if not array or len(array) <= 1:
        return
    array_len = len(array)
    max_num = max(array)
    min_num = min(array)
    bucket_num = 10
    if (max_num - min_num + 1) < 10:
        bucket_num = max_num - min_num
    avg_num = (max_num - min_num) / bucket_num
    temp_array = [[] for i in range(bucket_num)]
    for i in range(array_len):
        bucket_pos = (array[i] - min_num + 1) / avg_num
        if bucket_pos >= bucket_num:
            bucket_pos = bucket_num - 1
        temp_array[bucket_pos].append(array[i])

    temp = 0
    for i in range(bucket_num):
        quick_sort(temp_array[i])
        for j in temp_array[i]:
            array[temp] = j
            temp += 1

若有n个数字，m个桶，每个桶存k个数，则时间复杂度为，算法稳定性取决于每个桶使用什么排序算法。

基数排序

基数排序可以理解为一种桶排序，它从最低位数字开始排序，依次到高位数字结束，代码实现：
python:

def radix_sort(array):
    if not array or len(array) <= 1:
        return
    array_len = len(array)
    i = 0   # 最低位
    max_num = max(array)
    j = len(str(max_num)) # 最大值位数
    while i < j:
        bucket_list = [[] for i in range(10)]
        for num in array:
            bucket_list[int(x / (10**i)) % 10].append(num)

        array.clear()
        for i in bucket_list:
            for j in i:
                array.append(j)

        i += 1

时间复杂度位，算法稳定。

希尔排序

这是一种插入排序的改良。希尔排序会先设定一个步长，这里选择数组长度的一半，每个一个步长，组成一个要排序的数组进行排序，然后多个数组进行插入排序，一轮排序后，步长除以2，重复上面的步骤，直到步长为1，就是整个数组进行一次插入排序，终止。代码实现：
python:

def shell_sort(array):
    if not array or len(array) <= 1:
        return
    array_len = len(array)
    step = array_len / 2
    while step > 0:
        for i in range(step):
            for j in range(i + step, array_len, step):
                for k in range(i ,j, step):
                    if array[j] < array[k]:
                        break
                    else: 
                        k += step

                    if k < j:
                        temp_k = k
                        temp = array[i]
                        while temp_k >= k:
                            tmp = array[temp_k]
                            array[temp_k] = array[temp_k + step]
                            array[temp_k + step] = tmp
                            temp_k -= step
                        array[k] = tmp

        step /= 2

时间复杂度上比插入排序好，算法稳定。