C语言算法:排序

时间：2010-11-21 来源：osullishuai80

一、选择法排序
【算法】从第一个元素开始作为起始值，与起始值比较找出剩下未比较过的最值与起始值交换.
【例程】选择法排序
     #include "stdio.h"
     void swap(int *a,int *b)
    {
        int tmp;
        tmp = *a;
        *a = *b;
        *b = tmp;
    }     void selectsort(int k[],int n) /*选择排序*/
    {
        int i,j,max;
        int temp;         for(i=0;i<n;i++)
       {
          for(j=i+1;j<n;j++)
         {
             if(k[j] < k[i])
             swap(&k[j],&k[i]);
         }
       }
    }     int main()
   {
       int i,array[10] = {2,5,6,3,7,8,0,9,12,3};
       printf("The data array is:\n") ;
       for(i=0;i<10;i++)                      /*显示原序列之中的元素*/
          printf("%d ",array[i]);
       selectsort(array,10);                   /*执行选择排序*/
       printf("\nThe result of selection sorting for the array is:\n");
       for(i=0;i<10;i++)
          printf("%d ",array[i]);              /*输出排序后的结果*/
       printf("\n");

       return 0;
   } 二、冒泡法排序
【算法】每遍历一次都从第一个元素开始找出一个最值，依次相邻比较往后推移，结尾条件向前移动.
【例程】冒泡法排序
        #include "stdio.h"
        void swap(int *a,int *b)
       {
           int tmp;
           tmp = *a;
           *a = *b;
           *b = tmp;
       }        void bubblesort(int k[],int n)/*冒泡排序*/
      {
         int i,j,tmp;
          for(i=0;i<n;i++)      /*控制每趟往前推一个，即少比较一次*/
         {
             for(j=0;j<n-i-1;j++)/*从第一个开始,不断与相邻值比较并交换最值，一直到最后，形如冒泡*/
            {
              if(k[j]<k[j+1])
               {
                   swap(&k[j+1],&k[j]);
               }
            }
         }
      }       int main()
     {
         int i,a[10] = {2,5,6,3,7,8,0,9,12,1};

         printf("The data array is\n") ;
         for(i=0;i<10;i++)                            /*显示原序列之中的元素*/
             printf("%d ",a[i]);

         bubblesort(a,10);                            /*执行冒泡排序*/
         printf("\nThe result of bubble sorting for the array is\n");
         for(i=0;i<10;i++)
             printf("%d ",a[i]);                      /*输出排序后的结果*/
         printf("\n");

         return 0;
     } 三、插入法排序
【算法】通过数据移动，留出合适位置插入顺序合适的值，而无需数据交换.
【例程】插入法排序
        #include "stdio.h"
       //从大到小进行排序
       insertsort(int k[],int n)        /*直接插入排序*/
      {
          int i,j;
          int temp;           for(i=1;i<n;i++)
         {
             temp = k[i];           /*将要比较的值先绶存起来留出一个空位，方便移动*/
            j = i - 1;
             while(j>=0 && k[j]>temp) /*比较直到出现比temp大的值，或向前找到头*/
             k[j+1] = k[j--];        /*将前面的值往后移*/
             k[j+1] = temp;        /*插在a[j]的后面*/
         }
      }       int main()
     {
         int i,array[10] = {2,5,6,3,7,8,0,9,12,1};    /*初始化序列，a[0]可任意置数*/
         printf("The data array is:\n") ;
         for(i=0;i<10;i++)                        /*显示原序列之中的元素*/
            printf("%d ",array[i]);          insertsort(array,10);                    /*插入排序*/
         printf("\nThe result of insertion sorting for the array is:\n");
         for(i=0;i<10;i++)
            printf("%d ",array[i]);               /*输出排序后的结果*/
         printf("\n");

         return 0;
     }