轻松掌握编程基本算法（一）

2023-03-01

int mid max

笔者好长时间没有更新博客了，一个原因是开发的项目所用到的技术都是老技术点，所接触到的知识都是行业逻辑流程，所以只是自己做了总结并没有拿上来分享。另外一个原因是目前笔者在重新学习C++语言以及计算机的一些基本知识（算法等）。下面的代码为C++代码，好了直接进入正题编程基本算法（一）编程基本算法（二）编

笔者好长时间没有更新博客了，一个原因是开发的项目所用到的技术都是老技术点，所接触到的知识都是行业逻辑流程，所以只是自己做了总结并没有拿上来分享。另外一个原因是目前笔者在重新学习C++语言以及计算机的一些基本知识（算法等）。

下面的代码为C++代码，好了直接进入正题

编程基本算法（一）

编程基本算法（二）

编程基本算法（三）

折半查找

又称二分查找。

使用条件：有序集合。

算法思想：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或者不找到为止。

关键点在于比较中间位置所记录的关键字和给定值的比较，如果比给定值大（这里假设集合从小到大排列）那么可以缩小区间范围（集合开始-->中间位置的上一位），在比较该区间的中间位置所记录的关键字与给定值，依次循环到找到或者找不到位置。

举例编程：这里有一个整数数据 int a[10]={1,5,10,13,17,23,65,77,81,93};

（1）这是递归(感谢园友zdd指出这里判断条件的错误，应该改为if(min>max)

//折半查找 
//数组必须按照一定的顺序 
//参数：***，最小，目标（参数类型为整数） 
int BinarySearch(int min,int max,int num) 
{ 
if(min==max)return-1; 
int mid=(min+max)/2; 
if(a[mid]==num)return mid; 
elseif(a[mid]<num) 
{ 
return BinarySearch(mid+1,max,num); 
} 
else 
{ 
return BinarySearch(min,mid-1,num); 
} 
} 

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

（2）非递归

//非递归算法 
int BinarySearch_F(int num) 
{ 
int min=0; 
int max=9; 
int mid; 
while(min<=max) 
{ 
mid=(min+max)/2; 
if(a[mid]==num)return mid; 
elseif(a[mid]>num)max=mid-1; 
else min=mid+1; 
} 
return-1; 
} 

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

性能分析：时间复杂度O(logn)

插入排序

使用条件：可对比大小的集合。

算法思想：将一个记录插入到已排好序的有序列中，从而得到一个新的，记录数增1的有序序列。待插记录依次比较已经排好序列，如果序列数大于该待插记录，那么该序列往后挪一位，直到找到序列小于待插记录，那么此时插入到该序列的后一个位置，依次上面操作，直至插完位置。

举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}将其排序

//插入排序 
//这里temp是哨兵位 
//从小到大 
void InsertSort() { 
 int temp; 
 int j; 
 for(int i=1;i<10;i++) { 
 temp=b[i]; 
 for(j=i-1;j>=0;j--) { 
 if(b[j]>temp) { 
 b[j+1]=b[j]; 
 } 
 else { 
 break; 
 } 
 } 
 b[j+1]=temp; 
 } 
 cout<<"the sort is:"; 
 for(int i=0;i<10;i++) { 
 cout<<b[i]<<""; 
 } 
 cout<<endl; 
 } 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.

性能分析：时间复杂度O（n^2)

折半插入排序

使用条件：可对比大小的集合。

算法思想：基本思想与简单插入排序思想相似，唯一的不同点在于找出插入的位置，简单插入排序用的是依次比较，这里折半插入排序改进了，将依次查找改进成折半查找

举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}将其排序

void BinaryInsertSort() { 
 int temp,min,max,mid; int j; 
 for(int i=1;i<10;i++) {  
min=0;max=i-1; 
 temp=b[i]; 
 while(min<=max) { 
 mid=(min+max)/2; 
 if(b[mid]>temp) { 
 max=mid-1; } 
 else { min=mid+1; 
 } 
 } 
 for(j=i-1;j>=max+1;j--) { 
 b[j+1]=b[j]; 
 } 
 b[max+1]=temp; 
 } 
 cout<<"the sort is:"; 
 for(int i=0;i<10;i++) { 
 cout<<b[i]<<""; 
 } 
 cout<<endl; 
 } 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.