归并排序

相关题目

• 912. 排序数组 (opens new window)

题解

func sortArray(nums []int) []int {
    return mergeSort(nums, 0, len(nums) - 1)
}
func mergeSort(nums []int, begin, end int) []int {
    if begin >= end {
        return nums
    }
    mid := (begin + end) /2
    mergeSort(nums, begin,mid)
    mergeSort(nums, mid + 1,end)
    merge(nums, begin,mid,end)
    return nums
}

func merge (nums []int, begin,mid,end int) {
    tmpArr := make([]int, end - begin + 1)
    i := begin
    j := mid + 1
    k := 0

    for ;i<= mid && j <= end;k++ {
        if nums[i] <= nums[j]{
            tmpArr[k] = nums[i]
            i++
        }else {
            tmpArr[k] = nums[j]
            j++
        }
    }

    for ; i<=mid;i++{
        tmpArr[k] = nums[i]
        k++
    }

    for ; j<=end;j++{
        tmpArr[k] = nums[j]
        k++
    }

    copy(nums[begin:end+1],tmpArr)
}

快速排序

相关思路链接

• 快速排序的正确理解方式及运用 (opens new window)

func sortArr(nums []int) []int {
  n := len(nums)
	if n <= 1 {
		return nums
	}
  
	return quickSort(nums, 0,n-1)
}

func quickSort(nums []int, start, end int) []int {
  if start >= end {
		return nums
	}

	i := partition(nums, start, end)
	quickSort(nums, start, i-1)
	quickSort(nums, i+1, end)

	return nums
}

func partition(nums []int, start, end int) int {
	randPivot := rand.Intn(end-start+1) + start // 随机取一个中点
	pivot := nums[randPivot]
	nums[end], nums[randPivot] = nums[randPivot], nums[end]

	i := start
	for j := start; j <= end; j++ {
		if nums[j] > pivot {
			if i != j {
				nums[i], nums[j] = nums[j], nums[i]
			}
      i++
		}
	}
	nums[i], nums[end] = nums[end], nums[i]

	return i

}