算法基础部分-C语言表示

septstrings · 发表于 2011-6-3 13:12:30

C基础算法（个人整理版）

2011年5月，与WC和蓝总同去图书馆，突有此念头，故进行问题搜集并编写整理如下。部分代码参考或部分节选于网友程序。此为20个比较基础的，在各类C教程后习题中常见到的，后续将补充相关专业算法。

2011年5月，SeptStringS!

1，          两个值互换的问题

2，          计算某年是不是闰年

3，          冒泡法排序

4，          选择排序法

5，          插入排序法

6，          快速排序法

这个好难……弄了好久……不断修改……还是出问题了，后来参考了网上的一个程序……大体思想是，拿一个数作为基准，分别从右到左和从左到右进行扫描（假定从小到大排列），那么比基准小的就移动到基准的位置上，比基准大的，就移到先前操作空出来的右侧的位子上……额，这个说的有点乱，下面是程序，添加了许多辅助语句，直接运行分析已经很直观了！！就不多写了，免得自己也纠结了。

#include "stdio.h"

//实现从小到大排序

int Partition(int r[],int i,int j)

{

      int pivot,m;

      pivot = r; //把区间第一个数作为比较的基准

      printf("\n本次操作区间[=,=]\n",i,j);

      while(i < j)

      {

               ///////////////////////

               //从区间两端交替向中间扫描，直至i=j为止

               while(i < j&&r[j] >= pivot)

               {

                        j--; //如果没有找到比r小的数，那么一直减小j，向左扫描

               }

               if(i < j)

               {

                        r = r[j];//这里交换找到的第一个比r小的数

                        i++;

               }

               ///////////////////////

               //输出向左扫描换数操作后的数组当前值

               printf("由右向左扫描一次:\n");

               for(m = 0;m < 8;m++)

               {

                        printf("}",r[m]);

               }

               printf("��",i,j);

               printf("\n");

               ///////////////////////

               while(i < j&&r <= pivot)

               {

                        i++;//如果没有找到比r大的数，那么一直增大i，向右扫描

               }

               if(i < j)

               {

                        r[j] = r; //这里交换找到的第一个比r大的数

                        j--;

               }

               ///////////////////////

               //输出向右扫描换数操作后的数组当前值

               printf("由左向右扫描一次:\n");

               for(m = 0;m < 8;m++)

               {

                        printf("}",r[m]);

               }

               printf("��",i,j);

               printf("\n");

      } //endwhile

      r = pivot; //将基准值移动到当前所指数组位，以保证交换后不遗漏

      return i;//返回推进后的i值，作为下次分区间的标准

}

void QuickSort(int r[],int low,int high)

{

      int pivotpos; //把区间分成两部分，pivotpos是左区间和右区间的分割位

      if(low < high)//保证区间存在，也就是区间长度大于1时候才进行排序操作

      {

               pivotpos = Partition(r,low,high); //这是划分区间并移动数据的操作

               QuickSort(r,low,pivotpos - 1);//对左区间递归排序

               QuickSort(r,pivotpos + 1,high);//对右区间递归排序

      }

}

main()//这一部分没有什么难度，就是数组输出和子函数调用

{

      int a[8]={32,13,53,6,45,87,54,23},i;

      ///////////////////////

      printf("初始数据\n");

      printf(" a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]\n");

      for(i = 0;i < 8;i++)

      {

               printf("}",a);

      }

      printf("    i    j");

      printf("\n");

      printf("\n");

      ///////////////////////

      QuickSort(a,0,7);

      ///////////////////////

      printf("结果数据\n");

      for(i = 0;i < 8;i++)

      {

               printf("}",a);

      }

      printf("\n");

      ///////////////////////

}

7，          字符串排序

下面省略，放在附件