Algorithm和Structrues
1. 哪些排序算法是稳定的
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法.
排序算法的稳定性这个应该是清晰明了的，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。
其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。
基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些。
现在我们来分析一下常见的排序算法的稳定性。
(1)冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。
所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
(2)选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n – 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。
比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
(3)插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
(4)快速排序
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j，交换a[i]和a[j],重复上面的过程，直到i > j。 交换a[j]和a[center_index]，完成一趟快速排序。
在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。
(5)归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
(6)基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
(8)堆排序
我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， … 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。
所以，堆排序不是稳定的排序算法。
因此会有: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法
2. 给定一个二叉树,判断其是否是一个有效的二叉搜索树
什么是二叉树（Binary Tree)?
每个结点至多拥有两棵子树的树结构(即二叉树中不存在度大于2的结点)。并且，二叉树的子树有左右之分，其次序不能任意颠倒。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
上面概念中提到了“度”的概念，“度”其实就是某个节点子节点的数量。如果某个节点的子节点数量为1，则该节点的度为1，如果有8个子节点，则度为8，以此类推。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
可以直接按照定义比较大小，比 root 节点小的都在左边，比 root 节点大的都在右边:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func isValidBST(root *TreeNode) bool {
return isValid(root, math.MinInt64, math.MaxInt64)
}
func isValid(root *TreeNode, min, max int) bool {
if root == nil {
return true
}
if root.Val <= min {
return false
}
if root.Val >= max {
return false
}
return isValid(root.Left, min, root.Val) && isValid(root.Right, root.Val, max)
}
3. 排序算法
排序算法又分为稳定性算法和不稳定性算法：
- 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
-
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
-
冒泡排序
func main() {
var arr = []int{9,10,11,5,3,4,27,2,1,3,20}
//升序
bubbleAscendingSort(arr)
//降序
bubbleDescendingSort(arr)
}
//升序
func bubbleAscendingSort(arr []int) {
for i :=0; i < len(arr)-1; i++ {
for j := i+1; j< len(arr); j++ {
if (arr[i] > arr[j]) {
arr[i],arr[j] = arr[j],arr[i]
}
}
}
fmt.Println("bubbleAscendingSort:",arr)
}
//降序
func bubbleDescendingSort(arr []int) {
for i :=0; i < len(arr)-1; i++ {
for j := i+1; j< len(arr); j++ {
if (arr[i] < arr[j]) {
arr[i],arr[j] = arr[j],arr[i]
}
}
}
fmt.Println("bubbleDescendingSort:",arr)
}
运行结果:
bubbleAscendingSort: [1 2 3 3 4 5 9 10 11 20 27]
bubbleDescendingSort: [27 20 11 10 9 5 4 3 3 2 1]
- 选择排序
func main() {
var arr = []int{19,28,17,5,13,4,6,7,9,3,10}
//升序
selectAscendingSort(arr)
//降序
selectDescendingSort(arr)
}
//升序
func selectAscendingSort(arr []int) {
l := len(arr)
m := len(arr) - 1
for i := 0; i < m; i++ {
k := i
for j := i+1; j < l; j++ {
if arr[k] > arr[j] {
k = j
}
}
if k != i {
arr[k],arr[i] = arr[i],arr[k]
}
}
fmt.Println("selectAscendingSort:",arr)
}
//降序
func selectDescendingSort(arr []int) {
l := len(arr)
m := len(arr) - 1
for i := 0; i < m; i++ {
k := i
for j := i+1; j < l; j++ {
if arr[k] < arr[j] {
k = j
}
}
if k != i {
arr[k],arr[i] = arr[i],arr[k]
}
}
fmt.Println("selectDescendingSort:",arr)
}
运行结果:
selectDescendingSort: [3 4 5 6 7 9 10 13 17 19 28]
selectAscendingSort: [28 19 17 13 10 9 7 6 5 4 3]
- 插入排序
func main() {
var arr = []int{19,13,27,15,3,4,26,12,1,0}
insertSort(arr)
fmt.Println("insertSort:",arr)
}
func insertSort(arr []int) {
n := len(arr)
if n < 2 {
return
}
for i := 1; i < n; i++ {
for j := i; j >0 && arr[j] < arr[j-1]; j-- {
arr[j], arr[j-1] = arr[j-1], arr[j]
}
}
}
运行结果:
insertSort: [0 1 3 4 12 13 15 19 26 27]
- 希尔排序
func main() {
var arr = []int{19,8,27,15,3,17,6,2,1,0}
shellSort(arr)
fmt.Println("shellSort:",arr)
}
func shellSort(arr []int) {
n := len(arr)
h := 1
//寻找合适的间隔h
for h < n/3 {
h = 3*h +1
}
for h >= 1 {
for i := h; i < n; i++ {
for j := i; j >= h && arr[j] < arr[j-1]; j -= h {
arr[j], arr[j-1] = arr[j-1], arr[j]
}
}
h /= 3
}
}
运行结果:
shellSort: [0 1 2 3 6 8 15 17 19 27]
- 归并排序
func main() {
array := []int{55, 94, 87, 12, 4, 32, 11,8, 39, 42, 64, 53, 70, 12, 9}
fmt.Println("before MergeSort",array)
array = MergeSort(array)
fmt.Println("after MergeSort:",array)
}
func MergeSort(array []int) []int{
n := len(array)
if n < 2 {
return array
}
key := n / 2
left := MergeSort(array[0:key])
right := MergeSort(array[key:])
return merge(left, right)
}
func merge(left []int, right []int) []int{
tmp := make([]int, 0)
i, j := 0,0
for i < len(left) && j < len(right) {
if left[i] < right[j]{
tmp = append(tmp, left[i])
i ++
}else{
tmp = append(tmp, right[j])
j ++
}
}
tmp = append(tmp, left[i:]...)
tmp = append(tmp, right[j:]...)
return tmp
}
运行结果:
before MergeSort [55 94 87 12 4 32 11 8 39 42 64 53 70 12 9]
after MergeSort: [4 8 9 11 12 12 32 39 42 53 55 64 70 87 94]
- 快速排序
func main() {
var arr = []int{19,8,16,15,23,34,6,3,1,0,2,9,7}
quickAscendingSort(arr, 0, len(arr)-1)
fmt.Println("quickAscendingSort:",arr)
quickDescendingSort(arr, 0, len(arr)-1)
fmt.Println("quickDescendingSort:",arr)
}
//升序
func quickAscendingSort(arr []int, start, end int) {
if (start < end) {
i, j := start, end
key := arr[(start + end)/2]
for i <= j {
for arr[i] < key {
i++
}
for arr[j] > key {
j--
}
if i <= j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
}
if start < j {
quickAscendingSort(arr, start, j)
}
if end > i {
quickAscendingSort(arr, i, end)
}
}
}
//降序
func quickDescendingSort(arr []int, start, end int) {
if (start < end) {
i, j := start, end
key := arr[(start + end)/2]
for i <= j {
for arr[i] > key {
i++
}
for arr[j] < key {
j--
}
if i <= j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
}
if start < j {
quickDescendingSort(arr, start, j)
}
if end > i {
quickDescendingSort(arr, i, end)
}
}
}
运行结果:
quickAscendingSort: [0 1 2 3 6 7 8 9 15 16 19 23 34]
quickDescendingSort: [34 23 19 16 15 9 8 7 6 3 2 1 0]
- 堆排序
func main() {
array := []int{52,16,37,2,3,32,12,27,19,42,29,13,37,12,9}
HeapSort(array)
fmt.Println("HeapSort:",array)
}
func HeapSort(array []int) {
m := len(array)
s := m/2
for i := s; i > -1; i-- {
heap(array, i, m-1)
}
for i := m-1; i > 0; i-- {
array[i], array[0] = array[0], array[i]
heap(array, 0, i-1)
}
}
func heap(array []int, i, end int){
l := 2*i+1
if l > end {
return
}
n := l
r := 2*i+2
if r <= end && array[r]>array[l]{
n = r
}
if array[i] > array[n]{
return
}
array[n], array[i] = array[i], array[n]
heap(array, n, end)
}
运行结果:
HeapSort: [2 3 9 12 12 13 16 19 27 29 32 37 37 42 52]
- 桶排序
func main() {
array := []int{31,16,37,2,13,32,10,27,7,42,29,18,28,12,9,}
BucketSort(array)
fmt.Println("BucketSort:",array)
}
func sortInBucket(bucket []int) {//此处实现插入排序方式，其实可以用任意其他排序方式
length := len(bucket)
if length == 1 {return}
for i := 1; i < length; i++ {
backup := bucket[i]
j := i -1;
//将选出的被排数比较后插入左边有序区
for j >= 0 && backup < bucket[j] {//注意j >= 0必须在前边，否则会数组越界
bucket[j+1] = bucket[j]//移动有序数组
j -- //反向移动下标
}
bucket[j + 1] = backup //插队插入移动后的空位
}
}
//获取数组最大值
func getMaxInArr(arr []int) int{
max := arr[0]
for i := 1; i < len(arr); i++ {
if arr[i] > max{ max = arr[i]}
}
return max
}
//桶排序
func BucketSort(arr []int) []int {
//桶数
num := len(arr)
//k（数组最大值）
max := getMaxInArr(arr)
//二维切片
buckets := make([][]int, num)
//分配入桶
index := 0
for i := 0; i < num; i++ {
index = arr[i] * (num-1) /max//分配桶index = value * (n-1) /k
buckets[index] = append(buckets[index], arr[i])
}
//桶内排序
tmpPos := 0
for i := 0; i < num; i++ {
bucketLen := len(buckets[i])
if bucketLen > 0{
sortInBucket(buckets[i])
copy(arr[tmpPos:], buckets[i])
tmpPos += bucketLen
}
}
return arr
运行结果：
BucketSort: [2 7 9 10 12 13 16 18 27 28 29 31 32 37 42]
- 计数排序
func main() {
array := []int{69,16,48,2,3,32,10,27,17,42,29,8,28,12,9,}
countingSort(array,array[0])
fmt.Println("BucketSort:",array)
}
func countingSort(arr []int, maxValue int) []int {
bucketLen := maxValue + 1
bucket := make([]int, bucketLen) // 初始为0的数组
sortedIndex := 0
length := len(arr)
for i := 0; i < length; i++ {
bucket[arr[i]] += 1
}
for j := 0; j < bucketLen; j++ {
for bucket[j] > 0 {
arr[sortedIndex] = j
sortedIndex += 1
bucket[j] -= 1
}
}
return arr
}
运行结果:
countingSort: [2 3 8 9 10 12 16 17 27 28 29 32 42 48 69]
- 基数排序
func main() {
array := []int{12, 3, 8, 5, 9, 11, 23, 36,20,28,21}
fmt.Println("before radixSort:",array)
radixSort(array)
fmt.Println("after radixSort:",array)
}
//获取数组的最大值
func maxValue(arr []int) (ret int) {
ret = 1
var key int = 10
for i := 0; i < len(arr); i++ {
for arr[i] >= key {
key = key * 10
ret++
}
}
return
}
func radixSort(arr []int) {
key := maxValue(arr)
tmp := make([]int, len(arr), len(arr))
count := new([10]int)
radix := 1
var i, j, k int
for i = 0; i < key; i++ { //进行key次排序
for j = 0; j < 10; j++ {
count[j] = 0
}
for j = 0; j < len(arr); j++ {
k = (arr[j] / radix) % 10
count[k]++
}
for j = 1; j < 10; j++ { //将tmp中的为准依次分配给每个桶
count[j] = count[j-1] + count[j]
}
for j = len(arr) - 1; j >= 0; j-- {
k = (arr[j] / radix) % 10
tmp[count[k]-1] = arr[j]
count[k]--
}
for j = 0; j <len(arr); j++ {
arr[j] = tmp[j]
}
radix = radix * 10
}
}
运行结果:
before radixSort: [12 3 8 5 9 11 23 36 20 28 21]
after radixSort: [3 5 8 9 11 12 20 21 23 28 36]
4. 如何通过递归反转单链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。
由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。
链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。
package main
import "fmt"
// 通过递归反转单链表
type Node struct {
Value int
NextNode *Node
}
func Param(node *Node){
for node !=nil{
fmt.Print(node.Value,"--->")
node = node.NextNode
}
fmt.Println()
}
func reverse(headNode *Node) *Node{
if headNode ==nil {
return headNode
}
if headNode.NextNode == nil{
return headNode
}
var newNode = reverse(headNode.NextNode)
headNode.NextNode.NextNode = headNode
headNode.NextNode = nil
return newNode
}
func main() {
var node1 = &Node{}
node1.Value = 1
node2 := new(Node)
node2.Value = 2
node3 := new(Node)
node3.Value = 3
node4 := new(Node)
node4.Value = 4
node1.NextNode = node2
node2.NextNode = node3
node3.NextNode = node4
Param(node1)
reverseNode := reverse(node1)
Param(reverseNode)
}
运行结果:
1--->2--->3--->4--->
4--->3--->2--->1--->
5. 链表和数组相比有什么优缺点
数组是一块连续的空间，声明时长度就要确定,链表是一块不连续的动态空间，长度可变,数组的优点是速度快，数据操作直接使用偏移地址， 链表需要按顺序检索节点，效率低,链表的优点是可以快速插入和删除节点，大小动态分配长度不需要固定.
链表不存在越界问题，数组有越界问题.
6. 通常一般会用到哪些数据结构
数据结构是计算机存储、组织数据的方式。对于特定的数据结构(比如数组)，有些操作效率很高(读某个数组元素)，有些操作的效率很低(删除某个数组元素)。开发者的目标是为当前的问题选择最优的数据结构。
- 数组:是最常用的数据结构了。其他数据结构，比如栈和队列都是由数组衍生出来的。
- 栈:是限定仅表尾进行插入和删除操作的线性表 。
- 队列
- 链表
- 图
- 树
- 前缀树
- 哈希表
算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法，厄米变形模型，随机森林算法。
数据对象的运算和操作：计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，成为该计算机系统的指令系统。
一个计算机的基本运算和操作有如下四类：
- 算术运算：加减乘除等运算.
- 逻辑运算：或、且、非等运算.
- 关系运算：大于、小于、等于、不等于等运算.
- 数据传输：输入、输出、赋值等运算.
