# 以上均属性个人理解 若有错误 烦请提出 !

# 冒泡排序
# 一般冒泡排序的时间复杂度为O（n^2）
# 每一次循环都把最大的一个数往右浮
# 如果是进行排行榜取前几的榜单业务，用冒泡的话时间复杂度为O（n）
def BubbleSort(val):
    for i in range(len(val)):
        for j in range(len(val)-i-1):
            if val[j] > val[j+1]:
                val[j],val[j+1] = val[j+1],val[j]
    return val

# 选择排序
# 个人感觉跟冒泡排序 没差太多 就是在中间设置了个最小值的变量
# 每一次都会找到最小值 并把最小值往左移
# 时间复杂度一样为O（n^2）
def SelectSort(val):
    for i in range(len(val)):
        minloc = i
        for j in range(i+1,len(val)):
            if val[j] < val[minloc]:
                val[j],val[minloc] = val[minloc],val[j]
    return val


# 插入排序
# 依次取出的数跟前几个数相比 把它放在正确位置。列表i前面的位置是有序的
# 时间复杂度为O（n^2）
def InsertSort(val):
    for i in range(len(val)):
        temp = val[i]
        j = i - 1
        while j >=0 and val[j] > temp:
            val[j+1] = val[j]
            j = j - 1
        val[j+1] = temp
    return val


# 快速排序
# 暴力的不断拆分成左右，然后进行对比排序
# 在左右列表合并前都是有序的 然后进行合并
# 时间复杂度为O（nlogn）
def Partition(val,left,right):
    temp = val[left]
    while left < right:
        while left < right and val[right] >= temp:
            right = right - 1
        val[left] = val[right]
        while left < right and val[left] <= temp:
            left = left + 1
        val[right] = val[left]
    val[left] = temp
    return left
def _QuickSort(val,left,right):
    if left < right:
        mid = Partition(val,left,right)
        _QuickSort(val,left,mid-1)
        _QuickSort(val,mid+1,right)
def QuickSort(val):
    _QuickSort(val,0,len(val))
    return val

# 快排二
def quickSort(val,left,right):
    if left < right:
        temp = val[right]
        mid =left-1
        for j in range(left,right):
            if val[j] <= temp:
                # 如果val[j]<=temp 那么说明j是小的可以左移
                mid+=1
                val[mid],val[j] = val[j],val[mid]
        # 说明j 比最右边大 和右调换位置 下次循环为temp
        val[mid+1],val[right] = val[right],val[mid+1]
        mid = mid+1
        quickSort(val,left,mid-1)
        quickSort(val,mid+1,right)
    return val
val = [11,32,22,55,67,2,30,44,78,98]
res = quickSort(val,0,len(val)-1)
print(res)



# 归并排序 
# 个人的感觉就是归并排序和快速排序的区别不大
# 好吧 归并的话需要再申请一个列表 添加排完序的列表
# 时间复杂度为 O（nlogn）
def MergeSort(val,left,right):
    if left < right:
        mid = (left + right)//2
        MergeSort(val,left,mid)
        MergeSort(val,mid+1,right)
        return Merge(val,left,mid,right)

def Merge(val,left,mid,right):
    i = left
    j = right
    temp = []
    if left <right:
        while i <= mid and j <=right:
            if val[i] <val[j]:
                temp.append(val[i])
                i = i + 1
            else:
                temp.append(val[j])
                j = j + 1
        while i <= mid:
            temp.append(val[i])
            i = i + 1
        while j <= right:
            temp.append(val[j])
            j = j + 1
    val[left : right+1] = temp
    return val