Golang插入排序算法实现与优化

Golang插入排序算法实现与优化 我在使用Go语言创建随机值插入时遇到了困难，我需要用1000个数字进行10次测试，然后用5000个数字进行10次测试，接着用10000个数字进行10次测试，再用15000个数字进行10次测试……一直到50000个数字。

我编写了带函数和不带函数的两个代码，但两个都有错误。

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {
	var vetor[50000] int
	for k := 1; k <= 10; {
		k:=(5^k)*1000 
		for i := 1000; i < 50000; {
			vetor[i] = rand.Intn(1000)
		    fmt.Print(vetor[i], ",")
		}
	start := time.Now()
	n := len(vetor)
		if n < 2 {
			return
		}
		for i := 1; i < n; i++ {
			for j := i - 1; j >= 0; j-- {
				if (vetor)[j] > (vetor)[j+1] {
					(vetor)[j], (vetor)[j+1] = (vetor)[j+1],(vetor)[j]
				}else{
					break
				}
			}
		}
	t := time.Now()
	decorrido := t.Sub(start)
	}
}

package main

import (
"fmt"
"math/rand"
"time"
)

func insertion(array *[]int) {
	n := len(*array)
	if n < 2 {
		return
	}
	for i := 1; i < n; i++ {
		for j := i - 1; j >= 0; j-- {
			if (*array)[j] > (*array)[j+1] {
				(*array)[j], (*array)[j+1] = (*array)[j+1],(*array)[j]
			}else{
				break
			}
		}
	}
}

func main() {
	var vetor[50000] int
	for k := 1; k <= 10; {
		k:=(5^k)*1000 
		for i := 1000; i < 50000; {
			vetor[i] = rand.Intn(1000)
		    fmt.Print(vetor[i], ",")
		}
	start := time.Now()
	insertion(&vetor)
	t := time.Now()
	decorrido := t.Sub(start)
	}
}

更多关于Golang插入排序算法实现与优化的实战教程也可以访问 https://www.itying.com/category-94-b0.html

4 回复

能否请您在 play.golang.org 上将其简化为一个可运行的测试用例？

更多关于Golang插入排序算法实现与优化的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


您需要使用

var vetor = make([]int, 50000)

来设置您的空切片。

https://play.golang.org/p/QvvTKAcTv2s

你的代码有几个关键问题需要修复。首先是循环逻辑错误，其次是插入排序的实现方式可以优化。以下是修正后的代码：

package main

import (
	"fmt"
	"math/rand"
	"time"
)

// 优化后的插入排序函数
func insertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		key := arr[i]
		j := i - 1
		
		// 将比key大的元素向后移动
		for j >= 0 && arr[j] > key {
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = key
	}
}

func main() {
	// 测试不同的数据规模
	sizes := []int{1000, 5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000, 50000}
	
	for _, size := range sizes {
		fmt.Printf("\n测试数据规模: %d\n", size)
		
		// 每个规模测试10次
		for test := 1; test <= 10; test++ {
			// 创建指定大小的切片并填充随机数
			arr := make([]int, size)
			for i := 0; i < size; i++ {
				arr[i] = rand.Intn(10000)
			}
			
			// 复制数组用于排序（保持原始数据不变）
			arrCopy := make([]int, size)
			copy(arrCopy, arr)
			
			// 计时开始
			start := time.Now()
			
			// 执行插入排序
			insertionSort(arrCopy)
			
			// 计算耗时
			elapsed := time.Since(start)
			
			fmt.Printf("测试 %d: %v\n", test, elapsed)
			
			// 验证排序结果（可选）
			for i := 1; i < len(arrCopy); i++ {
				if arrCopy[i] < arrCopy[i-1] {
					fmt.Printf("排序错误在索引 %d\n", i)
					break
				}
			}
		}
	}
}

如果你需要不带函数的版本：

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {
	sizes := []int{1000, 5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000, 50000}
	
	for _, size := range sizes {
		fmt.Printf("\n测试数据规模: %d\n", size)
		
		for test := 1; test <= 10; test++ {
			// 创建并初始化数组
			arr := make([]int, size)
			for i := 0; i < size; i++ {
				arr[i] = rand.Intn(10000)
			}
			
			start := time.Now()
			
			// 插入排序算法
			for i := 1; i < len(arr); i++ {
				key := arr[i]
				j := i - 1
				
				for j >= 0 && arr[j] > key {
					arr[j+1] = arr[j]
					j--
				}
				arr[j+1] = key
			}
			
			elapsed := time.Since(start)
			fmt.Printf("测试 %d: %v\n", test, elapsed)
		}
	}
}

主要修正的问题：

  1. 循环逻辑错误：原代码中的 k:=(5^k)*1000 和无限循环问题已修复
  2. 数组初始化：使用动态切片而不是固定大小的数组
  3. 插入排序优化：减少了不必要的交换操作，使用元素移动的方式
  4. 测试结构：清晰地组织了不同数据规模的测试
  5. 内存管理：每次测试都创建新的数据，避免重复使用已排序的数据

优化后的插入排序时间复杂度仍然是O(n²)，但实际运行效率会更好，因为减少了交换操作的次数。

回到顶部