package quickSortV1

import (
	"InterviewQuestions/Algo/sort"
	"fmt"
)

/**
 * @Author: yirufeng
 * @Email: yirufeng@foxmail.com
 * @Date: 2020/9/10 7:45 上午
 * @Desc:
 */

/*
快速排序第1个版本：选择第1个元素作为划分枢轴
注意：切片作为参数传递的时候是一个引用
*/
func QuickSort(nums []int) []int {
	quickSort(nums, 0, len(nums)-1)
	return nums
}

func quickSort(nums []int, low int, high int) {
	var pivotkey int
	if low < high {
		//pivotkey 为枢轴防止的最终下标
		pivotkey = partition(nums, low, high)
		quickSort(nums, low, pivotkey-1)
		quickSort(nums, pivotkey+1, high)
	}
}

func partition(nums []int, low int, high int) int {
	//选择划分元素
	dummy := nums[low]
	for low < high {
		for low < high && dummy <= nums[high] {
			high--
		}
		swap(nums, low, high)
		for low < high && dummy > nums[low] {
			low++
		}
		swap(nums, low, high)
	}
	//最后low == high
	return low
}

func swap(nums []int, i int, j int) {
	nums[i], nums[j] = nums[j], nums[i]
}


//------------------------------for test------------------------------
func main() {

	fmt.Println(QuickSort(sort.RandArray(100)))
}