python实现各种排序算法

这些排序都是比较经典的排序算法：

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序
• 快速排序
• 计数排序
• 桶排序
• 基数排序

那么如何使用python来实现这些排序呢？

冒泡排序

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个。

重复以上步骤，直到排序完成。

def Bubble_Sort(array):
    length = len(array)
    for i in range(length):
        for j in range(length-i-1):
            if array[j] > array[j+1]: array[j+1], array[j] = array[j], array[j+1]
    return array

选择排序

1. 在未排序序列中找到最小元素，存放到排序序列的起始位置；
2. 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。

重复以上步骤，直到排序完成。

def Select_Sort(array):
    length = len(array)
    for i in range(length-1):
        idx_min = i
        for j in range(i+1, length):
            if array[j] < array[idx_min]:
                idx_min = j
        array[i], array[idx_min] = array[idx_min], array[i]
    return array

插入排序

1. 从第一个元素开始，该元素认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后。

重复步骤2~5，直到排序完成。

def Insert_Sort(array):
    length = len(array)
    for i in range(1, length):
        pointer, cur = i - 1, array[i]
        while pointer >= 0 and array[pointer] > cur:
            array[pointer+1] = array[pointer]
            pointer -= 1
        array[pointer+1] = cur
    return array

归并排序

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

def Merge(array_1, array_2):
    result = []
    while array_1 and array_2:
        if array_1[0] < array_2[0]:
            result.append(array_1.pop(0))
        else:
            result.append(array_2.pop(0))
    if array_1:
        result += array_1
    if array_2:
        result += array_2
    return result

def Merge_Sort(array):
    if len(array) < 2: return array
    pointer = len(array) // 2
    left = array[:pointer]
    right = array[pointer:]
    return Merge(Merge_Sort(left), Merge_Sort(right))

快速排序

1. 从数列中挑出一个元素，作为一个基准（pivot）；
2. 重新排序数列，将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面（相等的可以分到任一边），于是该基准就处于数列的中间位置。
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

def Quick_Sort(array, left, right):
    if left >= right:
        return array
    pivot, i, j = array[left], left, right
    while i < j:
        while i < j and array[j] >= pivot:
            j -= 1
        array[i] = array[j]
        while i < j and array[i] <= pivot:
            i += 1
        array[j] = array[i]
    array[j] = pivot
    Quick_Sort(array, left, i-1)
    Quick_Sort(array, i+1, right)
    return array

计数排序

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中值为i的元素出现的次数，存入数组C的第i项；
3. 对所有的计数累加（从C中的第一个元素开始，每一项值和前一项相加）；
4. 反向填充目标数组——将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

def Count_Sort(array):
    length = len(array)
    max_value = max(array)
    count = [0 for _ in range(max_value+1)]
    output = [0 for _ in range(length)]
    for i in range(length):
        count[array[i]] += 1
    for i in range(1, len(count)):
        count[i] += count[i-1]
    for i in range(length):
        output[count[array[i]]-1] = array[i]
        count[array[i]] -= 1
    return output

桶排序

1. 设置一个大小定量的数组A当作空桶；
2. 遍历一组数据，并且把数据一个一个放到对应的桶里去（数i放入A(i)）；
3. 遍历桶数组，对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来。

def Bucket_Sort(array):
    max_value, min_value, length = max(array), min(array), len(array)
    buckets = [0 for _ in range(min_value, max_value+1)]
    for i in range(length):
        buckets[array[i]-min_value] += 1
    output = []
    for i in range(len(buckets)):
        if buckets[i] != 0:
            output += [i+min_value] * buckets[i]
    return output

基数排序

1. 取得数组中的最大数，并取得其位数；
2. 假设arr为原始数组，从最低位开始取每个位组成radix数组；
3. 对radix进行计数排序。

def Radix_Sort(array):
    max_value = max(array)
    num_digits = len(str(max_value))
    for i in range(num_digits):
        buckets = [[] for k in range(10)]
        for j in array:
            buckets[int(j / (10 ** i)) % 10].append(j)
        output = [m for bucket in buckets for m in bucket]
    return output