刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/sort-an-array/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

思路

注意快排时候测试用例有坑，会有一个茫茫多一样数字的用例，导致常规快排超时
可以用增加交换频率 + 随机选择中间点的方式增加应对此类情况的效率
唔，堆排赛高？

代码

func sortArray(nums []int) []int {
	return quickSort(nums, 0, len(nums)-1)
    // return heapSort(nums)
}

func quickSort(nums []int, left, right int) []int {
	if left > right {
		return nil
	}
	i, j, pivot := left, right, rand.Intn(right-left+1)+left
	// 随机选点并增加交换频率写法，则需要在开始就进行交换，这样可以让中值位置经常移动，便于左右开弓遍历
	nums[i], nums[pivot] = nums[pivot], nums[i]
	for i < j {
		// 1、拆解常规的的严格大于才交换的条件（nums[j] >= nums[i]），增加交换频率
		for i < j && nums[j] > nums[i] {
			j--
		}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
			i++
		}
		// 2、并且让左右交替进行。两者共同作用，这样就可以让数据基本一致时，最终选取的点可以停留在数组中间位置附近
		for i < j && nums[i] < nums[j] {
			i++
		}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
			j--
		}
	}
	// 常规写法，中值位置不动，只在左右寻找时交换i、j位置，可以交替完后将中值移动到中间即可
	// nums[i], nums[left] = nums[left], nums[i]
	quickSort(nums, left, i-1)
	quickSort(nums, i+1, right)
	return nums
}

func heapSort(nums []int) []int {
	end := len(nums) - 1
	for i := end / 2; i >= 0; i-- {
		heapify(nums, i, end)
	}
	for i := end; i >= 0; i-- {
		nums[0], nums[i] = nums[i], nums[0]
		heapify(nums, 0, i-1)
	}
	return nums
}

func heapify(nums []int, root, end int) {
	left, right, largest := 2*root+1, 2*root+2, root
	if left <= end && nums[left] > nums[largest] {
		largest = left
	}
	if right <= end && nums[right] > nums[largest] {
		largest = right
	}
	if largest != root {
		nums[root], nums[largest] = nums[largest], nums[root]
		heapify(nums, largest, end)
	}
}