package main
import "fmt"
func QuickSort(arr []int) {
	if len(arr) <= 1 {
		return
	}
	// 選中間位置作為基準，比它值小的移動到左邊，比它大的值移動到右邊
	pivotIndex := len(arr) / 2
	pivot := arr[pivotIndex]
	arr[pivotIndex], arr[len(arr)-1] = arr[len(arr)-1], arr[pivotIndex]
	left := 0
	right := len(arr) - 2
	for left <= right { // 每一輪移動一次指針
		if arr[left] <= pivot {
			left++
		} else {
			arr[left], arr[right] = arr[right], arr[left]
			right--
		}
	}
	pivotIndex = left
	arr[left], arr[len(arr)-1] = arr[len(arr)-1], arr[left]
	QuickSort(arr[:pivotIndex])
	QuickSort(arr[pivotIndex+1:])
}
func main() {
	arr := []int{4, 1, 3, 5, 2}
	QuickSort(arr)
	fmt.Println(arr)
}

func quickSort(data []int) {
//如果數(shù)組長度為1，返回
	if len(data) <= 1 {
		return
	}
	//設置基準為數(shù)組第一個元素
	base := data[0]
	//兩個指針分別指向待交換首尾位置
	l, r := 0, len(data)-1
	//基準為第一個元素，比較的元素從第二個開始
	for i := 1; i <= r; {
	//如果比較元素大于基準元素，把該元素放到數(shù)組尾部，把尾部元素交換過來
	//此時尾部的元素已經(jīng)判斷過比基準元素大，因此r--向前移動，
	//而i所在的元素為新交換過來的還沒有判斷過大小，因此保持不動
		if data[i] > base {
			data[i], data[r] = data[r], data[i]
			r--
		} else {
		//如果比較元素小于等于基準元素，則交換當前元素和基準元素的位置
		//l指向的是基準元素，因此l++才能重新指向基準元素,i++判斷下一個數(shù)
			data[i], data[l] = data[l], data[i]
			l++
			i++
		}
	}
	//此時l指向基準元素，l前面的元素都比l小，l后面的都比l大
	//因此對l前面和后面的數(shù)組再次快排，直到子數(shù)組長度為1結(jié)束
	quickSort(data[:l])
	quickSort(data[l+1:])
}

func mergeSort(data []int) []int {
	length := len(data)
	//如果長度為1不可再分，就返回
	if length <= 1 {
		return data
	}
	//把數(shù)組一分為二
	num := length / 2
	//左邊和右邊的數(shù)組都要再分
	left := mergeSort(data[:num])
	right := mergeSort(data[num:])
	//對于每對數(shù)組進行排序
	return merge(left, right)
}
func merge(left, right []int) (result []int) {
//數(shù)組是從長度為1開始進行添加的，因此每個子數(shù)組都是有序的
	l, r := 0, 0
	//當兩個數(shù)組都沒有遍歷完的時候，按照元素大小依次添加
	for l < len(left) && r < len(right) {
		if left[l] < right[r] {
			result = append(result, left[l])
			l++
		} else {
			result = append(result, right[r])
			r++
		}
	}
	//一個數(shù)組遍歷完比，把沒有遍歷完的數(shù)組直接添加進去
	result = append(result, left[l:]...)
	result = append(result, right[r:]...)
	return
}

func heapSort(array []int) {
	m := len(array)
	s := m / 2
	for i := s; i > -1; i-- {
		heap(array, i, m-1)
	}
	for i := m - 1; i > 0; i-- {
		array[i], array[0] = array[0], array[i]
		heap(array, 0, i-1)
	}
}
func heap(array []int, i, end int) {
	l := 2*i + 1
	if l > end {
		return
	}
	n := l
	r := 2*i + 2
	if r <= end && array[r] > array[l] {
		n = r
	}
	if array[i] > array[n] {
		return
	}
	array[n], array[i] = array[i], array[n]
	heap(array, n, end)
}