写在前面

今天在写leetcode算法题6316. 重排数组以得到最大前缀分数的时候，总是超时，最后看别人的解答，发现思路是差不多的，先排序，然后遍历求和。

仔细看别人的代码，排序使用的是python语言自带的sort函数。唯一的区别是排序算法，我使用的是快速选择排序。众所周知快速选择排序的时间复杂度永远是O(n*n)，因此欢迎是排序算法导致耗时。准备改成快速排序。

快速排序算法有一段时间没有写了，参考这或许是东半球讲十大排序算法最好的一篇文章,其实这篇文章里面写的快速排序算法是有问题，最后通过在网上查找其他快速排序算法思想，让我想起了快速排序的思路，于是自己写，很快就写出来的。

快速排序代码

func FastSort(data []int) []int {
	fastSort(data, 0, len(data)-1)
	return data
}

func fastSort(data []int, begin, end int) {
	if begin >= end {
		return
	}
	mid := findMid(data, begin, end)
	fastSort(data, begin, mid-1)
	fastSort(data, mid+1, end)
}

func findMid(data []int, begin, end int) int {
	if begin >= end {
		return end
	}

	i, j := begin, end
	for i < j {
		for j > i && data[j] > data[i] {
			j--
		}
		if j == i {
			break
		}
		data[i], data[j] = data[j], data[i]
		i++

		for i < j && data[i] < data[j] {
			i++
		}
		if i == j {
			break
		}
		data[i], data[j] = data[j], data[i]
		j--
	}
	return i
}

题目代码

func MaxScore(nums []int) int {
	nums = FastSort(nums)
	sum := 0
	count := 0
	for i := len(nums) - 1; i >= 0; i-- {
		if i == len(nums)-1 {
			if nums[i] == 0 {
				break
			}
		}
		sum += nums[i]
		if sum > 0 {
			count += 1
		}
		if sum == 0 {
			break
		}
	}
	return count
}

结果：程序通过

源代码：https://github.com/ZBIGBEAR/sort/blob/master/memery_sort/swap_sort/fast_sort.go