package main

import "fmt"

// 快速排序
// 特征:
// 		1. 选定一个数，让这个数左边的比这个数小，右边比这个数大
//		2. 然后这个基数就是已经排好序的，将左边部分和右边部分执行1操作
//		3. 递归
// 实现:
//		1. 难点：
//			a. 参考数怎么找?
//			b. 如何让这个数左边的数比这个数小，右边的数比这个数大(最难的部分) => 填坑大法
//			c. 递归的退出条件


// QuickSort 快速排序
func QuickSort(nums []int, left, right int) {
	// 1. refer 参考数，一般等于元组中第一个元素
	refer := nums[left]
	loopFlag := true
	// 2. 让这个数左边的比这个数小，右边比这个数大
	for loopFlag {
		// 1. 先在右边找比查考数小的数，找到则赋值给左边
		for {
			if left == right {
				// 如果两者相等，意味着目标达成，这个位置的数就是已经拍好序的
				nums[left] = refer
				loopFlag = false
				break
			}
			if nums[right] >= refer {
				right --
			}  else {
				// 3. 在右边找到则将值赋值给
				nums[left] = nums[right]
				break
			}
		}

		// 2. 先在左边找比参考数大的数，赋值给右边
		for {
			// 如果两者相等，意味着目标达成，这个位置的数就是已经排好序的
			if left == right {
				nums[left] = refer
				loopFlag = false
				break
			}
			
			if nums[left] <= refer {
				left ++
			} else {
				// 3. 在右边找到则将值赋值给
				nums[right] = nums[left]
				break
			}
		}
	}
	//fmt.Println(left, right)
	// 左边部分
	leftPart := nums[:left]
	//  右边部分
	rightPart := nums[right+1:]
	//fmt.Println("left:", leftPart)
	//fmt.Println("Right:", rightPart)
	// 左边不为空则排序
	if len(leftPart) != 0 {
		QuickSort(leftPart, 0, len(leftPart)-1)
	}
	//  右边不为空则排序，也是递归的退出条件
	if len(rightPart) != 0 {
		QuickSort(rightPart, 0, len(rightPart)-1)
	}

}

func main() {
	//nums := []int{64, 5, 2, 44, 22, 45, 22, 666 , 22, 77, 3, 64, 74, 74, 73, 22, 43, 23,56, 77, 777}
	//nums := []int{56, 5, 2, 44, 22, 45, 22, 23, 22, 43, 3, 64, 22}
	//nums := []int{56, 5, 2, 44, 45, 22, 23, 43, 3, 64}
	//nums := []int{3, 5, 2, 44, 45, 22, 23, 43}
	nums := []int{64}
	//nums := []int{64, 33}
	//nums := []int{64, 33, 55}
	QuickSort(nums, 0, len(nums)-1)
	fmt.Println(nums)
}