反思

那天从百度面完自知面试结果不是很好，毕竟作为一个开发对于算法实在不该忘记的如此彻底，并且在我看来，程序员千千万，区分程序员好坏与专业性来说，算法真的占了很大一部分，而自己毕业以来彻底荒废了算法，一直在工程性上想要有所突破，或许我想，工程性一直没有比较满意突破的原因可能就在于自己对于算法的荒废吧。哎。。。

回忆

简单回忆了一下，当初对于算法的学习主要得益于三本书《算法导论》，《算法：C语言实现》，《编程珠玑》，其中前两本由于错误的学习方式既只看书不写代码只是理解记忆了算法的思想和一些基本理论，比如说，空间与时间的互换，以及排序最快的极限是nlogn，同时由于排序优化的根本思想是在于减少重复比较的次数，冒泡排序之所以慢就是因为其为暴力比较的方式，而快排之所以快是因为每一次递归都是左侧元素一定比基准数要小，右侧一定比基准数要大，左侧与右侧数据不需要在比较了，同样的归并排序，堆排序也是一样的道理，并且由于排序是要确保每个元素在自己正确的位置上，当时《算法导论》当中经过推理是看到了最终的nlogn的结果，现在已经推算不出来了。。。尴尬。

相应的和排序类似，查找一定是在排好序的前提下能最快找到元素，最快的查找一定是数组或者字典，时间复杂度为O(1)，但是这种数据结构又会造成空间的浪费（空间换时间）。

在编程珠玑当中更多的说的是程序性能和算法的关系，例如：

递归由于利用了堆栈，所以递归的调用次数是有限制的，过多的递归会导致超出最大可用堆栈大小
递归由于发生了函数调用其性能是不如迭代的（当时测试性能应该是要慢三分之一）
递归是可以转化成迭代的

目前来说，能记起的也就这些了 : (

结合到现在算法相关的职位薪水都奇高无比，真是严重怀疑自己当初选择的方向是不是正确啊，🤣

光说不练

不能光说不练，这里特意实现一遍，由于C已经好久不用了，以下实现使用go

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
		package main

		import (
			"fmt"
			"self-lib/algs"
			)
		func shift(arr []int,i,j int){
		fmt.Printf("shift:[%d][%d]\n",arr[i],arr[j])
		m := arr[j]
		for ii := j-1;ii >= i;ii --{
			arr[ii + 1] = arr[ii]
		}
		arr[i] = m
			fmt.Println(arr)
		}


func insert(arr []int){
al := len(arr)
		for i := 0;i < al; i++{
j := i
	   for j > 0{
		   if arr[j] < arr[i]{
			   break
		   }
		   j--
	   }
   if arr[j] < arr[i]{
	   j++
   }
   shift(arr,j,i)
		}
}

func main(){
length := 15
			arr := algs.RandList(length,15)
			fmt.Printf("ori:%v\n",arr)
			insert(arr)
			fmt.Printf("sorted:%v\n",arr)
}

快排

package main


import (
		"fmt"
		"self-lib/algs"
		"os"
		"strconv"
	   )

func swap(arr []int,i,j int){
	arr[i],arr[j] = arr[j],arr[i]
}
func quicksort(arr []int,si,ei int){
	//fmt.Printf("Start:%d,End:%d\n",si,ei)
	if si >= ei{
		return
	}
i := si
	   j := ei - 2
	   m := arr[ei - 1]
	   for i < j {
		   for arr[i] < m{
			   i++
		   }
		   for arr[j] > m && j > i{
			   j--
		   }
		   if i < j{
			   swap(arr,i,j)
				   i++
				   j--
		   }
	   }
   if arr[i] < m{
	   i++
   }
   swap(arr,i,ei-1)
	   quicksort(arr,si,i)
	   quicksort(arr,i+1,ei)
}
func main(){
	length,_ := strconv.Atoi(os.Args[1])
		arr := algs.RandList(length,20)
		fmt.Printf("ori:%v\n",arr)
		quicksort(arr,0,length)
		fmt.Printf("sorted:%v\n",arr)
}

对于快排来说，每一次调用都会将基准元素的位置最终确认，之后同样的步骤处理左侧元素以及右侧元素，快排之所以快就在于此，不会重复比较基准元素左侧与右侧元素的大小，当然也有例外情况，就是极端情况下，元素是逆序拍列的：）

二分查找

func binary_search(arr []int,n int) int{
start := 0
		   end := len(arr) - 1
		   for start <= end {
mid := (start + end) / 2
		 m := arr[mid]
		 if m > n{
			 end = mid - 1
		 }else if m < n{
			 start = mid + 1
		 }else if m == n{//已经找到这里了，那么就是向左找或者向右找到所有
			 fmt.Printf("Found:%d\n",mid)
				 return mid
		 }
		   }
	   return -1
}

二分查找虽然快，但是他有一个前提是需要在已经排好序的元素序列上进行查找，其查找次数最多为logn次

以上就是对于排序以及查找的回忆

当时百度还有对于最大公约数以及最小公倍数的编程实现，哎，表示这个题在《C和指针》课后题也是做过的，然而当时也是想不起来了，哭死，后面要把这个也实现一下

转载请注明来源链接 http://just4fun.im/2017/11/20/一些算法复习/ 尊重知识,谢谢:)