每日一排序回顾
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
}
评论区