# 直接排序
def sort(list):
    n = len(list)
    for i in range(n-1):
        for j in range(i+1,n):
            if list[i]>list[j]:
                list[i],list[j] = list[j],list[i]
    return list

# 冒泡
def bubbleSort(list):
    n = len(list)
    for i in range(n-1):            # 该层循环控制 需要冒泡的轮数
        for j in range(n-1,i,-1):   # 每次循环比较相邻两个数，按大小交换
            if list[j-1] >list[j]:
                list[j-1],list[j] = list[j],list[j-1]
    return list

//冒泡 go
func bubble(list []int) []int {
    n := len(list)
    for i := 0; i < n; i++ {
        for j := n - 1; j > i; j-- {
            if list[j-1] > list[j] {
                list[j-1], list[j] = list[j], list[j-1]
            }
        }
    }
    return list
}

# 选择排序
def selectSort(list):
    n = len(list)
    for i in range(n-1):
        min = i
        # 每一趟选出一个最小值，放到前面
        for j in range(i+1,n):
            if list[j] < list[min]:
                min = j
        list[min],list[i] = list[i],list[min]
    return list

# 插入排序
def insertSort(list):
    n = len(list)
    for i in  range(1,n):
        min = list[i]
        # 不断地从后面选一个数，然后插入到前面已经有序的序列里
        for j in range(i-1,-1,-1):
            if list[j] > min:
                list[j+1],list[j] =list[j],list[j+1]
            else:
                break
    return list

# 快排
def quickSort(list):
    # 先判断是否需要继续进行
    n = len(list)
    if n <= 1:
        return list
    # 选择第一个元素作为基准
    base = list[0]
    # 遍历除了基准外的所有元素，按照大小关系放入两个数组内
    left = []
    right = []
    for i in range(1, n):
        if base > list[i]:
            left.append(list[i])
        else:
            right.append(list[i])
    # 分别对左边和右边的数组进行相同的排序处理方式递归调用这个函数
    # 合并
    return quickSort(left)+[base]+quickSort(right)

//快排 go
func quick(list []int) []int {
    n := len(list)
    if n <= 1 {
        return list
    }
    base := list[0]
    left := []int{}
    right := []int{}
    for i := 1; i < n; i++ {
        if list[i] < base {
            left = append(left, list[i])
        } else {
            right = append(right, list[i])
        }
    }
    return append(append(quick(left), base), quick(right)...)
}

# 归并
def mergeSort(list):
    # 先判断是否需要继续进行
    n = len(list)
    if n <= 1:
        return list
    mid = n//2  # 向下取整
    # 拆分到单个元素,然后两个两个往上进行递归合并。
    left = mergeSort(list[:mid])
    right = mergeSort(list[mid:])

    # 设置left 和right两个游标, 进行合并
    left_point, right_point = 0, 0
    result = []
    while True:
        if left_point == len(left):
                result+=right[right_point:]
                break
        if right_point == len(right):
                result+=left[left_point:]
                break

        if left[left_point] < right[right_point]:
            result.append(left[left_point])
            left_point+=1
        else:
            result.append(right[right_point])
            right_point+=1
    return result

//归并 go
func merge(list []int) []int {
    n := len(list)
    if n <= 1 {
        return list
    }
    mid := n / 2
    l1 := merge(list[:mid])
    l2 := merge(list[mid:])
    p1, p2 := 0, 0
    l := []int{}
    for {
        if p1 == len(l1) {
            l = append(l, l2[p2:]...)
            break
        }
        if p2 == len(l2) {
            l = append(l, l1[p1:]...)
            break
        }

        if l1[p1] < l2[p2] {
            l = append(l, l1[p1])
            p1++
        } else {
            l = append(l, l2[p2])
            p2++
        }
    }
    return l
}

nums = [6,8,4,7,2,1]
# print(sort(nums))
# print(bubbleSort(nums))
# print(quickSort(nums))
# print(selectSort(nums))
# print(insertSort(nums))
# print(mergeSort(nums))