冒泡排序和选择排序C语言版

冒泡排序算法的思想：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
   代码如下：
   

   #include <stdio.h>
   #define N (sizeof(a) / sizeof(a[0])) //宏定义求数组的元素个数
   
   int main(int argc, const char *argv[])
   {
       int i,j,k;
       int tmp = 0;
       int a[] = {3,5,7,8,1,2,10,100,90,50,120};
   
       for(i = 0;i < N - 1;i++) //外层循环控制循环趟数，对于N各数字，只需要循环N-1趟
       {
           for(j = 0;j < N - 1 - i;j++) //内层循控制每趟循环中两两比较的次数
           {
               if(a[j] < a[j + 1])
               {
                   tmp = a[j];
                   a[j] = a[j + 1];
                   a[j + 1] = tmp;
               }
           }
       }
   
       for(k = 0;k < N;k++)
       {
           printf("%d  ",a[k]);
       }
       printf("\n");
   
       return 0;
   }

   运行结果：
   

   ubuntu@ubuntu:~/interview/c_study$ ./a.out
   120  100  90  50  10  8  7  5  3  2  1

       以上是把所有的代码全部写在main函数中，并没有体现出模块化变成的思想，因此将排序和打印的功能使用函数封装，且数组的值写死在代码中，不能让用户输入，因此，增加以上没有实现的功能，代码如下：
   

   #include <stdio.h>
   
   int bubble_sort(int a[],int n)
   {
       int i,j,tmp;
   
       for(i = 0;i < n - 1;i++)
       {
           for(j = 0;j < n - 1 - i;j++)
           {
               if(a[j] < a[j + 1])
               {
                   tmp = a[j];
                   a[j] = a[j + 1];
                   a[j + 1] = tmp;
               }
           }
       }
   
       return  0;
   }
   
   int print(int a[],int n)
   {
       int i;
   
       for(i = 0;i < n;i++)
       {
           printf("%d  ",a[i]);
       }
       printf("\n");
   }
   
   int main(int argc, const char *argv[])
   {
       int i;
       int a[32];
   
       printf("Please input 5 int numbers:\n");
   
       for(i = 0;i < 5;i++)
       {
           scanf("%d",&a[i]);
       }
   
       bubble_sort(a,5);
   
       print(a,5);
   
       return 0;
   }

   运行结果如下：
   

   ubuntu@ubuntu:~/interview/c_study$ ./a.out
   Please input 5 int numbers:
   5 3 2 1 4
   5  4  3  2  1
   ubuntu@ubuntu:~/interview/c_study$

   选择排序的思想：
       对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。
   代码如下：
   

   #include <stdio.h>
   
   #define N (sizeof(a) / sizeof(a[0]))
   
   int main(int argc, const char *argv[])
   {
       int i,j,k;
       int tmp = 0;
       int a[] = {3,1,5,2,100,90,20,60,9};
   
       for(i = 0;i < N - 1;i ++)
       {
           k = i; //使用k记录当前最小的元素，这里只是假设第i个元素是最小的，然后第i个元素后面的各个元素一次和
            //第i个元素比较，如果比i小，则使用k来记录这个比较小的元素。
   
           for(j = i + 1;j < N;j++) //循环中不断比较，始终让k值记录当前数组中最小元素的下标
           {
               if(a[j] < a[k]) //此时是按照从小到大的顺序排列
               {
                   k = j; //更新k的值，记录最小元素的下标
               }
           }
   
           if(k != i) //此时，我们假设的第i个元素并不是最小的，因此将第i个元素和第k个元素交换
           {
               tmp = a[k];
               a[k] = a[i];
               a[i] = tmp;
           }
           //经过一次循环，第一个数已经是最小的元素，下次从第2个数开始比较，然后找出次小的数，一次类推……
       }
   
       for(i = 0;i < N;i++)
       {
           printf("  %d\n",a[i]);
       }
       printf("\n");
   
   
       return 0;
   }

   运行结果：
   

   ubuntu@ubuntu:~/interview/c_study$ gcc select.c
   ubuntu@ubuntu:~/interview/c_study$ ./a.out
   1  2  3  5  9  20  60  90  100

   前面的代码把所有功能都写在main函数中，同样不能体现出模块化设计程序设计的思想，因此进行改造，让数据从终端输入保存在数组中，代码如下：
   

   #include <stdio.h>
   
   int selecl_sort(int a[],int n)
   {
       int i,j,k;
       int tmp = 0;
   
       for(i = 0;i < n - 1;i++)
       {
           for(j = i + 1,k = i;j < n;j++)
           {
               if(a[j] < a[k])
               {
                   k = j;
               }
           }
   
           if(k != i)
           {
               tmp = a[k];
               a[k] = a[i];
               a[i] = tmp;
           }
       }
   
       return 0;
   }
   
   int print(int a[],int n)
   {
       int i = 0;
   
       for(i = 0;i < n;i++)
       {
           printf("%d  ",a[i]);
       }
       printf("\n");
   
       return 0;
   }
   
   int main(int argc, const char *argv[])
   {
       int a[5];
       int i = 0;
   
       printf("please inpute 5 nubers \n");
       for(i = 0;i < 5;i++)
       {
           scanf("%d",&a[i]);
       }
   
       selecl_sort(a,5);
       print(a,5);
   
       return 0;
   }

   运行结果如下：
   

   ubuntu@ubuntu:~/interview/c_study$ gcc select_fun.c
   ubuntu@ubuntu:~/interview/c_study$ ./a.out
   please inpute 5 nubers
   5 4 3 1 2
   1  2  3  4  5

   冒泡排序算法和选择排序算法的区别：
   区别主要在交换的方式上
   这两种排序算法的相同点是每一轮都把最大或最小的元素筛选出来放在相应的位置上，但是，对于每一轮，比如第一轮，要把1~n 中最大的那个放到n这个位置，两种算法的主要区别如下：
   1.冒泡法每次比较和移动相邻的两项
   2.选择排序每次交换当前项和第n项
   冒泡：
   for i:=1 to n-1 do
     if (a[i]>a[i+1]) then swap(i,i+1);
   选择：
   for i:=1 to n-1 do
     if (a[i]>a[n]) then swap(i,n);
   (swap 表示交换）
   
   总的来说，两种排序比较的次数是相同的
   但交换的次数，选择排序是更少的
   虽然两者的时间复杂度都是 O（n^2)
   但通常，选择排序更快一点
   
   难得中秋放假更新一下博文，以便复习。