快速排序

基于分制的思想

func quicksort(list []int, left, right int) {
	if left >= right {
		return
	}
	pivot := partition(list, left, right)
	fmt.Println(pivot)
	quicksort(list, left, pivot-1)
	quicksort(list, pivot+1, right)
}

// 基于pivot进行分制


func partition2(arr []int, low, high int) int {
	pivot := arr[high]
	counter := low
	for j := low; j < high; j++ {
		if arr[j] < pivot {
			arr[counter], arr[j] = arr[j], arr[counter]  //比基点小的放前边
			counter++
		}
	}
	arr[counter], arr[high] = arr[high], arr[counter]  //将基点放到合适的位置
	return counter
}

// 分成两类数  一组比基点小  另一组比基点大
// 

func partition(arr []int, low, high int) int {
	pivot := arr[low] // 基准点选择最左边的元素
	i := low
	j := high
	for i < j {
		for i < j && arr[j] > pivot {
			j--
		}
		for i < j && arr[i] <= pivot { //= 号位置不能乱写  前置条件不能省略 i < j
			i++
		}

		arr[i], arr[j] = arr[j], arr[i]  // 左右指针相互交换

	}
	fmt.Println("i", i, "j", j)
	arr[low], arr[i] = arr[i], arr[low]  //基点放到合适的位置
	return i
}

//测试
func main() {
	list := make([]int, 0)
	list = append(list, 5, 2, 8, 2, 9, 5, 1, 7)
	fmt.Println(list)
	quicksort(list, 0, len(list)-1)
	fmt.Println(list)
}

// 简单 但是浪费空间
func quickSort2(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	pivot := arr[0]
	var left, right []int

	for _, v := range arr[1:] {
		if v <= pivot {
			left = append(left, v)
		} else {
			right = append(right, v)
		}
	}

	left = quickSort2(left)
	right = quickSort2(right)

	return append(append(left, pivot), right...)
}