基于C语言的算法总结(不定时更新)

这篇博客我准备写一些我见过的算法，虽然现在我见过的还很少，但我相信会越来越多，方便日后自己查阅

好了 开始了

求解最大子序列和的最有效的算法

int MaxSubsequenceSum(const int A[], int N)
{
  int ThisSum, MaxSum, j;
  // 定义本次循环的和 与 最大和 为0
  ThisSum = MaxSum = 0;  
  // 循环求和
  for (j = 0; j < N; j++)
  {
       ThisSum += A[j];
       // 判断本次的和与最大和的大小，如果本次和比最大和大，把本次和的值赋值给最大和
       if (ThisSum > MaxSum)
        MaxSum = ThisSum;
       /* 如果本次和小于0，将本次和赋值为0 因为加到小于0了肯定不是最大子序列和了
        将其赋值为0 从新进行最大子序列和的比较 */
       else if ( ThisSum < 0)
       ThisSum = 0;
  }
      return MaxSum;
}
// 这个算法只循环了一次数组就求出了最大子序列和

 已知排序好的数组，求某个值的下标---->对分查找

int BinarySearch( const int A[], int X, int N)
{
    // 定义最小坐标，中间坐标，最大坐标
    int Low, Mid, High;
    Low = 0; High = N - 1;
    // 循环条件 最小坐标<=最大坐标
    while (Low <= High) {
        // 中间坐标算出来
        Mid = (Low + High) / 2;
        // 判断中间坐标对应的值是否小于要找到的值
        if (A[Mid] < X) {
            /* 如果小于让最小坐标变成中间坐标 + 1
            (也就是不用考虑中间坐标前面的数了) */
            Low = Mid + 1;
        } else if (A[Mid] > X) {
            /* 如果大于让最大坐标变成中间坐标 - 1
             (也就是不用考虑中间坐标后面的数了) */
            High = Mid - 1;
        } else {
            // 循环找到坐标
            return Mid;  // Found
        }
    }
    return -1;   // Not Found
}

计算最大公因数(欧几里德算法)

两个整数的最大公因数(Gcd)是同时整除二者的最大整数 例：Gcd(50, 15) = 5

unsigned int Gcd (unsigned int M, unsigned int N)
{
    unsigned int Rem;
    while ( N > 0) {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    return M;
}
// 算法通过连续计算余数直到余数是0为止，最后的非零余数就是最大公因数

高效率的取幂算法

/*
 如果N是偶数，我们有 X的N次方 = X的N/2次方 * X的N/2次方
 如果N是奇数，我们有 X的N次方 = X的(N - 1)/2次方 * X的(N - 1)/2次方 * X
 */
long int Pow (long int x, int N)
{
    if (N == 0) {
        return 0;
    }
    if (N == 1) {
        return x;
    }
    if (N % 2 == 0) {
        return Pow(x*x, N/2);
    } else {
        return Pow(x*x, N/2) * x;
    }
}
// 此算法运用到了递归

数组排序：冒泡排序

void sortArray(int a[], int len)
{
    for (int i = 0; i < len-1; i++) {
        /*
         每趟排序都会确定一个数，所以需要再循环len-i次，但因为每次都是
         相邻的两个数比较，为了a[j + 1]不越界，让j循环到len-i-1时停止
         */
        for (int j = 0; j < len-i-1; j++) {
            int tmp;
            // 如果条件满足，交换a[j]和a[j+1]两个相邻数的值
            if (a[j] > a[j+1]) {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}

数组排序：选择排序

void selectSort(int a[], int len)
{
    // 确定需要排序的次数
    for (int i = 0; i < len - 1; i++) {
        // 每一次都是拿一个元素与后面其他的元素进行比较，找到最小值
        for (int j = i + 1; j < len; j++) {
            if (a[i] > a[j]) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
    }
}

插入法排序

//插入法排升序
/*
 插入算法把要排序的数组分成两部分：
    第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置）
    第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
 */
#include <stdio.h>

void InsertionSort(int a[], int len)
{
    int i, j, tmp;
    // i=1是为了让数组多一个空间方便插入
    for (i = 1; i<len; i++) {
        // 将数组第i+1个数取出来
        tmp = a[i];
        // 循环从数组第i+1个数开始，判断前面的数是否大于这个数
        for (j = i; j>0 && a[j-1]>tmp; j--) {
            // 如果前面的数大于这个数，将前面的数移动到它后面一位，使前面留出位置
            a[j] = a[j-1];
        }
        // 将这个数插入这个留出的位置
        a[j] = tmp;
    }
    
    for (int i = 0; i<7; i++) {
        printf("%d	",a[i]);
    }
    printf("
");
}

int main()
{
//  插入排序的思想是数组是部分有序的，然后将无序的部分循环插入到已有序的序列中
    int b[]={1,2,3,4,18,32,12};
    InsertionSort(b, 7);
}

为了方便理解插入一张图片，配合上面代码理解（如下）

有两个数组a,b，大小都为n,数组元素的值任意整形数，无序； 

要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小。

    当前数组a和数组b的和之差为
    A = sum(a) - sum(b)

    a的第i个元素和b的第j个元素交换后，a和b的和之差为
    A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
           = sum(a) - sum(b) - 2 (a[i] - b[j])
           = A - 2 (a[i] - b[j])
    设x = a[i] - b[j]

    |A| - |A'| = |A| - |A-2x|

    假设A > 0,

    当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,

    如果找不到在(0,A)之间的x，则当前的a和b就是答案。

    所以算法大概如下：

    在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。

int sum1,sum2,a;          // 分别表示 a[]的和 b[]的和 以及2者之差
    int temp;     
    bool dayu0;                  // 和之差是否大于0
    int pos1,pos2;               // 等待交换的a[i]和b[j]的下标 i j
    float minn;                // 最接近a/2的a[i]-b[j]值
    bool have1 ;               // 是否能有解
    while (1)
    {
        sum1 = 0;
        sum2 = 0;
        for (int i = 0 ; i < n;++i)             // 求两个数组的和
        {
            sum1 += ar1[i];
            sum2 += ar2[i];
        }
        a = sum1 - sum2;                    // 和之差
        dayu0 = a>0?true:false;                  // 和之差是大于0还是小于0
        have1 = false;                           // 是否能找到解
        for (int i = 0 ; i < n;++i)            // 找最接近a/2的 a[i]-b[j]
        {
            for (int j = 0;j < n;++j)
            {
                temp = ar1[i] - ar2[j];
                if ((dayu0&&temp > 0&&temp < a)||(!dayu0&&temp < 0 && temp > a))      // 如果a[i]-b[j] 在(0,a)之间  (超出的就没有意义了)   
                {
                    if (have1&&abs(temp - a/2.0) < minn)                 // 若比之前的a[i]-b[j]更接近a/2 则更新
                    {
                        minn = abs(temp - a/2.0);
                        pos1 = i;
                        pos2 = j;
                    }
                    else                                               
                    {
                        have1 = true;
                        minn = abs(temp - a/2.0);
                        pos1 = i;
                        pos2 = j;
                    }
                }
            }
        }
        if (!have1)         // 若找不到符合条件的a[i]-b[j]了 则结束
        {
            break;
        }
        swap(ar1[pos1],ar2[pos2]);       // 交换a b中的元素
    }

-----------------------------------------------未完待续-----------------------------------------------

提示：1、代码由本人手打如有失误请麻烦提醒下，我将及时改正

            2、注释代表个人理解有歧义请指教，谢谢