常见的排序算法

package main

import "fmt"

// BubbleSort implements the bubble sort algorithm
func BubbleSort(arr []int) {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		for j := 0; j < n-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

func main() {
	arr := []int{5, 2, 9, 1, 5, 6}
	BubbleSort(arr)
	fmt.Println("Sorted array:", arr)
}

package main

import "fmt"

// SelectionSort implements the selection sort algorithm
func SelectionSort(arr []int) {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		minIdx := i
		for j := i + 1; j < n; j++ {
			if arr[j] < arr[minIdx] {
				minIdx = j
			}
		}
		arr[i], arr[minIdx] = arr[minIdx], arr[i]
	}
}

func main() {
	arr := []int{29, 10, 14, 37, 14}
	SelectionSort(arr)
	fmt.Println("Sorted array:", arr)
}

package main

import "fmt"

// InsertionSort implements the insertion sort algorithm
func InsertionSort(arr []int) {
	n := len(arr)
	for i := 1; i < n; i++ {
		key := arr[i]
		j := i - 1
		for j >= 0 && arr[j] > key {
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = key
	}
}

func main() {
	arr := []int{12, 11, 13, 5, 6}
	InsertionSort(arr)
	fmt.Println("Sorted array:", arr)
}

package main

import "fmt"

// MergeSort implements the merge sort algorithm
func MergeSort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	mid := len(arr) / 2
	left := MergeSort(arr[:mid])
	right := MergeSort(arr[mid:])
	return merge(left, right)
}

func merge(left, right []int) []int {
	result := []int{}
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] < right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}
	result = append(result, left[i:]...)
	result = append(result, right[j:]...)
	return result
}

func main() {
	arr := []int{12, 11, 13, 5, 6, 7}
	sortedArr := MergeSort(arr)
	fmt.Println("Sorted array:", sortedArr)
}

package main

import "fmt"

// QuickSort implements the quick sort algorithm
func QuickSort(arr []int) {
	if len(arr) < 2 {
		return
	}
	left, right := 0, len(arr)-1
	pivot := arr[len(arr)/2]
	for left <= right {
		for arr[left] < pivot {
			left++
		}
		for arr[right] > pivot {
			right--
		}
		if left <= right {
			arr[left], arr[right] = arr[right], arr[left]
			left++
			right--
		}
	}
	QuickSort(arr[:right+1])
	QuickSort(arr[left:])
}

func main() {
	arr := []int{10, 7, 8, 9, 1, 5}
	QuickSort(arr)
	fmt.Println("Sorted array:", arr)
}

package main

import "fmt"

// HeapSort implements the heap sort algorithm
func HeapSort(arr []int) {
	n := len(arr)
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, n, i)
	}
	for i := n - 1; i >= 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		heapify(arr, i, 0)
	}
}

func heapify(arr []int, n, i int) {
	largest := i
	left := 2*i + 1
	right := 2*i + 2

	if left < n && arr[left] > arr[largest] {
		largest = left
	}

	if right < n && arr[right] > arr[largest] {
		largest = right
	}

	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)
	}
}

func main() {
	arr := []int{12, 11, 13, 5, 6, 7}
	HeapSort(arr)
	fmt.Println("Sorted array:", arr)
}

package main

import "fmt"

// CountingSort implements the counting sort algorithm
func CountingSort(arr []int, max int) []int {
	count := make([]int, max+1)
	for _, num := range arr {
		count[num]++
	}
	idx := 0
	for num, c := range count {
		for c > 0 {
			arr[idx] = num
			idx++
			c--
		}
	}
	return arr
}

func main() {
	arr := []int{4, 2, 2, 8, 3, 3, 1}
	sortedArr := CountingSort(arr, 8)
	fmt.Println("Sorted array:", sortedArr)
}

package main

import (
	"fmt"
	"sort"
)

// BucketSort implements the bucket sort algorithm
func BucketSort(arr []int, bucketSize int) []int {
	if len(arr) == 0 {
		return arr
	}

	// Determine minimum and maximum values
	minValue := arr[0]
	maxValue := arr[0]
	for _, num := range arr {
		if num < minValue {
			minValue = num
		} else if num > maxValue {
			maxValue = num
		}
	}

	// Initialize buckets
	bucketCount := (maxValue-minValue)/bucketSize + 1
	buckets := make([][]int, bucketCount)

	// Distribute input array values into buckets
	for _, num := range arr {
		bucketIndex := (num - minValue) / bucketSize
		buckets[bucketIndex] = append(buckets[bucketIndex], num)
	}

	// Sort individual buckets and concatenate them
	sortedArr := []int{}
	for _, bucket := range buckets {
		sort.Ints(bucket)
		sortedArr = append(sortedArr, bucket...)
	}

	return sortedArr
}

func main() {
	arr := []int{42, 32, 33, 52, 37, 47, 51}
	sortedArr := BucketSort(arr, 5)
	fmt.Println("Sorted array:", sortedArr)
}