// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
func bubbleSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr)-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

func bubbleSort2(arr []int) {
	l, r := 0, len(arr)-1
	for ; l < r; {
		for i := l; i < r; i++ {
			if arr[i] > arr[i+1] {
				arr[i], arr[i+1] = arr[i+1], arr[i]
			}
		}
		r--
		for i := r; i > l; i-- {
			if arr[i] < arr[i-1] {
				arr[i], arr[i-1] = arr[i-1], arr[i]
			}
		}
		l++
	}
}

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
func selectionSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		minValeIndex := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[minValeIndex] {
				minValeIndex = j
			}
		}
		arr[i], arr[minValeIndex] = arr[minValeIndex], arr[i]
	}
}

// 分类 ------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
func insertSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		toInsertValue := arr[i]
		var j int
		for j = i - 1; j >= 0; j-- {
			if arr[j] <= toInsertValue {
				break
			}
			arr[j+1] = arr[j]
		}
		arr[j+1] = toInsertValue
	}
}

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
func insertSort2(arr []int) {
	for i := 1; i < len(arr); i++ {
		toInsertValue := arr[i]
		l, r := 0, i-1
		for ; l <= r; {
			mid := l + (r-l)/2
			if arr[mid] < toInsertValue {
				l = mid + 1
			} else {
				r = mid - 1
			}
		}
		var j int
		for j = i - 1; j >= l; j-- {
			arr[j+1] = arr[j]
		}
		arr[j+1] = toInsertValue
	}
}

func insertSort3(arr []int) {
	for incre := len(arr) / 2; incre >= 1; incre = incre / 2 {
		for i := incre; i < len(arr); i++ {
			toInsertValue := arr[i]
			var j int
			for j = i - incre; j >= 0; j -= incre {
				if arr[j] <= toInsertValue {
					break
				}
				arr[j+incre] = arr[j]
			}
			arr[j+incre] = toInsertValue
		}
	}
}

func guibingSort(arr []int, l, r int) {
	if l >= r {
		return
	}
	mid := l + (r-l)/2
	guibingSort(arr, l, mid)
	guibingSort(arr, mid+1, r)
	merge(arr, l, r)
}
func merge(arr []int, l, r int) {
	if l >= r {
		return
	}
	len := r - l + 1
	newArr := make([]int, len)
	mid := l + (r-l)/2
	i, j := l, mid+1
	index := 0
	for ; i <= mid && j <= r; index++ {
		if arr[i] < arr[j] {
			newArr[index] = arr[i]
			i++
		} else {
			newArr[index] = arr[j]
			j++
		}
	}
	if i <= mid {//这里注意是<=
		for ; i <= mid; i++ {
			newArr[index] = arr[i]
			index++
		}
	}
	if j <= r {//这里注意是<=
		for ; j <= r; j++ {
			newArr[index] = arr[j]
			index++
		}
	}
	for index := 0; l <= r; l++ {
		arr[l] = newArr[index]
		index++
	}
}

//先进行一遍排序，第一个做基准，左边的比基准小，右边的比基准大;进行一遍排序后对剩余的进行分组再进行重复
func QuickSort(arr []int, start, end int) {
	if start >= end {
		return
	}
	l, r := start, end //[l,r]为待排序的，l左边和r右边的都是已经排好的
	k := arr[l]        //基准,那么左边第一个就是坑，任何比k小的都可以放进去
	for ; r > l; {
		//从右边往左，找到比基准小的，填到坑里，那么右边的就变成了新的坑，任何比k大的都可以放进去
		for ; r > l && arr[r] >= k; r-- {

		}
		arr[l] = arr[r]
		//从左往右，找到比基准大的
		for ; r > l && arr[l] <= k; l++ {

		}
		arr[r] = arr[l]
	}
	//当for循环结束，说明l和r相遇了，那么l=r处就是最后的坑，直接把k放进去即可，这样一遍下来，k的左边比k小，右边比k大
	arr[l]=k
	//剩余的分两组，进行重复操作
	QuickSort(arr, start, l-1)
	QuickSort(arr, l+1, end)
}

func QuickSort3(arr []int, start, end int) {
	if start >= end {
		return
	}
	l, r := start, end //[start,l)为小于基准，(r,end]大于基准。都是已经排好的
	i := l + 1 //[l,i)等于基准，[i,r]等待排序
	k := arr[l]
	for ; r > l && i <= end; {
		if arr[i]<k{
			arr[l],arr[i]=arr[i],arr[l]
			l++
			i++
		}else if arr[i]>k{
			arr[r],arr[i]=arr[i],arr[r]
			r--
		}else {
			i++
		}
	}

	QuickSort3(arr, start, l-1)
	QuickSort3(arr, r+1, end)
}