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)
计数排序也是稳定的
稳定的排序算法有:冒泡排序、插入排序、计数排序、基数排序。
不稳定的排序算法有:选择排序、希尔排序、快速排序、堆排序。
当然每个排序方法只有最适合的场景,不能单从稳定性考虑,也要从性能上考虑,不能一概而论。
还没有评论,快来发表第一个评论吧