'''
1. bubbleSort
2. selectionSort
3. incertionSort
4. shellSort
5. mergeSort
6. quickSort
7. heapSort
8. countingSort
9. bucketSort
10.radisSort
'''

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

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将i和最小数交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

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

def shellSort(arr):
    gap = 1
    while gap < len(arr) // 3:
        gap = gap * 3 + 1
    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
    return arr

def mergeSort(arr):
    if len(arr) < 2:
        return arr
    middle = len(arr) // 2
    # 注意:写法虽简单，但传递整个数组，在数组很大时，空间消耗
    left, right = arr[:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))


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

    while left:
        res.append(left.pop(0))
    while right:
        res.append(right.pop(0))
    return res

def MergeSort(lst):
    def merge(arr, left, mid, right):
        temp = []
        i = left
        j = mid + 1
        while i <= mid and j <= right:
            if arr[i] <= arr[j]:
                temp.append(arr[j])
                i += 1
            else:
                temp.append((arr[j]))
                j += 1
        while i <= mid:
            temp.append(arr[i])
            i += 1
        while j <= right:
            temp.append(arr[j])
            j += 1
        for i in range(left, right + 1):
            arr[i] = temp[i - left]

    def mSort(arr, left, right):
        if left >= right:
            return
        mid = (left + right) // 2
        mSort(arr, left, mid)
        mSort(arr, mid + 1, right)
        merge(arr, left, mid, right)

    n = len(lst)
    if n <= 1:
        return lst
    mSort(lst, 0, n - 1)
    return lst

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left, (int, float)) else left
    right = len(arr) - 1 if not isinstance(right, (int, float)) else right

    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):
    pivot = left
    index = pivot + 1
    i = index
    while i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index += 1
        i += 1
    swap(arr, pivot, index - 1)
    return index


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

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr) - 1, 0, -1):
        swap(arr, 0, i)
        arrLen -= i
        heapify(arr, 0)
    return arr


def buildMaxHeap(arr):
    for i in range(len(arr) // 2, -1, -1):
        heapify(arr, i)


def heapify(arr, i):
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)
     
 def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def countingSort(arr, maxValue):
    bucketLen = maxValue + 1
    bucket = [0] * bucketLen
    sortedIndex = 0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]] = 0
        bucket[arr[i]] += 1
    for j in range(bucketLen):
        while bucket[j] > 0:
            arr[sortedIndex] = j
            sortedIndex += 1
            bucket[j] -= 1
    return arr

def bucket_sort(arr, n):
    '''
    1.创建n个空桶
    2.把arr[i] 插入到bucket[n*array[i]]
    3.桶内排序
    4.产生新的排序后的列表
    '''
    bucket_list = [[] for _ in range(n)]

    for data in arr:
        index = int(data * n)
        bucket_list[index].append(data)

    for i in range(n):
        bucket_list.sort()

    index = 0
    for i in range(n):
        for j in range(len(bucket_list[i])):
            arr[index] = bucket_list[i][j]
            index += 1
    return arr

def radix_sort(s):
    # 记录当前正在排哪一位，最低位为1
    i = 0
    max_num = max(s)
    j = len(str(max(s)))  # 记录最大值的位数
    while i < j:
        bucket_list = [[] for _ in range(10)]
        for x in s:
            bucket_list[int(x / (10 ** i)) % 10].append(x)  # 找到位置放入桶数组
        s.clear()

        for x in bucket_list:  # 放回原数组
            for y in x:
                s.append(y)
        i += 1
    return s