数据结构和算法

数据结构和算法
数据结构和算法
wmg
发布日期:   2021-12-15
文章字数:   2.4k
阅读次数:  

数据结构和算法

冒泡排序

func main() {
	var array = [...]int{24,69,80,57,13,34,1,9,56,90,44,11,16,78,99,4}
	fmt.Println("排序前 array=",array)
	BubbleSort(array[:])
	fmt.Println("冒泡排序后 array=",array)
}

// BubbleSort 冒泡排序
func BubbleSort(arr []int)  {
	for j := 0; j< len(arr)-1 ; j++ {
		for i := 0; i< len(arr) -1 - j ; i++ {
			if arr[i] > arr[i+1] {
				temp := arr[i]
				arr[i] = arr[i+1]
				arr[i+1] =temp
			}
		}
	}
}

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。时间复杂度：O(n^2)

func main() {
	arr := [...]int{10,34,98,9,56,23,87,4,20}

	fmt.Println("排序前数组arr=",arr)
	SelectSort(arr[:])
	fmt.Println("选择排序后数组arr=",arr)

}

func SelectSort(arr []int)  {

	for j := 0; j < len(arr)-1;j++{
		min := arr[j]
		minIndex := j
		for i := 1+j ; i < len(arr);i++{
			if min > arr[i] {
				min = arr[i]
				minIndex = i
			}
		}
		if minIndex != j {
			arr[j],arr[minIndex] = arr[minIndex],arr[j]
		}
	}
}

插入排序

插入排序(InsertionSort)，一般也被称为直接插入排序。

对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。

插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)。

func main() {
	arr := [...]int{10,34,98,9,56,23,87,4,20}

	fmt.Println("排序前数组arr=",arr)
	InsertionSort (arr[:])
	fmt.Println("插入排序后数组arr=",arr)

}

func InsertionSort (arr []int)  {
	for i := 0; i < len(arr); i++ {
		// 寻找元素 arr[i] 合适的插入位置
		for j := i; j >0 ; j-- {
			if arr[j]<arr[j-1] {
				arr[j],arr[j-1] = arr[j-1],arr[j]
			}else {
				break
			}
		}
	}

}

二分查找

// BinaryFind 对有序数组进行二分查找
func BinaryFind(in int,arr []int,leftIndex int,rightIndex int ) int {

	middle := (leftIndex+rightIndex)/2

	if leftIndex > rightIndex {
		return -1
	}

	if arr[middle] > in {
		//查找范围  leftIndex  -  middle-1
		return BinaryFind(in,arr,leftIndex,middle-1)
	}else if arr[middle] < in {
		//查找范围  middle+1   - rightIndex
		return BinaryFind(in,arr,middle+1,rightIndex)
	}else {
		//找到了
		return middle
	}

	return -1
}

func main() {
	var array = [...]int{24,69,80,57,13,34,1,9,56,90,44,11,16,78,99,4}
	fmt.Println("排序前 array=",array)
	BubbleSort(array[:])
	fmt.Println("冒泡排序后 array=",array)
	in := 5
	findResult := BinaryFind(in, array[:], 0, len(array))
	fmt.Println("二分查找 in=",in," 数组array=",array)
	fmt.Println("二分查找结果下标为： index=",findResult)
}

稀疏数组（Sparse Array）

概念：当一个数组中大部分元素是0，或者是一个相同的值时，可以使用稀疏数组来保存该数组。稀疏数组的本质就是压缩数组

例如二维数组：

0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  56 0  0  0  0  0  0
0  23 0  0  32 0  26 0  0  0  0           
0  0  73 0  0  0  0  0  0  0  0
0  0  0  0  0  68 0  0  0  0  0
0  22 0  0  0  62 0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  78 0
0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0

对应的稀疏数组为：

行 列 值
11 11 0   // 第0行记录二维数组的：行数、列数、默认值
1  4  56
2  1  23
2  4  32
2  6  26
3  2  73
4  5  68
5  1  22
5  5  62
7  9  78

稀疏数组的处理方式是：

  1. 记录数组一共有几行几列，以及不同值的数量
  2. 把具有不同值元素的行列及其值记录在一个小规模的数组中，从而缩小数据的规模。

二维数组转稀疏数组的思路：

  1. 遍历原始的 二维数组，得到有效的数据个数sum

  2. 根据得到的有效数据个数sum就可以创建稀疏数组 

    spareseArr[sum + 1][3]

  3. 将二维数组的有效值数据存储到稀疏数组

稀疏数组转二维数组的思路：

  1. 先读取系数数组的第一行，根据第一行的数据，创建原始的二维数组，
  2. 在读取稀疏数组的后几行数据，并赋值给原始的二维数组
// ValNode 保存稀疏数组值节点结构体
type ValNode struct {
	col int  //行
	row int  //列
	val int  //值
}

func main() {
    //初始化数组
	var originalArray [11][11]int
	originalArray[1][4] = 56
	originalArray[2][1] = 23
	originalArray[2][4] = 32
	originalArray[2][6] = 26
	originalArray[3][2] = 73
	originalArray[4][5] = 68
	originalArray[5][1] = 22
	originalArray[5][5] = 62
	originalArray[7][9] = 78

	// 输出原始数组
	for _, ints := range originalArray {
		for _, v := range ints {
			fmt.Printf("%d\t",v)
		}
		fmt.Println()
	}

	var sparseArray []ValNode   //定义稀疏数组切片

	//先保存数组规模
	sparseArray = append(sparseArray,ValNode{col: 11,row: 11, val: 0})

	// 遍历原始数组，将不为0的保存到稀疏数组切片
	for i1, ints := range originalArray {
		for i2, v := range ints {
			if v != 0 {
				valNode := ValNode {i1,i2,v}
				sparseArray = append(sparseArray,valNode)
			}
		}
	}

	fmt.Println("转化后的稀疏数组为：")
	for _, node := range sparseArray {
		fmt.Println(node)
	}

	// 将稀疏数组还原为二维数组
	var restoreArray [11][11]int
	for  i,node := range sparseArray {
		if i != 0 {
			restoreArray[node.col][node.row] = node.val
		}

	}

	fmt.Println("稀疏数组还原为二维数组：")
	for _, ints := range restoreArray {
		for _, v := range ints {
			fmt.Printf("%d\t",v)
		}
		fmt.Println()
	}

}

队列（Queue）

概念：队列是一个有序列表，可以用数组或者链表来实现。队列遵循先进先出的原则

数组模拟队列：

  • 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的大小为队列的最大容量( MaxSize)。
  • 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而rear则是随着数据输人而改变
  • 将数据存入队列时，将尾指针后移：rear+1,front==real 并且要求 rear <= MaxSize -1 否则无法存入（即队列满）

使用数组实现环形队列的思路：

  1. 创建一个数组array，作为队列的一个字段，队列容量为 数组大小-1
  2. head 表示队列头部初始化为0
  3. tail 表示队列尾部，初始化为0
  4. 完成队列的基本操作：添加数据，取出数据，显示队列
  5. 实现环形队列可以将数组看作是环形的，通过取模的方式实现
  6. 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，队列满条件：（ tail +1）% maxSize == head
  7. tail = 0 head=0 tail== head 表示队列空
  8. 统计队列内元素个数：（tail +maxSize -head）% maxSize
package main

import (
	"errors"
	"fmt"
	"os"
)

type CircleQueue struct {
	maxSize int  //队列最大容量
	array []int //数组大小
	head int     //指向队列首
	tail int	 //指向队列尾
}

func InitCircleQueue(maxSize int) *CircleQueue  {
	return &CircleQueue{
		maxSize: maxSize,
		array: make([]int,maxSize+1),
		head: 0,
		tail: 0,
	}
}

// Push 往队列添加元素
func (this *CircleQueue) Push(val int) error  {

	if this.IsFull() {
		return errors.New("Queue full")
	}

	// 不会包含最后一个元素
	this.array[this.tail] = val
	this.tail = (this.tail+1) % this.maxSize
	return nil
}

// Pop 取出队列元素
func (this *CircleQueue) Pop() (val int,err error)  {

	if this.IsEmpty() {
		return -1, errors.New("Queue is Empty")
	}

	//取出元素，同时清空该元素值
	val = this.array[this.head]
	this.array[this.head] = 0
	this.head = (this.head+1) % this.maxSize
	return val,nil
}

// IsEmpty 判断环形队列是否为空
func (this *CircleQueue) IsEmpty() bool  {
	return this.head==this.tail
}

// IsFull 判断环形队列是否已满
func (this *CircleQueue) IsFull() bool  {
	return ((this.tail+1) % this.maxSize ) ==this.head
}

// Count 统计队列内元素个数
func (this *CircleQueue) Count() int  {
	return (this.tail + this.maxSize -this.head) % this.maxSize
}

// Show 显示队列所有元素
func (this *CircleQueue) Show()  {
	fmt.Println("队列内的元素个数为:",this.Count())
	for i:= 0;i<len(this.array);i++ {
		fmt.Printf("%d\t",this.array[((this.head+i+1)% this.maxSize)])
	}
	fmt.Println()
}




func main() {
	queue := InitCircleQueue(5)

	var key string
	var val int

	for  {
		fmt.Println("1. 输入add 添加元素到队列")
		fmt.Println("2. 输入get 获取队列元素")
		fmt.Println("3. 输入all 查看队列所有元素")
		fmt.Println("4. 输入exit 退出")

		fmt.Scanln(&key)
		switch key {
		case "add":
			fmt.Println("请输入添加队列的元素：")
			fmt.Scanln(&val)
			err := queue.Push(val)
			if err !=nil {
				fmt.Println(err.Error())
			}
		case "get":
			pop, err := queue.Pop()
			if err !=nil {
				fmt.Println(err.Error())
			}
			fmt.Println("出队元素：",pop)
		case "all":
			queue.Show()
		case "exit":
			os.Exit(0)
		}
	}

}
文章作者: wmg
文章链接: http://wumangeng.github.io/2021/12/15/shu-ju-jie-gou/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 wmg !
数据结构和算法
赏
  目录