21

Golang 排序算法实现 - ZZIR's Blog

 4 years ago
source link: https://zzir.cn/2019/golang-sort.html?
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Golang 排序算法实现

Mar 24, 2019

O(N^2) 基于比较的排序算法

  • 冒泡排序 BUB
  • 选择排序 SEL
  • 插入排序 INS

基于比较的排序算法比较数组的元素并决定是否交换它们。这三种排序算法最容易实现，但不是最高效的，因为它们的时间复杂度是O(N^2)。

O(NlogN) 基于比较的排序算法

  • 希尔排序 SHE
  • 并归排序 MER
  • 快速排序 QUI
    • 随机快速排序 R-Q

这些排序算法通常以递归方式实现，使用分而治之的思想解决问题。

O(N) 不基于比较的排序算法

  • 计数排序 COU
  • 桶排序 BUC
  • 基数排序 RAD

复杂度和稳定性

算法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度复 稳定性
冒泡排序 O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) O(n)O(n)O(n) O(1)O(1)O(1) 稳定
选择排序 O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) O(1)O(1)O(1) 不稳定
插入排序 O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) O(n)O(n)O(n) O(1)O(1)O(1) 稳定
堆排序 O(nlog2n)O(nlog_{2}n)O(nlog2​n) O(nlog2n)O(nlog_{2}n)O(nlog2​n) O(nlog2n)O(nlog_{2}n)O(nlog2​n) O(1)O(1)O(1) 不稳定
希尔排序 O(n1.3)O(n^{1.3})O(n1.3) O(n2)O(n^2)O(n2) O(n)O(n)O(n) O(1)O(1)O(1) 不稳定
并归排序 O(nlog2n)O(nlog_{2}n)O(nlog2​n) O(nlog2n)O(nlog_{2}n)O(nlog2​n) O(nlog2n)O(nlog_{2}n)O(nlog2​n) O(1)O(1)O(1) 稳定
快速排序 O(nlog2n)O(nlog_{2}n)O(nlog2​n) O(n2)O(n^2)O(n2) O(nlog2n)O(nlog_{2}n)O(nlog2​n) O(nlog2n)O(nlog_{2}n)O(nlog2​n) 不稳定
计数排序 O(n+k)O(n+k)O(n+k) O(n+k)O(n+k)O(n+k) O(n+k)O(n+k)O(n+k) O(n+k)O(n+k)O(n+k) 稳定
桶排序 O(n+k)O(n+k)O(n+k) O(n2)O(n^2)O(n2) O(n)O(n)O(n) O(n+k)O(n+k)O(n+k) 稳定
基数排序 O(n∗k)O(n*k)O(n∗k) O(n∗k)O(n*k)O(n∗k) O(n∗k)O(n*k)O(n∗k) O(n+k)O(n+k)O(n+k) 稳定

冒泡排序 Bubble Sort

算法的核心在于每次通过两两比较交换位置，选出剩余无序序列里最大(小)的数据元素放到队尾。

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

选择排序 Selection Sort

算法核心在于线性搜索数列并找到最大(小)值，并将最大(小)值替换为列中左端的数字并进行排序。

func SelectionSort(data []int) {
	length := len(data)
	for i := 0; i < length; i++ {
		maxIndex := 0
		for j := 1; j < length-i; j++ {
			if data[j] > data[maxIndex] {
				maxIndex = j
			}
		}
		data[length-i-1], data[maxIndex] = data[maxIndex], data[length-i-1]
	}
}

堆排序 Heap Sort

堆排序是指利用堆这种数据结构所设计的一种排序算法。

func HeapSort(data []int) []int {
	heapify(data)
	for i := len(data) - 1; i > 0; i-- {
		data[0], data[i] = data[i], data[0]
		siftDown(data, 0, i)
	}
	return data
}

func heapify(data []int) {
	for i := (len(data) - 1) / 2; i >= 0; i-- {
		siftDown(data, i, len(data))
	}
}

func siftDown(heap []int, lo, hi int) {
	root := lo
	for {
		child := root*2 + 1
		if child >= hi {
			break
		}
		if child+1 < hi && heap[child] < heap[child+1] {
			child++
		}
		if heap[root] < heap[child] {
			heap[root], heap[child] = heap[child], heap[root]
			root = child
		} else {
			break
		}

	}
}

插入排序 Insertion Sort

插入排序的原理是，从第二个数开始向右侧遍历，每次均把该位置的元素移动至左侧，放在放在一个正确的位置(比左侧大，比右侧小)。

func InsertionSort(data []int) {
	for i := 1; i < len(data); i++ {
		if data[i] < data[i-1] {
			j := i - 1
			temp := data[i]
			for j >= 0 && data[j] > temp {
				data[j+1] = data[j]
				j--
			}
			data[j+1] = temp
		}
	}
}

希尔排序 Shell Sort

1959 年 Shell 发明，第一个突破 O(n^2) 的排序算法，是简单插入排序的改进版。

它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

func ShellSort(data []int) {
	n := len(data)
	h := 1
	for h < n/3 {
		h = 3*h + 1
	}
	for h >= 1 {
		for i := h; i < n; i++ {
			for j := i; j >= h && data[j] < data[j-h]; j -= h {
				data[j], data[j-h] = data[j-h], data[j]
			}
		}
		h /= 3
	}
}

并归排序 Merge Sort

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

func MergeSort(data []int) []int {
	if len(data) <= 1 {
		return data
	}
	middle := len(data) / 2
	left := MergeSort(data[:middle])
	right := MergeSort(data[middle:])

	return merge(left, right)
}
func merge(left, right []int) []int {
	result := make([]int, len(left)+len(right))
	for i := 0; len(left) > 0 || len(right) > 0; i++ {
		if len(left) > 0 && len(right) > 0 {
			if left[0] < right[0] {
				result[i] = left[0]
				left = left[1:]
			} else {
				result[i] = right[0]
				right = right[1:]
			}
		} else if len(left) > 0 {
			result[i] = left[0]
			left = left[1:]
		} else if len(right) > 0 {
			result[i] = right[0]
			right = right[1:]
		}
	}
	return result
}

快速排序 Quick Sort

快速排序的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

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

func recursionSort(data []int, left int, right int) {
	if left < right {
		pivot := partition(data, left, right)
		recursionSort(data, left, pivot-1)
		recursionSort(data, pivot+1, right)
	}
}

func partition(data []int, left int, right int) int {
	for left < right {
		for left < right && data[left] <= data[right] {
			right--
		}
		if left < right {
			data[left], data[right] = data[right], data[left]
			left++
		}

		for left < right && data[left] <= data[right] {
			left++
		}
		if left < right {
			data[left], data[right] = data[right], data[left]
			right--
		}
	}
	return left
}

随机快速排序 Random Quick Sort

func RandomQuickSort(list []int, start, end int) {
	if end-start > 1 {
		mid := randomPartition(list, start, end)
		RandomQuickSort(list, start, mid)
		RandomQuickSort(list, mid+1, end)
	}
}

func randomPartition(list []int, begin, end int) int {
	rand.Seed(time.Now().UnixNano())
	i := begin + rand.Intn(end-begin)
	list[i], list[begin] = list[begin], list[i]
	return partition(list, begin, end)
}

func partition(list []int, begin, end int) (i int) {
	cValue := list[begin]
	i = begin
	for j := i + 1; j < end; j++ {
		if list[j] < cValue {
			i++
			list[j], list[i] = list[i], list[j]
		}
	}
	list[i], list[begin] = list[begin], list[i]
	return i
}

计数排序 Counting Sort

func CountingSort(data []int, maxValue int) []int {
	bucketLen := maxValue + 1
	bucket := make([]int, bucketLen)

	sortedIndex := 0
	length := len(data)

	for i := 0; i < length; i++ {
		bucket[data[i]] += 1
	}

	for j := 0; j < bucketLen; j++ {
		for bucket[j] > 0 {
			data[sortedIndex] = j
			sortedIndex += 1
			bucket[j] -= 1
		}
	}
	return data
}

桶排序 Bucket Sort

桶排序是计数排序的升级版。


func insertionSort(data []int) {
	for i := 0; i < len(data); i++ {
		temp := data[i]
		j := i - 1
		for ; j >= 0 && data[j] > temp; j-- {
			data[j+1] = data[j]
		}
		data[j+1] = temp
	}
}

func BucketSort(data []int, bucketSize int) []int {
	var max, min int
	for _, n := range data {
		if n < min {
			min = n
		}
		if n > max {
			max = n
		}
	}
	nBuckets := int(max-min)/bucketSize + 1
	buckets := make([][]int, nBuckets)
	for i := 0; i < nBuckets; i++ {
		buckets[i] = make([]int, 0)
	}

	for _, n := range data {
		idx := int(n-min) / bucketSize
		buckets[idx] = append(buckets[idx], n)
	}

	sorted := make([]int, 0)
	for _, bucket := range buckets {
		if len(bucket) > 0 {
			insertionSort(bucket)
			sorted = append(sorted, bucket...)
		}
	}

	return sorted
}

基数排序 Radix Sort

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

func findLargestNum(data []int) int {
	largestNum := 0

	for i := 0; i < len(data); i++ {
		if data[i] > largestNum {
			largestNum = data[i]
		}
	}
	return largestNum
}

func RadixSort(data []int) {

	largestNum := findLargestNum(data)
	size := len(data)
	significantDigit := 1
	semiSorted := make([]int, size, size)

	for largestNum/significantDigit > 0 {
		bucket := [10]int{0}

		for i := 0; i < size; i++ {
			bucket[(data[i]/significantDigit)%10]++
		}

		for i := 1; i < 10; i++ {
			bucket[i] += bucket[i-1]
		}

		for i := size - 1; i >= 0; i-- {
			bucket[(data[i]/significantDigit)%10]--
			semiSorted[bucket[(data[i]/significantDigit)%10]] = data[i]
		}

		for i := 0; i < size; i++ {
			data[i] = semiSorted[i]
		}

		significantDigit *= 10
	}
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK