-
归并排序
func sortArray(nums []int) []int {
if len(nums) <= 1 {
return nums
}
partA := sortArray(nums[:len(nums)/2])
partB := sortArray(nums[len(nums)/2:])
temp := make([]int, len(partA) + len(partB))
aPointer := 0
bPointer := 0
i := 0
for aPointer < len(partA) && bPointer < len(partB) {
if partA[aPointer] < partB[bPointer] {
temp[i] = partA[aPointer]
aPointer++
} else {
temp[i] = partB[bPointer]
bPointer++
}
i++
}
for aPointer < len(partA) {
temp[i] = partA[aPointer]
aPointer++
i++
}
for bPointer < len(partB) {
temp[i] = partB[bPointer]
bPointer++
i++
}
return temp
}
-
快速排序
func sortArray(nums []int) []int {
quickSort(nums)
return nums
}
func quickSort(nums []int) {
left, right := 0, len(nums) - 1
for right > left {
// 右边部分放大于
if nums[right] > nums[0] {
right--
continue
}
// 左边部分放小于等于
if nums[left] <= nums[0] {
left++
continue
}
nums[left], nums[right] = nums[right], nums[left]
}
nums[0], nums[right] = nums[right], nums[0]
if len(nums[:right]) > 1 {
sortArray(nums[:right])
}
if len(nums[right + 1:]) > 1 {
sortArray(nums[right + 1:])
}
}
-
堆排序
func sortArray(nums []int) []int {
// 从n/2 最后一个非叶子结点起开始构建大顶堆
for i := len(nums) / 2; i >= 0; i-- {
heapSort(nums, i)
}
end := len(nums) - 1
// 每次将大顶堆的最大值与末尾进行交换,并再次排序
for end > 0 {
nums[0], nums[end] = nums[end], nums[0]
heapSort(nums[:end], 0)
end--
}
return nums
}
// 对一个非叶子结点进行排序
func heapSort(nums []int, pos int) {
end := len(nums) - 1
left := 2 * pos + 1
if left > end {
return
}
right := 2 * pos + 2
temp := left
// 先左右子结点进行比较,找出较小的那一个
if right <= end && nums[right] > nums[temp] {
temp = right
}
if nums[temp] <= nums[pos] {
return
}
nums[temp], nums[pos] = nums[pos], nums[temp]
// 如果发生了交换的话 就要继续调查后续子节点(只调查交换了的后续,不用全调查,不然会超时)
heapSort(nums, temp)
}
- 卑鄙排序
func sortArray(nums []int) []int {
sort.Ints(nums)
return nums
}
有疑问加站长微信联系(非本文作者)