用go写一段插入排序

好的，以下是Go语言实现的插入排序代码：

package main

import "fmt"

func insertSort(nums []int) []int {
    for i := 1; i < len(nums); i++ {
        value := nums[i]
        j := i - 1
        for j >= 0 && nums[j] > value {
            nums[j+1] = nums[j]
            j--
        }
        nums[j+1] = value
    }
    return nums
}

func main() {
    nums := []int{3, 2, 4, 1, 5}
    fmt.Println(insertSort(nums))
}

以上代码将实现一个排序算法，它可以对一个整型切片进行排序，并返回排序后的结果。

相关问题

桶排序 基数排序 go代码

### 关于桶排序和基数排序的Go语言实现

#### 桶排序 (Bucket Sort)

桶排序是一种分配排序算法，工作原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用不同的排序算法或是以递归方式继续使用桶排序）。这种分割的结果是一个非常快速有效的排序方法。

package main

import (
	"fmt"
	"math"
)

func bucketSort(slice []float64) {
	if len(slice) == 0 {
		return
	}

	minValue := slice[0]
	maxValue := slice[0]

	for _, value := range slice { // 找出最大最小值
		if value < minValue {
			minValue = value
		} else if value > maxValue {
			maxValue = value
		}
	}

	bucketCount := int(math.Floor(maxValue - minValue)) + 1
	buckets := make([][]float64, bucketCount)

	for _, value := range slice { // 将元素放入对应的桶中
		index := int(math.Floor(value - minValue))
		buckets[index] = append(buckets[index], value)
	}

	result := make([]float64, 0, len(slice))

	for _, bucket := range buckets { // 对每一个桶中的元素进行排序并合并结果
		if len(bucket) != 0 {
			insertionSort(bucket)
			result = append(result, bucket...)
		}
	}

	copy(slice, result)
}

// 插入排序用于对各个桶内元素排序
func insertionSort(nums []float64) {
	for i := 1; i < len(nums); i++ {
		key := nums[i]
		j := i - 1
		for j >= 0 && nums[j] > key {
			nums[j+1] = nums[j]
			j--
		}
		nums[j+1] = key
	}
}

func main() {
	slice := []float64{0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}
	fmt.Println("Original Slice:", slice)
	bucketSort(slice)
	fmt.Println("Sorted Slice :", slice)
}

此代码实现了浮点数类型的桶排序[^1]。

#### 基数排序 (Radix Sort)

基数排序基于这样的想法：通过比较数字的不同位上的数值来进行排序；它可以从最低有效位(LSD)开始或最高有效位(MSD)，这里展示的是LSD版本。

package main

import "fmt"

const base = 10

func countingSortByDigit(array []int, exp int) {
	n := len(array)
	output := make([]int, n)
	count := make([]int, base)

	for i := 0; i < n; i++ {
		index := (array[i] / exp) % base
		count[index]++
	}

	for i := 1; i < base; i++ {
		count[i] += count[i-1]
	}

	for i := n - 1; i >= 0; i-- {
		index := (array[i] / exp) % base
		output[count[index]-1] = array[i]
		count[index]--
	}

	for i := range output {
		array[i] = output[i]
	}
}

func radixSort(array []int) {
	maxElement := getMax(array)

	exp := 1
	for maxElement/exp > 0 {
		countingSortByDigit(array, exp)
		exp *= base
	}
}

func getMax(array []int) int {
	max := array[0]
	for _, element := range array {
		if element > max {
			max = element
		}
	}
	return max
}

func main() {
	arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
	fmt.Printf("Unsorted Array: %v\n", arr)
	radixSort(arr)
	fmt.Printf("Sorted Array:   %v\n", arr)
}

这段程序展示了如何利用计数排序作为子过程来完成整型数据的基数排序。

介绍几个排序算法以及对应的python、java、go的代码实现

### 排序算法介绍及代码实现

#### 选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

**Python实现：**

def selectSort(a):
    lens = len(a)
    for i in range(lens - 1):
        mina = i
        for j in range(i + 1, lens):
            if a[mina] > a[j]:
                mina = j
        a[i], a[mina] = a[mina], a[i]
    return a

**Go实现：**

func selectSort(a []int) []int {
    lens := len(a)
    for i := 0; i < lens; i++ {
        mina := i
        for j := i + 1; j < lens; j++ {
            if a[mina] > a[j] {
                mina = j
            }
        }
        a[i], a[mina] = a[mina], a[i]
    }
    return a
}

#### 插入排序（Insertion Sort）

插入排序的工作方式像玩扑克牌时整理手中的牌。它将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的适当位置。

**Python实现：**

def insertSort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and key < a[j]:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

**Go实现：**

func insertSort(a []int) []int {
    for i := 1; i < len(a); i++ {
        key := a[i]
        j := i - 1
        for j >= 0 && key < a[j] {
            a[j+1] = a[j]
            j--
        }
        a[j+1] = key
    }
    return a
}

#### 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

**Python实现：**

def bubbleSort(a):
    n = len(a)
    for i in range(n):
        for j in range(0, n-i-1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
    return a

**Go实现：**

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

#### 归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

**Python实现：**

def mergeSort(a):
    if len(a) > 1:
        mid = len(a) // 2
        L = a[:mid]
        R = a[mid:]

        mergeSort(L)
        mergeSort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                a[k] = L[i]
                i += 1
            else:
                a[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            a[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            a[k] = R[j]
            j += 1
            k += 1

    return a

**Go实现：**

func mergeSort(a []int) []int {
    if len(a) > 1 {
        mid := len(a) / 2
        L := a[:mid]
        R := a[mid:]

        mergeSort(L)
        mergeSort(R)

        i := j := k := 0
        for i < len(L) && j < len(R) {
            if L[i] < R[j] {
                a[k] = L[i]
                i++
            } else {
                a[k] = R[j]
                j++
            }
            k++
        }
        for i < len(L) {
            a[k] = L[i]
            i++
            k++
        }
        for j < len(R) {
            a[k] = R[j]
            j++
            k++
        }
    }
    return a
}

#### 快速排序（Quick Sort）

快速排序通过一个划分操作将数据分为独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再递归地对这两部分数据分别进行快速排序，以达到整个序列有序。

**Python实现：**

def quickSort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    left = [x for x in a if x < pivot]
    middle = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quickSort(left) + middle + quickSort(right)

**Go实现：**

func quickSort(a []int) []int {
    if len(a) <= 1 {
        return a
    }
    pivot := a[len(a)/2]
    left := []int{}
    middle := []int{}
    right := []int{}
    for _, v := range a {
        if v < pivot {
            left = append(left, v)
        } else if v == pivot {
            middle = append(middle, v)
        } else {
            right = append(right, v)
        }
    }
    return append(append(quickSort(left), middle...), quickSort(right)...)
}