# 冒泡排序
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
if __name__ == '__main__':
  list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  print("List source is:", list)
  result = bubbleSort(list)
  print("List sort is:", result)

# 快速排序
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-1
def swap(arr, i, j):
  arr[i], arr[j] = arr[j], arr[i]
if __name__ == '__main__':
  list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  print("List source is:", list)
  result = quickSort(list)
  print("List sort is:", result)

def quickSort2(array):
  return array if len(array) <= 1 else quickSort2([lt for lt in array[1:] if lt < array[0]]) + array[0:1] + quickSort2([ge for ge in array[1:] if ge >= array[0]])

# 选择排序
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
if __name__ == '__main__':
  list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  print("List source is:", list)
  result = selectionSort(list)
  print("List sort is:", result)

# 堆排序
def buildMaxHeap(arr):
  import math
  for i in range(math.floor(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 heapSort(arr):
  global arrLen
  arrLen = len(arr)
  buildMaxHeap(arr)
  for i in range(len(arr)-1,0,-1):
    swap(arr,0,i)
    arrLen -=1
    heapify(arr, 0)
  return arr
if __name__ == '__main__':
  list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  print("List source is:", list)
  result = heapSort(list)
  print("List sort is:", result)

# 作者：沙振宇
# 插入排序
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
if __name__ == '__main__':
  list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  print("List source is:", list)
  result = insertionSort(list)
  print("List sort is:", result)

# 作者：沙振宇
# 希尔排序
def shellSort(arr):
  import math
  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 = math.floor(gap/3)
  return arr
if __name__ == '__main__':
  list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  print("List source is:", list)
  result = shellSort(list)
  print("List sort is:", result)

# 作者：沙振宇
# 归并排序
def mergeSort(arr):
  import math
  if(len(arr)<2):
    return arr
  middle = math.floor(len(arr)/2)
  left, right = arr[0: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
if __name__ == '__main__':
  list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  print("List source is:", list)
  result = mergeSort(list)
  print("List sort is:", result)

# 作者：沙振宇
# 计数排序
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
if __name__ == '__main__':
  list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  print("List source is:", list)
  result = countingSort(list,max(list))
  print("List sort is:", result)

# 作者：沙振宇
# 基数排序
def radix_sort(arr):
  """基数排序"""
  i = 0 # 记录当前正在排拿一位，最低位为1
  max_num = max(arr) # 最大值
  j = len(str(max_num)) # 记录最大值的位数
  while i < j:
    bucket_list =[[] for _ in range(10)] #初始化桶数组
    for x in arr:
      bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶数组
    arr.clear()
    for x in bucket_list:  # 放回原序列
      for y in x:
        arr.append(y)
    i += 1
  return arr
if __name__ == '__main__':
  list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  print("List source is:", list)
  result = radix_sort(list)
  print("List sort is:", result)

# 作者：沙振宇
# 桶排序
def bucketSort(arr):
  # 选择一个最大的数
  max_num = max(arr)
  # 创建一个元素全是0的列表, 当做桶
  bucket = [0] * (max_num + 1)
  # 把所有元素放入桶中, 即把对应元素个数加一
  for i in arr:
    bucket[i] += 1
  # 存储排序好的元素
  sort_nums = []
  # 取出桶中的元素
  for j in range(len(bucket)):
    if bucket[j] != 0:
      for y in range(bucket[j]):
        sort_nums.append(j)
  return sort_nums
if __name__ == '__main__':
  list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  print("List source is:", list)
  result = bucketSort(list)
  print("List sort is:", result)