侧边栏壁纸
博主头像
SeaDream乄造梦

Dream,Don't stop a day of hard and don't give up a little hope。 ——不停止一日努力&&不放弃一点希望。

  • 累计撰写 39 篇文章
  • 累计创建 20 个标签
  • 累计收到 13 条评论

目 录CONTENT

文章目录

【每日一算】来来一起来

SeaDream乄造梦
2024-01-10 / 0 评论 / 0 点赞 / 328 阅读 / 2,082 字
温馨提示:
亲爱的,如果觉得博主很有趣就留下你的足迹,并收藏下链接在走叭

每日一排序回顾

package ten_sort

/*
博客地址:
https://www.cnblogs.com/onepixel/articles/7674659.html
*/

/**
1.冒泡排序
原理:比较相邻的元素。如果第一个比第二个大,就交换他们两个。
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:稳定
*/

func BubbleSort(arr []int) []int {
	for i := 0; i < len(arr); i++ {
		for j := i + 1; j < len(arr); j++ {
			if arr[i] > arr[j] {
				arr[i], arr[j] = arr[j], arr[i]
			}
		}
	}
	return arr
}

/**
2.选择排序
原理:每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:不稳定
*/

func SelectionSort(arr []int) []int {
	for i := 0; i < len(arr); i++ {
		minLoc := i
		for j := i + 1; j < len(arr); j++ {
			if arr[i] > arr[j] {
				minLoc = j
			}
		}
		arr[i], arr[minLoc] = arr[minLoc], arr[i]
	}
	return arr
}

/**
3.插入排序
原理:对于未排序数据从第一个依次遍历,在已排序序列中从后向前扫描,找到相应位置并插入。
步骤:3.1 从第一个元素开始,该元素可以认为已经被排序;
	 3.2 取出下一个元素,在已经排序的元素序列中从后向前扫描;
	 3.3 如果该元素(已排序)大于新元素,将该元素移到下一位置;
	 3.4 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
	 3.5 将新元素插入到该位置后;
	 3.6 重复步骤2~5。
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:稳定
*/

func InsertionSort(arr []int) []int {
	for i := 0; i < len(arr); i++ {
		preIndex := i - 1
		current := arr[i]
		for preIndex >= 0 && arr[preIndex] > current {
			arr[preIndex+1] = arr[preIndex]
			preIndex--
		}
		arr[preIndex+1] = current
	}
	return arr
}

/**
4.希尔排序
原理:希尔排序是插入排序的一种更高效的改进版本,希尔排序是非稳定排序算法。
步骤:4.1 选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
	 4.2 按增量序列个数 k,对序列进行 k 趟排序;
	 4.3 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。
	 仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
时间复杂度:O(n^1.3)
空间复杂度:O(1)
稳定性:不稳定
*/

func ShellSort(arr []int) []int {
	for gap := len(arr) / 2; gap > 0; gap /= 2 {
		for i := gap; i < len(arr); i++ {
			preIndex := i - gap
			current := arr[i]
			for preIndex >= 0 && arr[preIndex] > current {
				arr[preIndex+gap] = arr[preIndex]
				preIndex -= gap
			}
			arr[preIndex+gap] = current
		}
	}
	return arr
}

每日一leetcode

/**
题库地址:https://leetcode.cn/studyplan/top-interview-150/
*/

/*
题序:88
题目:合并两个有序数组
地址:https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150
*/
func merge(nums1 []int, m int, nums2 []int, n int) []int {
	nums1 = append(nums1[:m], nums2...)
	sort.Ints(nums1)
	return nums1
}

/*
题序:118
题目:杨辉三角
地址:https://leetcode-cn.com/problems/pascals-triangle/
*/
func generate(numRows int) [][]int {
	var res [][]int
	for i := 0; i < numRows; i++ {
		var row []int
		for j := 0; j <= i; j++ {
			if j == 0 || j == i {
				row = append(row, 1)
			} else {
				row = append(row, res[i-1][j-1]+res[i-1][j])
			}
		}
		res = append(res, row)
	}
	return res
}
0

评论区