// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
)

func quickSortFunc(array1 []int, array2 []int) []int {
	var res []int
	var tmp []int
	var m = make(map[int]int)
	for _, v := range array2 {
		m[v] = 0
	}
	for _, v := range array1 {
		_, ok := m[v]
		if ok {
			m[v]++
		} else {
			tmp = append(tmp, v)
		}
	}
	for _, v := range array2 {
		for m[v] > 0 {
			res = append(res, v)
			m[v]--
		}
	}
	quickSort(tmp, 0, len(tmp)-1)
	res = append(res, tmp...)
	return res
}

func quickSort(array []int, left int, right int) {
	if left >= right {
		return
	}
	index := partition(array, left, right)
	quickSort(array, left, index-1)
	quickSort(array, index+1, right)
}

func partition(array []int, left int, right int) int {
	base := array[left]
	for left < right {
		for array[right] >= base && left < right {
			right--
		}
		array[left] = array[right]
		for array[left] <= base && left < right {
			left++
		}
		array[right] = array[left]
	}
	array[right] = base
	return right
}

func main() {
	array1 := []int{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19}
	array2 := []int{2, 1, 4, 3, 9, 6}
	res := quickSortFunc(array1, array2)
	fmt.Println(res)
}

//$ go run interview6-11.go
//[2 2 2 1 4 3 3 9 6 7 19]