欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

GO 语言常用排序

程序员文章站 2022-03-21 17:17:41
1. 冒泡排序(bubble sort)的基本思想:比较相邻两个 元素的关键字值,如果反序,则交换 2. 快速排序 快速排序(quick sort)是一种分区交换排序算法. 它的基本思想:在数据序列中选择一个值作为比较的基准值, 每趟从数据序列的两端开始交替进行,将小于基准值的元素交换到序列前端,将 ......

1. 冒泡排序(bubble sort)的基本思想:比较相邻两个 元素的关键字值,如果反序,则交换

func bubblesort(arr []int) {
	flag := false
	//外层控制行
	for i := 0; i < len(arr)-1; i++ {
		//内层控制列
		for j := 0; j < len(arr)-1-i; j++  {
			//比较两个相邻元素
			if arr[j] > arr[j+1] {
				//交换数据
				arr[j], arr[j+1] = arr[j+1], arr[j]
				flag = true
			}
		}
		//判断数据是否是有序
		if !flag {
			return
		} else {
			flag = false
		}
	}
}

 2. 快速排序

快速排序(quick sort)是一种分区交换排序算法.

它的基本思想:在数据序列中选择一个值作为比较的基准值, 每趟从数据序列的两端开始交替进行,将小于基准值的元素交换到序列前端,将大于基准值的元素交换到序列后端, 介于两者之间的位置则成为基准值的最终位置。

func quicksort(arr []int, left int, right int) {
	//设置基准值
	temp := arr[left]
	index := left

	i := left
	j := right

	for i <= j {
		//从右面找到比基准值小的数据
		for j >= index && arr[j] >= temp {
			j--
		}
		//获取基准值合适下标
		if j > index {
			arr[index] = arr[j]
			index = j
		}
		//从左面找比基准值大的数据
		for i <= index && arr[i] <= temp {
			i++
		}
		//获取基准值合适下标
		if i <= index {
			arr[index] = arr[i]
			index = i
		}
	}
	//将基准值放在合适位置
	arr[index] = temp

	//递归调用 分步处理数据
	if index-left > 1 {
		quicksort(arr, left, index-1)
	}
	if right-index > 1 {
		quicksort(arr, index+1, right)
	}

}

3. 直接选择排序

直接选择排序(straight select sort)的基本思想:第一趟从n个元素的数据序列中选出关键字最小(或最大)的元素并放到最前(或最后)位置,下一趟再从n-1个元素中选出最小(大)的元素并放到次前(后)位置,以此类推,经过n-1趟完成排序。

func selectsort(arr []int) {

	//外层控制行
	for i := 0; i < len(arr); i++ {
		//记录最大值下标
		index := 0
		//内层控制列
		//遍历数据 查找最大值
		for j := 1; j < len(arr)-i; j++ {
			if arr[j] > arr[index] {
				//记录下标
				index = j
			}
		}

		//交换数据
		arr[index], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[index]
	}
}

4.堆排序

堆排序(heap sort)是完全二叉树的应用,它的基本思想:将数据序列“堆”成树状,每趟只遍历树中的一条路径。

//初始化堆
func heapinit(arr []int) {

	//将切片转成二叉树模型  实现大根堆
	length := len(arr)
	for i := length/2 - 1; i >= 0; i-- {
		heapsort(arr, i, length-1)
	}

	//根节点存储最大值
	for i := length - 1; i > 0; i-- {
		//如果只剩下根节点和跟节点下的左子节点
		if i == 1 && arr[0] <= arr[i] {
			break
		}
		//将根节点和叶子节点数据交换
		arr[0], arr[i] = arr[i], arr[0]
		heapsort(arr, 0, i-1)
	}

}

//获取堆中最大值  放在根节点
func heapsort(arr []int, startnode int, maxnode int) {

	//最大值放在根节点
	var max int
	//定义做左子节点和右子节点
	lchild := startnode*2 + 1
	rchild := lchild + 1
	//子节点超过比较范围 跳出递归
	if lchild >= maxnode {
		return
	}
	//左右比较  找到最大值
	if rchild <= maxnode && arr[rchild] > arr[lchild] {
		max = rchild
	} else {
		max = lchild
	}

	//和跟节点比较
	if arr[max] <= arr[startnode] {
		return
	}

	//交换数据
	arr[startnode], arr[max] = arr[max], arr[startnode]
	//递归进行下次比较
	heapsort(arr, max, maxnode)
}

5. 插入排序

func insertsort(arr []int) {
	for i := 1; i < len(arr); i++ {
		//如果当前数据小于有序数据
		if arr[i] < arr[i-1] {
			j := i - 1
			//获取有效数据
			temp := arr[i]
			//一次比较有序数据
			for j >= 0 && arr[j] > temp {
				arr[j+1] = arr[j]
				j--
			}
			arr[j+1] = temp
		}
	}
}

 6. 希尔排序

希尔排序(shell sort)又称缩小增量排序,它的基本思想:分组的直接插入排序。

func shellsort(arr []int) {
	//根据增量(len(arr)/2)每次变成上一次的1/2
	for inc := len(arr) / 2; inc > 0; inc /= 2 {

		for i := inc; i < len(arr); i++ {
			temp := arr[i]

			//根据增量从数据到0进行比较
			for j := i - inc; j >= 0; j -= inc {
				//满足条件交换数据
				if temp < arr[j] {
					arr[j], arr[j+inc] = arr[j+inc], arr[j]
				} else {
					break
				}
			}
		}
	}
}

 7. 二分查找 binarysearch(数据,元素) 返回值为下标

package main

import "fmt"

func binarysearch(arr []int, num int) int {
	//定义起始下标
	start := 0
	//定义结束下标
	end := len(arr) - 1
	//中间基准值
	mid := (start + end) / 2

	for i := 0; i < len(arr); i++ {
		//基准值为查找值
		if num == arr[mid] {
			return mid
		} else if num > arr[mid] {
			//比基准值大  查找右侧
			start = mid + 1
		} else {
			//比基准值小  查找左侧
			end = mid - 1
		}
		//再次设置中间基准值位置
		mid = (start + end) / 2
	}
	return -1
}
func main() {
	//前提必须是 "有序数据"
	arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	num := 666

	index := binarysearch(arr, num)
	fmt.println(index)
}

 8. 变相排序

变相排序  基于大量重复 在某一个范围内

func main02() {
	//随机数种子
	rand.seed(time.now().unixnano())
	s := make([]int, 0)

	for i := 0; i < 10000; i++ {
		s = append(s, rand.intn(1000)) //0-999
	}
	fmt.println(s)

	//统计数据集合中数据出现的次数
	m := make(map[int]int)
	for i := 0; i < len(s); i++ {
		m[s[i]]++
	}
	//fmt.println(m)

	//排序
	for i := 0; i < 1000; i++ {
		for j := 0; j < m[i]; j++ {
			fmt.print(i, " ")
		}
	}

}