《算法导论》打卡1，主要内容：插入排序，分治法，归并排序
第一部分 基础知识
第一章 算法在计算中的作用
1.1 算法
算法就是任何良定义的计算过程，该过程取某个值或值的集合作为输入并产生某个值或者值的集合作为输出。规范书写：问题：XXXX输入：XXXXXXXX输出：XXXXXXXX算法步骤：1.XXXXXXXXXXX2.XXXXXXXXXXX
注意问题与问题实例的区别。
1.2 作为一种技术的算法
考虑效率：时间与空间资源的消耗第二章 算法基础
2.1 插入排序
输入：n个数的一个序列<a1,a2,...,an>输出：输入序列的一个排列<a1’,a2’,...,an’>，满足a1’≤a2’≤...≤an’
算法：
#include<iostream>using namespace std;void insertionsort(int *A,int length){//插入排序int key; //暂存当前位置的值int i;for(int j=1;j<length;j++){key = A[j]; //暂存当前位置的值i= j-1;while(i>=0 && A[i]>key){ //如果前面的值比key大，则交换A[i+1]=A[i];i=i-1;}A[i+1]=key;}}int main(){int A[9]={9,3,4,2,6,7,5,1,8}; //举了个栗子int length=sizeof(A)/sizeof(A[0]); //求数组的长度的一种方法insertionsort(A,length);//输出排序后的序列for(int i=0;i<length;i++){cout<<A[i]<<" ";}return 0;}
伪代码👇
2.2 分析算法
时间复杂度：最好的情况下：O(n),最坏的情况下：O(n²),平均情况下：O(n²)2.3 设计算法
2.3.1 分治法
分治法：将原问题分解为几个规模较小但类似于原问题的子问题，递归求解这些子问题，然后再合并这些子问题的解来建立原问题的解归并排序：#include <iostream>using namespace std;void merge(int arr[],int left,int mid,int right){int aux[right-left+1];//开辟一个新的数组，将原数组映射进去for(int m=left;m<=right;m++){aux[m-left]=arr[m];}int i=left,j=mid+1;//i和j分别指向两个子数组开头部分for(int k=left;k<=right;k++){if(i>mid)//右边还有剩余{arr[k]=aux[j-left];j++;}else if(j>right)//左边还有剩余{arr[k]=aux[i-left];i++;}else if(aux[i-left]<aux[j-left])//左边小于右边{arr[k]=aux[i-left];i++;}else//右边小于左边{arr[k]=aux[j-left];j++;}}}//递归的使用归并排序，对arr[l....right]排序void merge_sort(int arr[],int left,int right){if(left >=right)return ;int mid=(left+right)/2;merge_sort(arr,left,mid);merge_sort(arr,mid+1,right);merge(arr,left,mid,right);}void my_merge_sort(int arr[],int n){merge_sort(arr,0,n-1);}int main(){//举个栗子int a[6];for(int i=0;i<6;i++){cin>>a[i];}my_merge_sort(a,6);for(int i=0;i<6;i++){cout<<a[i]<<" ";}return 0;}
