用Python手撕常见排序算法

所用python版本为2.7.6（与Python-3.5稍微有点语法变化）

冒泡排序：

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

if __name__ == __main__:
    a = [2,3,5,1,3,7,-6]
    print Bubble_sort(a)

选择排序：

def Select_sort(nums):
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            if nums[j] == min(nums[j:len(nums)]):
                nums[i], nums[j] = nums[j], nums[i]
                break
    return nums

if __name__ == __main__:
    a = [2,3,5,1,3,7,-6]
    print Select_sort(a)

插入排序（写的不怎么好，以后完善）

def insert_sort(nums):
    if nums[1] < nums[0]:
        nums[0], nums[1] = nums[1], nums[0]
    for i in range(2, len(nums)):
        for j in range(i)[::-1]:
            if nums[i] < min(nums[0:j]):
                y = nums.pop(i)
                nums.insert(0, y)
                break
            if nums[i] >= nums[j]:
                x = nums.pop(i)
                nums.insert(j+1, x)
                break
    return nums

if __name__ == __main__:
    a = [2,3,5,1,3,7,-6]
    print insert_sort(a)

快速排序（特别简单的快排代码）：

def qsort(nums):
    if len(nums) <= 1:
        return nums
    else:
        return qsort([i for i in nums[1:] if i < nums[0]]) + nums[0:1] + qsort([j for j in nums[1:] if j >= nums[0]])

if __name__ == __main__:
    a = [2,3,5,1,3,7,-6]
    print qsort(a)

非递归实现：

希尔排序：

def shell_sort(nums):
    gap = len(nums)/2
    while gap > 0:
        for i in range(gap, len(nums)):
            while i >= gap and nums[i-gap] > nums[i]:
                nums[i], nums[i-gap] = nums[i-gap], nums[i]
                i -= gap
        gap /= 2
    return nums

if __name__ == __main__:
    a = [2,3,5,1,3,7,-6]
    print shell_sort(a)

归并排序：

def merge(a, b):
    m, n = 0, 0
    c = []
    while m < len(a) and n < len(b):
        if a[m] <= b[n]:
            c.append(a[m])
            m += 1
        else:
            c.append(b[n])
            n += 1
    if m == len(a):
        for i in b[n:]:
            c.append(i)
    else:
        for i in a[m:]:
            c.append(i)
    return c
def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums)/2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)

if __name__ == __main__:
    a = [2,3,5,1,3,7,-6]
    print merge_sort(a)

堆排序：（有时间自己重新写个）