go 8个常用排序测试（冒泡排序,插入排序,选择排序,希尔排序,堆排序,基数排序,快速排序,计数排序）

前两天在做项目的时候，用到了排序，在网上查阅了一些资料做了部分对比，所以对常用的排序做了一些对比。当然不是全部，例如归并排序，二叉树之类的。等以后有时间可以了解一下。下面我们就了解一下这些排序；

首先，我们先生成100位随机数字，然后对这一组数字进行排序。

package main

import (
	"fmt"
	"math"
	mathRand "math/rand"
	"time"
)
func main() {
// 生成随机数
	mathRand.Seed(time.Now().UnixNano())
	var arr [100]int
	// 不重复生成
	for i := 0; i < 100; i++ {
		arr[i] = mathRand.Intn(100)
	loop:
		for k := 0; k < i; k++ {
			if arr[k] == arr[i] {
				arr[i] = mathRand.Intn(100)
				goto loop
			}
		}
	}
	//打印随机数据
	fmt.Println("生成的随机数切片：\n", arr)
}

1、冒泡排序

// 冒泡排序方法
func mpArr(data [100]int) [100]int {
	var arrx int
	for i := 0; i < len(data)-1; i++ {
		for j := 0; j < len(data)-i-1; j++ {
			arrx++
			if data[j] > data[j+1] {
				//交换
				data[j], data[j+1] = data[j+1], data[j]
			}
		}
	}
	fmt.Println("冒泡排序排序次数", arrx)
	return data
}

mpArr := mpArr(arr)
fmt.Println("冒泡排序之后的切片", mpArr)

我们可以看到冒泡排序是比较稳定的。

2、插入排序

// 插入排序
func insertSort(data [100]int) [100]int {
	var j int
	var pxNum int
	for i := 1; i < len(data); i++ {
		temp := data[i]
		for j = i; j > 0 && temp < data[j-1]; j-- {
			data[j] = data[j-1]
			pxNum++
		}
		data[j] = temp
	}
	fmt.Println("改进版插入排序次数：", pxNum)
	return data
}

// 改进版插入排序
func InsertionSort2(arr [100]int) [100]int {
	n := len(arr)
	var pxNum int
	for i := 1; i < n; i++ { // 无序区
		tmp := arr[i]
		left, right := 0, i-1
		for left <= right {
			pxNum++
			mid := (left + right) / 2
			if arr[mid] > tmp {
				right = mid - 1
			} else {
				left = mid + 1
			}
		}
		j := i - 1
		for ; j >= left; j-- { // 有序区
			arr[j+1] = arr[j]
			pxNum++
		}
		arr[left] = tmp
	}
	fmt.Println("插入排序次数：", pxNum)
	return arr
}

// 使用插入排序
cr2Arr := InsertionSort2(arr)
fmt.Println("插入排序之后的切片", cr2Arr)

// 使用改进版插入排序
crArr := insertSort(arr)
fmt.Println("改进版插入排序之后的切片", crArr)

我们可以看到插入排序也是比较稳定的。

3、选择排序

// 选择排序
func SelectionSort(arr [100]int) [100]int {
	var pxNum int
	n := len(arr)
	for i := 0; i < n-1; i++ {
		minNumIndex := i // 无序区第一个
		for j := i + 1; j < n; j++ {
			if arr[j] < arr[minNumIndex] {
				minNumIndex = j
				pxNum++
			}

		}
		arr[i], arr[minNumIndex] = arr[minNumIndex], arr[i]
	}
	fmt.Println("选择排序次数：", pxNum)
	return arr
}

// 使用选择排序
xzArr := SelectionSort(arr)
fmt.Println("选择排序之后的切片", xzArr)

由此可以看出，选择排序是不稳定的

4、希尔排序

// 希尔排序
func shellSort(data [100]int) [100]int {
	var j int
	var pxNum int
	for h := len(data) / 2; h > 0; h /= 2 {
		//外层循环控制步长
		for i := h; i < len(data); i++ {
			//内层循环是对步长个子切片做插入排序
			temp := data[i]
			for j = i; j >= h && temp < data[j-h]; j -= h {
				data[j] = data[j-h]
				pxNum++
			}
			data[j] = temp
		}
	}
	fmt.Println("希尔排序次数：", pxNum)
	return data
}

xrArr := shellSort(arr)
fmt.Println("希尔排序之后的切片", xrArr)

希尔排序也是不稳定的

5、堆排序

// 堆排序
func heapSort(data [100]int) [100]int {
	m := len(data)
	var pxNum int
	s := m / 2
	for i := s; i >= 0; i-- {
		heap(data, i, m-1)
	}
	for i := m - 1; i > 0; i-- {
		data[i], data[0] = data[0], data[i]
		heap(data, 0, i-1)
		pxNum++
	}
	fmt.Println("堆排序次数：", pxNum)
	return data
}

dArr := heapSort(arr)
fmt.Println("堆排序之后的切片", dArr)

堆排序也是不稳定的

6、基数排序

// 基数排序
func RadixSort(arr [100]int) [100]int {
	var pxNum int
	maxn := maxBitNum(arr)      // arr最大位数
	dev := 1                    // 除数，保证商最后一位是我们想要的
	mod := 10                   // 模，取商的最后一位
	for i := 0; i < maxn; i++ { // 进行maxn次排序
		bucket := make([][]int, 10) // 定义10个空桶
		result := make([]int, 0)    // 存储中间结果
		for _, v := range arr {
			n := v / dev % mod // 取出对应位的值，放入对应桶中
			bucket[n] = append(bucket[n], v)
			pxNum++
		}
		dev *= 10
		// 按顺序存入中间切片
		for j := 0; j < 10; j++ {
			result = append(result, bucket[j]...)
			pxNum++
		}
		// 转存到原切片（结果）
		for k := range arr {
			arr[k] = result[k]
			pxNum++
		}
	}
	fmt.Println("基数排序次数：", pxNum)
	return arr
}

zsArr := RadixSort(arr)
fmt.Println("基数排序之后的切片", zsArr)

基数排序是稳定的。

7、快速排序

// 快速排序
func QuickSort(left int, right int, array *[100]int) {
	l := left
	r := right
	// pivot 是中轴， 支点
	pivot := array[(left+right)/2]
	temp := 0
	// for 循环的目标是将比 pivot 小的数放到左边，比 pivot 大的数放到右边
	for l < r {
		// 从 pivot 的左边找到大于等于pivot的值
		for array[l] < pivot {
			l++
		}
		// 从 pivot 的右边边找到小于等于pivot的值
		for array[r] > pivot {
			r--
		}
		// 1 >= r 表明本次分解任务完成, break
		if l >= r {
			break
		}
		// 交换
		temp = array[l]
		array[l] = array[r]
		array[r] = temp
		// 优化
		if array[l] == pivot {
			r--
		}
		if array[r] == pivot {
			l++
		}
	}
	// 如果  1== r, 再移动下
	if l == r {
		l++
		r--
	}
	// 向左递归
	if left < r {
		QuickSort(left, r, array)
	}
	// 向右递归
	if right > l {
		QuickSort(l, right, array)
	}
}

ksArr := arr
QuickSort(0, len(ksArr)-1, &ksArr)
fmt.Println("快速排序之后的切片", ksArr)

快排也是不稳定的。

8、计数排序

// 计数排序
func CountingSort(arr [100]int) [100]int {
	var pxNum int
	length := len(arr)
	maxValue := getMaxValue(arr)
	bucketLen := maxValue + 1
	bucket := make([]int, bucketLen)
	sortedIndex := 0
	// 统计每个元素出现的个数
	for i := 0; i < length; i++ {
		bucket[arr[i]] += 1
		pxNum++
	}
	// 按照统计结果写入arr
	for j := 0; j < length; j++ {
		for bucket[j] > 0 {
			pxNum++
			arr[sortedIndex] = j // bucket[j]的值是统计结果，后面会变化，j是真正值
			sortedIndex++
			bucket[j]--
		}
	}
	fmt.Println("计数排序次数：", pxNum)
	return arr
}
jsArr := CountingSort(arr)
fmt.Println("计数排序之后的切片", jsArr)

计数排序也是稳定的

稳定的排序算法有：冒泡排序、插入排序、计数排序、基数排序。

不稳定的排序算法有：选择排序、希尔排序、快速排序、堆排序。

当然每个排序方法只有最适合的场景，不能单从稳定性考虑，也要从性能上考虑，不能一概而论。