关于筛选法求素数，选择法对一串数字进行排序，折半查找法查找数字

1.关于筛选法求素数

算法描述：原理很简单，就是当i是质(素)数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质数的倍数筛掉。

如图：

代码描述l:（查找100以内的素数）

#include <stdio.h>
#include <stdlib.h>
int SiftPrime(int n)
{
int i,j;
    int *p = (int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
  p[i]=1;
  p[0]=p[1]=0;
  for(i=2;i<n;i++)
  {
   for(j=i+1;j<n;j++)
    if(j%i==0)
    {
     p[j]=0;
    }
  }
}
for(i=0;i<n;i++)
{
  if(p[i]!=0)
   printf("%-4d",i);
}
return 0;
}
int main()
{
SiftPrime(100);
return 0;
}

2. 选择法对一串数字进行排序

算法描述：

选择法排序指每次选择所要排序的数组中的最大值（由小到大排序则选择最小值）的数组元素，将这个数组元素的值与最前面没有进行排序的数组元素的值互换。以数字9、6、15、4、2为例，采用选择法实现数字按从小到大进行排序，每次交换的顺序如下图所示

关于筛选法求素数，选择法对一串数字进行排序，折半查找法查找数字

代码描述：（用选择法对1,9,2,4,3,6,10进行排序）

void SelectSort(int *arr,int len)
{
int min;
int tmp;
for(int i = 0;i < len;i++)
{
  min = i;
  for(int j = i+1;j < len;j++)
  {
   if(arr[min] > arr[j])
   {
    min = j;
   }
  }
  if(min != i)
  {
   tmp = arr[i];
   arr[i] = arr[min];
   arr[min] = tmp;
  }
}
}
int main()
{
int arr[]={1,9,2,4,3,6,10};
int len = sizeof(arr)/sizeof(arr[0]);
SelectSort(arr,len);
Show(arr,len);
return 0;
}

3.折半查找法查找数组元素

算法描述：

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

代码描述：

int BinSearch(int *arr,int len,int key)
{
int low = 0;
int high = len-1;
int mid;
while(low <= high)
{
  mid = (low+high)/2;
  if(arr[mid] == key)
  {
   return mid;
  }
  else if(arr[mid] < key)//在右边找
  {
   low = mid+1;
  }
  else
  {
   high = mid-1;
  }
}
return -1;
}

int main()
{
int arr[] = {1,2,3,5,7,9,10};
int len = sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<len;i++)
{
  printf("%d\n",BinSearch(arr,len,arr[i]));
}
printf("%d\n",BinSearch(arr,len,0));
printf("%d\n",BinSearch(arr,len,7));
printf("%d\n",BinSearch(arr,len,13));
}

关于筛选法求素数，选择法对一串数字进行排序，折半查找法查找数字

相关推荐