【每日一算】来来一起来

每日一排序回顾

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
}