算法

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。

将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。

// 使用Go语言实现
func main() {
	nums := []int{4, 4, 2, 5, 2, 3}
	process(nums, 0, len(nums)-1)
	fmt.Println(nums)
}
func process(nums []int, L, R int) {
	if L == R {
		return
	}
	m := L + ((R - L) >> 2)
	process(nums, L, m)
	process(nums, m+1, R)
	merge(nums, L, m, R)
	return
}
func merge(nums []int, L, M, R int) {
	help := make([]int, R-L+1)
	i := 0
	p1 := L
	p2 := M + 1
	for p1 <= M && p2 <= R {
		if nums[p1] >= nums[p2] {
			help[i] = nums[p2]
			i++
			p2++
		} else {
			help[i] = nums[p1]
			i++
			p1++
		}
	}
	for p2 <= R {
		help[i] = nums[p2]
		i++
		p2++
	}
	for p1 <= M {
		help[i] = nums[p1]
		i++
		p1++
	}
	for i := 0; i < len(help); i++ {
		nums[i+L] = help[i]
	}
}

LCR 170. 交易逆序对的总数

此题使用归并排序进行解题

func reversePairs(record []int) int {

    return process(record, 0, len(record)-1)
}

func process(nums []int, L, R int) int {
	if L >= R {
		return 0
	}
	mid := L + ((R - L) >> 1)
	l := process(nums, L, mid)
	r := process(nums, mid+1, R)
	return l + r + merge(nums, L, mid, R)
}
func merge(nums []int, L, M, R int) int {
	help := make([]int, R-L+1)
	i := 0
	p1 := L
	p2 := M + 1
	res := 0
	for p1 <= M && p2 <= R {
		if nums[p1] > nums[p2] {
			help[i] = nums[p2]
			i++
			p2++
		} else {
            res += p2-(M+1)
			help[i] = nums[p1]
			i++
			p1++
		}
	}
	for p2 <= R {
		help[i] = nums[p2]
		i++
		p2++
	}
	for p1 <= M {
        res += R -M
		help[i] = nums[p1]
		i++
		p1++
	}
	for i := 0; i < len(help); i++ {
		nums[i+L] = help[i]
	}
	return res
}

快排

快排的 partition 其实与昨天的荷兰国旗的思路是一样的，每次将目标元素放置数组的中间，小于目标值的放左边，大于目标值的放右边。

在partition中，特别要注意他的边界值，因为对边界值认知不清晰导致一个快速排序用了非常多的时间去了

// 初始化随机数生成器的种子
func init() {
	rand.Seed(time.Now().UnixNano())
}

func main() {
	nums := []int{3, 5, 6, 3, 4, 5, 1, 6, 9, 0, 5}
	quickSort(nums, 0, len(nums)-1)
	fmt.Println(nums)
}
func quickSort(nums []int, l, r int) {
	if l < r {
		// 	随机选取一个数与最右侧的元素交换位置
		i := rand.Intn(r-l) + l
		nums[i], nums[r] = nums[r], nums[i]
		left, right := partition(nums, l, r)
		quickSort(nums, l, left-1)
		quickSort(nums, right, r)
	}
}
func partition(nums []int, l, r int) (int, int) {
	i := l
	right := r
	for ; i < right; i++ {
		if nums[i] < nums[r] {
			nums[l], nums[i] = nums[i], nums[l]
			l++
		} else if nums[i] > nums[r] {
			right--
			nums[i], nums[right] = nums[right], nums[i]
			i--
		}
	}
	nums[i], nums[right] = nums[right], nums[i]
	return i, right
}