C语言常用算法及解析_c语言算法

算法主要是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么数据）、采用什么结构、使用什么语句及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。

1.选择法排序

选择排序第一次从待排序的中数据元素选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
例如：

#include <stdio.h>
 
void arr_out(int a[])
{
 
    int i = 0;
    for(i = 0;i < 10;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}
 
void arr_sort(int *p,int n)
{
    int i,j;
    int min = 0;
    for(i = 0;i < n - 1;i++)
    {
        min = i;
        for(j = i + 1;j < n;j++)
        {
            if(p[j] < p[min])
            {
                min = j;
            }
        }
        if(i != min)
        {
            int temp = p[i];
            p[i] = p[min];
            p[min] = temp;
        }  
    }
}
 
int main()
{
    int a[10] = {0};
    int i = 0;
    printf("输入10个数字为：\n");
    for(i = 0;i < 10;i++)
    {
        scanf("%d",&a[i]);
    }
    arr_sort(a,10);
    printf("输出10个选择排序数字为：\n");
    arr_out(a);
    while(1);
    return 0;
}

编译后运行输出：

输入10个数字为：
23 6 78 99 45 23 64 85 32 100
输出10个选择排序数字为：
6 23 23 32 45 64 78 85 99 100

2.冒泡法排序

冒泡排序重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来，直重复这个过程，直到没有任何两个相邻元素可以交换，就表明完成了排序。如有n个数（存放在数组a(n)中），第一趟将每相邻两个数比较，小的调到前头，经n-1次两两相邻比较后，最大的数已“沉底”，放在最后一个位置，小数上升“浮起”；第二趟对余下的n-1个数（最大的数已“沉底”）按上法比较，经n-2次两两相邻比较后得次大的数；依次类推，n个数共进行n-1趟比较，在第j趟中要进行n-i次两两比较。
例如：

#include <stdio.h>
 
#define  n  5
int a[n] = { 6,3,5,1,10 };
void swap(int *a, int *b);
void BubSort(void);
 
void swap(int *a, int *b) {
 
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
 
void BubSort(void){
 
    int i,j,b;
    for (i = 0; i < n; i++) {
        for (j = 0; j + 1 < n - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(&a[j], &a[j + 1]);
            }
        }
 
    printf("第%d轮排序：", i + 1);
        for (b = 0; b < n; b++) {
            printf("%d ", a[b]);
        }
        printf("\n");
    }
}
 
int main()
{
    BubSort();
    while(1);
    return 0;
}

编译后运行输出：

第1轮排序：3 5 1 6 10
第2轮排序：3 1 5 6 10
第3轮排序：1 3 5 6 10
第4轮排序：1 3 5 6 10
第5轮排序：1 3 5 6 10

3.合并法排序

合并排序遵循分而治之的规则，以递归方式对一组给定的数字/元素进行排序，从而减少了时间。

例如：

#include <stdio.h>
 
 void merge(int a[], int p, int q, int r)
{
    int b[5];   
    int i, j, k;
    k = 0;
    i = p;
    j = q + 1;
    while(i <= q && j <= r)
    {
        if(a[i] < a[j])
        {
            b[k++] = a[i++];    
        }
        else
        {
            b[k++] = a[j++];
        }
    }
    while(i <= q)
    {
        b[k++] = a[i++];
    }
    while(j <= r)
    {
        b[k++] = a[j++];
    }
    for(i=r; i >= p; i--)
    {
        a[i] = b[--k];
    }
}
 
 void mergeSort(int a[], int p, int r)
{
    int q;
    if(p < r)
    {
        q = (p + r) / 2;
        mergeSort(a, p, q);
        mergeSort(a, q+1, r);        
        merge(a, p, q, r);
    }
}
 
 void printArray(int a[], int size)
{
    int i;
    for (i=0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}
 
int main()
{
    int arr[] = {68, 12, 33, 3, 42};
    int len = sizeof(arr)/sizeof(arr[0]);
    printf("Given array: \n");
    printArray(arr, len);
    mergeSort(arr, 0, len - 1);
    printf("\nSorted array: \n");
    printArray(arr, len);
    while(1);
    return 0;
}

编译后运行输出：

Given array:
68 12 33 3 42
 
Sorted array:
3 12 33 42 68

4.快速排序法

快速排序是一种高效的排序算法，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个序列有序的目的。

例如：

#include <stdio.h>
 
void swap(int arr[], int low, int high)
{
    int t = arr[low];
    arr[low] = arr[high];
    arr[high] = t;
}
 
int partition(int arr[], int low, int high)
{
      int point = arr[low];
      while(low<high)
      {
          while(low<high && arr[high]>=point)
          {
                 high--;
          }  
         swap(arr,low,high);
         while(low<high && arr[low]<=point)
          {
                low++;
          }  
          swap(arr,low,high);
      }
    return low;
}
 
void quicksort(int arr[], int low, int high)  
{
    if(low<high){
        int point = partition(arr,low,high);
        quicksort(arr,low,point-1);  
        quicksort(arr,point+1,high);
    }
}
 
int main()
{
    int i;
    int arr[] = {6,51,8,1,7,13,32,78,19,26};
    int n = 10;
    quicksort(arr, 0, n-1);  
    for(i=0; i<n; i++)
    printf("%d ", arr[i]);
    while(1);
    return 0;
}

编译后运行输出：

1 6 7 8 13 19 26 32 35 51 68 78

5.直接插入排序法

直接插入排序是一种简单的排序算法，将待排序的数据元素插入到已经有序的序列中，从而得到一个新的排序。将待排序序列分为两部分，一部分有序一部分无序；第一个元素为有序序列，从第二个元素到最后为无序序列；将无序序列中每一个元素依次插入到有序序列的合适位置--从小到大（从大到小）。对于大规模数据排序时效率较低，但对于小规模数据排序是一种简单且实用的排序算法。

例如：

#include<stdio.h>
 
void Print(int arr[],int len){
int i;
for(i=0;i<len;i++){
printf("%d ",arr[i]);
}
}
 
void InsertSort(int arr[],int len){
int i,j;
for(i=1;i<len;i++){  
  int tem = arr[i];  
  for(j=i-1;tem<=arr[j]&&j>=0;j--){  
  arr[j+1] = arr[j];
  }
arr[j+1] = tem;  
}
printf("\n排序OK!\n\n");
}
 
int main(){
int arr[10] = {8,12,1,62,31,9,82,33,41,76};
int len = sizeof(arr) / sizeof(int);
printf("排序前：\n");
Print(arr,len);
InsertSort(arr,len);
printf("排序后：\n");
Print(arr,len);
while(1);
return 0;
}

编译后运行输出：

排序前：

8 12 1 62 31 9 82 33 41 76
排序OK!
 
排序后：
1 8 9 12 31 33 41 62 76 82

6.希尔排序法

希尔排序将待排序的数据元素分组，对每组进行直接插入排序，从而使得整个序列逐步变得有序。希尔排序比直接插入排序的时间复杂度要低，因此对于大规模数据排序时效率更高。希尔排序也是一种稳定的排序算法，不会改变相同元素的相对位置；因此，在需要保持相同元素相对位置的情况下，希尔排序是一种更好的选择。

例如：

#include<stdio.h>
#include <assert.h>
#include<stdlib.h>
#define MAXLEN 20
 
void initar(int *arr,int len)
{
int i;
assert(arr != NULL);
for(i = 0;i < len;i++){
arr[i] = rand() % 30;
}
}
 
void showar(int *arr,int len)
{
int i;
assert(arr != NULL);
for(i = 0;i < len;i++){
printf("%d ",arr[i]);
}
printf("\n--------------------------\n");
}
 
void Shell_sort(int *arr, int len) {
int i = 0,j = 0;
int temp = 0;
int gap = 0;
assert(arr != NULL && len >= 0);
gap = len;
while(gap > 1){
gap /= 2;
for(i = gap;i < len;i += gap){
if(arr[i] < arr[i - gap]){
temp = arr[i];
for(j = i - gap;j >= 0 && arr[j] > temp;j -= gap){
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
}
}
 
int main()
{
int arr[MAXLEN];
initar(arr,MAXLEN);
printf("随机数据为：\n");
showar(arr,MAXLEN);
printf("\n希尔排序的数据为：\n");
Shell_sort(arr,MAXLEN);
showar(arr,MAXLEN);
while(1);
return 0;
}

编译后运行输出：

随机数据为：
11 17 4 10 29 4 18 18 22 14 5 5 1 27 1 11 25 2 27 6
--------------------------
 
希尔排序的数据为：
1 1 2 4 4 5 5 6 10 11 11 14 17 18 18 22 25 27 27 29
--------------------------

7.顺序查找法

顺序查找是非常简单常用的查找算法，从第一个元素开始逐个与需要查找的元素进行比较，当比较到元素值相同时返回元素的下标，如果比较到最后都没有找到，则返回。

例如1：

含有哨兵的顺序查找，使用哨兵之后，不会出现查找不到元素的情况，最多出现返回值为0的情况。

#include "stdio.h"
 
int Search(int *arr,int n)
{
int x;
int i=n;
printf("请输入要查询的数：\n");
scanf("%d",&x);
arr[0]=x;
while(arr[i]!=x)
{
i--;
}
return i;
}
 
int main()
{
int n,i;
int x;
int arr[]={0};
printf("请输入序列的元素个数：\n");
scanf("%d",&n);
printf("请输入序列中元素：\n");
for(i=1;i<n+1;i++)
{
scanf("%d",&arr[i]);
}
x=Search(arr,n);
if(x==0)
printf("要查询的数不在此序列中\n");
else
printf("此数在序列中的位置为：%d\n",x);
while(1);
return 0;
}

编译后运行输出：

请输入序列的元素个数：
3
请输入序列中元素：
10 20 30
请输入要查询的数：
20
此数在序列中的位置为：2

例如2：

不含有哨兵的顺序查找，没有找到元素时返回-1。

#include <stdio.h>
#include <stdlib.h>
 
typedef struct List
{
int *data;
int length;
int num;
}List;
 
List *initList(int length)
{
List *list = (List*)malloc(sizeof(List));
list->length = length;
list->data = (int*)malloc(sizeof(int)*length);
list->num = 0;
return list;
}
 
void listAdd(List *list,int data)
{
list->data[list->num] = data;
list->num += 1;
}
 
int search(List *list,int key)
{
int i;
for(i=0;i<list->num;i++)
{
if(list->data[i]==key)
return key;
}
return -1;
}
 
void printList(List *list)
{
int i;
for(i=0;i<list->num;i++)
printf("%d ",list->data[i]);
printf("\n");
}
 
int main()
{
List *list = initList(8);
int i,keyval,m;
for(i=0;i<8;i++)
listAdd(list,i);
printf("列表内元素:");
printList(list);
printf("请输入要查找的元素:");
scanf("%d",&keyval);
m = search(list,keyval);
if(m>=0)
printf("查找到该元素下标值n:%d\n",m);
else
printf("未查找到该元素!\n");
while(1);
return 0;
}

编译后运行输出：

列表内元素:0 1 2 3 4 5 6 7
请输入要查找的元素:5
查找到该元素下标值n:5

8.二分查找法

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法，其思想就是不断地将有序查找表“一分为二”，逐渐缩小搜索区域，进而找到目标元素。

编译后运行输出：

#include <stdio.h>
 
int binarySearch(int arr[], int len, int target) {
int low = 0, high = len -1, mid;
while(low <= high) {
mid = (low + high) / 2;
if(arr[mid] == target) {
return mid;
} else if(arr[mid] > target) {
high = mid -1;
} else {
low = mid + 1;
}
}
return -1;
}
 
int main() {
int arr[] = {3, 4, 6, 12, 23, 26, 38, 42, 46, 55, 68};
int len = sizeof(arr) / sizeof(int);
int index, target;
printf("请输入要查找的值：");
scanf("%d", &target);
index = binarySearch(arr, len, target);
printf("目标值的下标是%d\n", index);
while(1);
return 0;
}

编译后运行输出：

请输入要查找的值：46
目标值的下标是8

9.分块查找法

分块查找是一种基于分块思想的查找算法，将待查找的数据元素序列分成若干块，每块中的数据元素可以是无序的，但块与块之间必须是有序的。然后，通过对块的查找和定位，缩小查找范围，最终在对应的块中进行顺序查找，从而找到目标元素；是一种效率较高的查找算法。

例如：

#include <stdio.h>
#include <stdlib.h>
 
struct index{
int key;
int start;
}newIndex[3];
 
 int cmp(const void*a,const void*b){
  return (*(struct index*)a).key>(*(struct index*)b).key?1:-1;
 }
 
 int search(int key,int a[])
 {
  int i=0,startvalue;
 while(i<3&&newIndex[i].key <key)
 {
  i++;
 }
 if(i>3)
 {
  return -1;
 }
 startvalue=newIndex[i].start ;
 while(startvalue<=startvalue+5&&a[startvalue]!=key)
 {
  startvalue++;
 }
 if(startvalue>startvalue+5)
 {
  return -1;
 }
 return startvalue;
  }
 
  int main()
  {
  int i,j=1,k,key,n;
  int a[20];
  printf("要输入数据的个数为：\n");
  scanf("%d",&n);
  printf("请输入%d个数据：\n",n);
  for(i=0;i<n;i++)
  {
   scanf("%d",&a[i]);
  }
  for(i=0;i<3;i++)
  {
   newIndex[i].start =j+1;
  j+=6;
  for(k=newIndex[i].start;k<=j;k++)
  {
   if(newIndex[i].key<a[k])
   {
   newIndex[i].key=a[k];
  }
   }
}  
 qsort(newIndex,3,sizeof(newIndex[0]),cmp);
 printf("输入您想要查找的数：\n");
 scanf("%d",&key);
 k=search(key,a);
 if(k>0)
 {
  printf("查找成功！您要找的数在数组中的标位是:%d\n",k);
  }
  else{
   printf("查找失败！您查找的数不在数组中。\n");
  }
  while(1);
  return 0;
}

编译后运行输出：

要输入数据的个数为：
12
请输入12个数据：
3 1 98 24 6 82 36 47 29 16 85 35
输入您想要查找的数：
16
查找成功！您要找的数在数组中的标位是:9

10.限幅滤波法

限幅滤波可以有效去除干扰波，维持稳定输出。对于输入信号的波形进行限制，当输入信号的幅值超过预设的限制范围时，输出信号就会被限制在预设范围内。限幅滤波法通常用于处理信号中的高频噪声，如电压波动等。

#include <stdio.h>
 
int filter(int value, int max, int min)
{
   value = (value)>(max)?(max):(value) ;
   value = (value)<(min)?(min):(value) ;
   return value;
}
 
int main()
{
int a = 1800;
int val;
val = filter(a, 1850, 1750);
printf("滤波数值为：%d", val);
while(1);
return 0;
}

编译后运行输出：

滤波数值为：1800

11.中位值滤波法

中位值滤波法能有效克服偶然因素引起的波动或采样不稳定引起的误码等脉冲干扰；采集N个周期的数据，去掉N个周期数据中的最大值和最小值，取剩下的数据的平均值。中位值滤波算法特别适用于会偶然出现异常值的系统。对温度 液位等缓慢变化的被测参数用此法能收到良好的滤波效果 ,但是对于流量压力等快速变化的参数一般不宜采用中位值滤波法；

例如：

#include<stdio.h>
#define NUM   7
 
int filter_middle(int *value_buf,int N)
{
    int count,i,j,temp;
    for (j=0;j<=N;j++){
           for (i=0;i<=N-j;i++){
               if (value_buf[i] > value_buf[i+1]){
                temp = value_buf[i];
                value_buf[i] = value_buf[i+1];
                value_buf[i+1] = temp;
            }
        }
    }
    printf("滤波中位值为：---%d---\n",value_buf[(N-1)/2]);
    return value_buf[(N-1)/2];
}
 
int main(){
 
 int value_buf[NUM] = {68,32,12,24,38,25,46};
 filter_middle(value_buf,NUM);
 while(1);
 return 0;
}

编译后运行输出：

滤波中位值为：---24---

12.算术平均滤波法

算术平均滤波法对连续的一段信号值进行平均处理，以减小信号中的噪声干扰；适用于信号变化缓慢且噪声比较小的情况，可以有效地平滑信号并减小噪声，但对于快速变化的信号或者噪声比较大的情况，则可能会产生较大误差。这种信号的特点是信号本身在某一数值范围附近上下波动 ,如测量流量、 液位；

例如：

#include <stdio.h>
 
int filter_ave(int *value_buf, int num)
{
int sumval=0, i;
for(i=0; i<num; i++)
sumval += value_buf[i];
return (int)(sumval/num);
}
 
int main()
{
int val;
int arr[5]= {12, 36, 82, 78, 31};
val = filter_ave(arr, sizeof(arr)/sizeof(int));
printf("平均数值为：%d", val);
while(1);
return 0;
}
 

编译后运行输出：

平均数值为：47

13.递推平均滤波法

递推平均滤波法采用队列作为测量数据存储器 , 设队列的长度为 N ,每进行一次测量 ,把测量结果放于队尾 ,而扔掉原来队首的一个数据 ,这样在队列中始终就有 N 个 “最新” 的数据。当计算平均值时 ,只要把队列中的 N 个数据进行算数平均 ,就可得到新的算数平均值。

例如：

#include <stdio.h>
 
int filter(int *value_buf, int new_value, int num)
{
static int i;
int count;
int sum = 0;
value_buf[i++] = new_value;
for (count=0; count<num; count++)
printf("%d ", value_buf[count]);
printf("\n");
if (i == num)
i = 0;
for (count=0; count<num; count++)
sum += value_buf[count];
return (int)(sum/num);
}
 
int main()
{
int i;
int ave_val, inval;
int arr[6]= {1, 2, 3, 4, 5,6};
inval = 0;
for(i=1; i<6; i++)
{
ave_val = filter(arr, inval, sizeof(arr)/sizeof(int));
printf("第%d次递推平均值为：%d\n",i,ave_val);
inval+= 10;
}
while(1);
return 0;
}

编译后运行输出：

0 2 3 4 5 6
第1次递推平均值为：3
0 10 3 4 5 6
第2次递推平均值为：4
0 10 20 4 5 6
第3次递推平均值为：7
0 10 20 30 5 6
第4次递推平均值为：11
0 10 20 30 40 6
第5次递推平均值为：17

14.一阶滞后滤波法

一阶滞后滤波法对周期干扰有良好的抑制作用，适用于波动频率比较高的场合；不适用于对实时性要求高的，相位滞后，灵敏度低。

例如：

#include <stdio.h>
#define a 0.3
 
int filter(int *value_buf, int num)
{
   static int value;
   static int add;
   if(add==num)add=0;
   value=(1-a)*value + a*value_buf[add];
   add++;
   return value;
}
 
int main()
{
int i;
int val;
int arr[6]= {120, 130, 133, 115,123,138};
for(i=1; i<7; i++)
{
val = filter(arr,sizeof(arr)/sizeof(int));
printf("第%d次一阶滞后数值为：%d\n",i,val);
}
while(1);
return 0;
}

编译后运行输出：

第1次一阶滞后数值为：36
第2次一阶滞后数值为：64
第3次一阶滞后数值为：84
第4次一阶滞后数值为：93
第5次一阶滞后数值为：102
第6次一阶滞后数值为：112