几个简单的排序算法

排序

快速排序

package main

import "fmt"

func quickSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	pivot := arr[len(arr)/2]
	var less, equal, greater []int

	for _, value := range arr {
		switch {
		case value < pivot:
			less = append(less, value)
		case value == pivot:
			equal = append(equal, value)
		case value > pivot:
			greater = append(greater, value)
		}
	}

	// 递归排序小于和大于基准值的子数组
	return append(append(quickSort(less), equal...), quickSort(greater)...)
}

func main() {
	arr := []int{64, 34, 25, 12, 22, 11, 90}

	fmt.Println("Unsorted array:", arr)

	arr = quickSort(arr)

	fmt.Println("Sorted array:", arr)
}

冒泡排序

package main

import "fmt"

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{64, 34, 25, 12, 22, 11, 90}
	
	fmt.Println("Unsorted array:", arr)

	bubbleSort(arr)

	fmt.Println("Sorted array:", arr)
}

二分查找

package main

import "fmt"

func binarySearch(arr []int, target int) int {
	low, high := 0, len(arr)-1

	for low <= high {
		mid := low + (high-low)/2

		if arr[mid] == target {
			return mid // 找到目标值，返回索引
		} else if arr[mid] < target {
			low = mid + 1 // 目标值在右半部分
		} else {
			high = mid - 1 // 目标值在左半部分
		}
	}

	return -1 // 目标值不存在
}

func main() {
	arr := []int{11, 12, 22, 25, 34, 64, 90}
	target := 25

	index := binarySearch(arr, target)

	if index != -1 {
		fmt.Printf("Target %d found at index %d\n", target, index)
	} else {
		fmt.Printf("Target %d not found in the array\n", target)
	}
}