各种排序算法(Golang版本)

1.快速排序

快速排序是一种非稳定排序。

func findPivot(nums []int, left int, right int) int {
    pivot := nums[left]  // pivot的选择这里一直取第0个元素，可换成随机数
    nums[left], nums[right] = nums[right], nums[left]
    var back = left - 1
    var front = left
    for front < right {
        if nums[front] < pivot {
            back++
            nums[back], nums[front] = nums[front], nums[back]
        }
        front++
    }
    back++
    nums[right] = nums[back]
    nums[back] = pivot
    return back
}


func quickSort(nums []int, left int, right int) {
    if left >= right {
        return
    }
    for left < right {
        pivot := findPivot(nums, left, right)
    
    quickSort(nums, left, pivot-1)
    left = pivot+1
    }
    
    // quickSort(nums, pivot+1, right)
}

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

2.堆排序

堆排序是一种借助数据结构堆完成的排序。堆这种数据结构也经常用于解决topk问题。

一般从小到大排序，则使用大顶堆。从大到小排序，则使用小顶堆。

堆排序是一种不稳定排序。

func makeHeap(nums []int, root int, end int) {
    child := 2 * root + 1

    for child <= end {
        if child + 1 <= end && nums[child] < nums[child+1] {
            child = child + 1
        }

        if nums[root] >= nums[child] {
            break
        }
        nums[root], nums[child] = nums[child], nums[root]
        
        root = child
        child = 2 * root + 1

    }

}


func sortArray(nums []int) []int {
    // 构建初始堆
    for i := len(nums)/2; i >= 0; i-- {
        makeHeap(nums, i, len(nums)-1)
    }
    
    // 依次取出第一个元素，与对位元素交换。然后再次调整堆。
    var end = len(nums) - 1
    for end >= 1 {
        nums[end], nums[0] = nums[0], nums[end]
        end--
        makeHeap(nums, 0, end)
    }
    return nums
}

3.归并排序

归并排序利用分治的思维，将一个大数组的排序问题，拆成许多小数组的排序问题，然后将这些有序数组进行合并。此方法同样适合与链表排序。

归并排序是一种稳定排序。

// 合并两个有序数组
func mergeArray(nums1 []int, nums2 []int) []int {
    var retNum []int
    var ptr1 = 0
    var ptr2 = 0
    
    for ptr1 <len(nums1) || ptr2 < len(nums2) {
        var current int

        if ptr1 >= len(nums1) {
            current = nums2[ptr2]
            ptr2++
        } else if ptr2 >= len(nums2) {
            current = nums1[ptr1]
            ptr1++ 
        } else if nums1[ptr1] > nums2[ptr2] {
            current = nums2[ptr2]
            ptr2++
        } else {
            current = nums1[ptr1]
            ptr1++
        }

        retNum = append(retNum, current)
        
    }
    return retNum
}



func sortArray(nums []int) []int {
    var mergeSort func(int, int) []int 

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

        mid := left + (right - left)/2
        leftPart := mergeSort(left, mid)
        rightPart := mergeSort(mid+1, right)
        
        ret := mergeArray(leftPart, rightPart)
        return ret

    }
    nums = mergeSort(0, len(nums)-1)
    return nums
}

4.插入排序

插入排序是一种稳定排序。对于数组大部分有序的情况下使用该方法，能够快速的解决问题。

核心思想是向后遍历数组，找出每一个元素在已排序数组能够插入的位置。一旦找到，则停止并且寻找下一个元素。

func InsertSort(nums []int) {
	var i, j int
	for i = 1; i < len(nums); i++ {
		for j = i-1; j >=0 && nums[j] > nums[j+1]; j-- {
			nums[j], nums[j+1] = nums[j+1], nums[j]
		}
	}
}

5.冒泡排序

冒泡排序是一种稳定排序。每次将最大的元素往后顶，则每次循环能够完成一个元素的排序。

func bubbleSort(nums []int) {
	for i := len(nums)-1; i>0 ; i-- {
		for j := 0; j < i; j++ {
			if nums[j] > nums[j+1] {
				nums[j+1], nums[j] = nums[j], nums[j+1]
			}
		}
	}
}

6.希尔排序

希尔排序是一种不稳定排序。可以看出来希尔排序和插入排序代码是十分相似的。

func ShellSort(nums []int) {
	h := len(nums)/2
	for ; h >= 1; h/=2 {
		for i := h; i < len(nums); i++ {
			for j := i; j-h >= 0 && nums[j-h] > nums[j] ; j -= h {
				nums[j], nums[j-h] = nums[j-h], nums[j]
			}
		}
	}
}