Cacher is the code snippet organizer for pro developers

#! /usr/bin/env python
# -*- coding: UTF-8 -*-

"""
@Author: LuMingdong

@License: (C) Copyright 2017.

@Contact: lumingdong@live.cn

@Project: Alg

@File: Sort.py.py

@Create Date: 2019/11/28 0028 14:37

@Version: 1.0

@Description: Now is better than never.  ——The Zen of Python

"""


# 1. bubbleSort
def bubbleSort(arr):
    for i in range(1, len(arr)):  # 对L-1个位置进行迭代
        for j in range(0, len(arr)-i):  #  最后的是最大的，对比次数每次都减小1次
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
# 优化：https://blog.csdn.net/hansionz/article/details/80822494

# 2. selectionSort
def selectionSort(arr):
    for i in range(0, len(arr)-1):
        minIndex = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr


# 3. insertionSort
def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i - 1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex+1] = current
    return arr


# 4. 优化：（拆半插入）希尔排序
# 动画： https://www.jianshu.com/p/40dcc3b83ddc
# 希尔排序利用分组粗调的方式减少了直接插入的工作量
# 分组的方式可以是按排序元素总数逐步折半进行跨越选取，如8个元素所使用的分组跨度为（4，2，1），被称为希尔排序的增量，
# 增量的选择可以有很多种，这里所用的逐步折半的增量方法，是Donald Shell在发明希尔排序时提出的一种朴素方法，被称为希尔增量。
"""
希尔排序是插入排序的一种改进版本，Donald Shell在1959年提出而得名。

希尔排序的实现思路：设定一个缩小增量的规则，以某个增量对数组进行分组，对每个分组进行直接插入排序，然后缩小增量再次分组依次类推，直到增量缩小到1，程序结束。

希尔排序的时间复杂度与增量序列的选取有关。关键词比较次数、记录移动次数和增量序列选择之间的关系，至今没有一个统一的公式可以归纳。
在中小规模的排序中，希尔排序占优，在大规模数据量的排序中快排占优。在实际场景中根据测试数据结果选择使用哪种排序。

稳定性：不稳定，相同的元素可能会颠倒位置。

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。
动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。在这里，我就使用了这种方法。
"""
def shellSort(arr):
    gap = 1
    while gap < len(arr)/3:
        gap = gap * 3 + 1   # 动态定义间隔序列
        print gap
    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > temp:
                arr[j+gap] = arr[j]
                j -= gap
            arr[j+gap] = temp
        gap = gap / 3  # gap // 3 (in python3)
        print gap
    return arr


# 5. 归并排序
def mergeSort(arr):
    if len(arr) < 2:
        return arr
    middle = len(arr) / 2  # len(arr)//2 （in Python3）
    left, right = arr[:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result


# 6.快速排序，QuickSort
def quickSort(arr, left=None, right=None):
    left = left if isinstance(left, (int, float)) else 0
    right = right if isinstance(right, (int, float)) else len(arr)-1
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    povit = left
    j = povit + 1  # j是处理区分界点
    i = j  # i是循环指针
    while i <= right:
        print 'i=', i
        if arr[i] < arr[povit]:
            swap(arr, i, j)
            print 'j=', j
            j += 1
        i += 1
    swap(arr, povit, j-1)
    return j-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

# 7.堆排序(HeapSort)

# 8.桶排序（BucketSort）
def bucketSort(arr, bucket_size=5):
    if len(arr) == 0:
        return arr
    min_value, max_value = arr[0], arr[0]
    for i in range(len(arr)):
        if arr[i] < min_value:
            min_value = arr[i]
        elif arr[i] > max_value:
            max_value = arr[i]

    bucket_count = (max_value - min_value) / bucket_size + 1
    buckets = [[] for x in range(bucket_count)]

    for i in range(len(arr)):
        buckets[(arr[i]-min_value)/bucket_size].append(arr[i])  # map to bucket

    sorted_arr = []
    for i in range(bucket_count):
        quickSort(buckets[i])
        for v in range(len(buckets[i])):
            sorted_arr.append(buckets[i][v])
    return sorted_arr

# 8.计数排序
def countingSort(arr, max_value=None):
    if max_value is None:
        max_value = max(arr)
    bucket_len = max_value + 1
    buckets = [0] * bucket_len
    sorted_index = 0
    for i in range(len(arr)):
        if not buckets[arr[i]]:
            buckets[arr[i]] = 0
        buckets[arr[i]] += 1
    for j in range(bucket_len):
        while buckets[j] > 0:
            arr[sorted_index] = j
            sorted_index += 1
            buckets[j] -= 1
    return arr

# 9.基数排序

def radix(arr):
    digit = 0
    max_digit = 1
    max_value = max(arr)
    # 找出列表中最大的位数
    while 10 ** max_digit < max_value:
        max_digit = max_digit + 1

    while digit < max_digit:
        temp = [[] for i in range(10)]
        for i in arr:
            # 求出每一个元素的个、十、百位的值
            t = int((i / 10 ** digit) % 10)
            temp[t].append(i)

        coll = []
        for bucket in temp:
            for i in bucket:
                coll.append(i)

        arr = coll
        digit = digit + 1

    return arr


# main
if __name__ == '__main__':
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print radix(arr)