912.M 排序数组

Problem: 912. 排序数组

思路

思路1：堆排序

思路2：归并排序

思路3：快速排序

Code

代码1：

func sortArray(nums []int) []int {
	if len(nums) < 1 {
		return nums
	}

	for i := len(nums) / 2 - 1; i >= 0; i-- {
		maxHeapify(nums, i, len(nums))
	}

	for i := len(nums) - 1; i > 0; i-- {
		nums[0], nums[i] = nums[i], nums[0]
		maxHeapify(nums, 0, i)
	}

	return nums
}

func maxHeapify(nums []int, root int, size int) {
	l := 2*root + 1
	r := 2*root + 2
	largest := root
	if l < size && nums[l] > nums[largest] {
		largest = l
	}

	if r < size && nums[r] > nums[largest] {
		largest = r
	}

	if largest != root {
		nums[root], nums[largest] = nums[largest], nums[root]
		maxHeapify(nums, largest, size)
	}
}

代码2：

func sortArray(nums []int) []int {
	return mergeSort(nums)
}

func mergeSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}

	mid := len(nums) / 2
	left := mergeSort(nums[:mid])
	right := mergeSort(nums[mid:])
	return merge(left, right)
}

func merge(left []int, right []int) []int {
	i, j := 0, 0
	ans := make([]int, 0, len(left)+len(right))
	for i < len(left) && j < len(right) {
		if left[i] < right[j] {
			ans = append(ans, left[i])
			i++
		} else {
			ans = append(ans, right[j])
			j++
		}
	}

	if i < len(left) {
		ans = append(ans, left[i:]...)
	}

	if j < len(right) {
		ans = append(ans, right[j:]...)
	}

	return ans
}

代码3：

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

func quickSort(nums []int, left int, right int) {
	if left >= right {
		return
	}

	i, j := left, right
	pivot := nums[(i+j)/2] //必须这样把Pivot固定下来，不可在下面的循环根据下标取值
	for i <= j {
		for i <= j && nums[i] < pivot {
			i++
		}

		for i <= j && nums[j] > pivot {
			j--
		}

		if i <= j {
			nums[i], nums[j] = nums[j], nums[i]
			i++
			j--
		}
	}

	quickSort(nums, left, j)
	quickSort(nums, i, right)
}