排序算法总结     在第七章《数组》中涉及到选择法排序以及冒泡法排序，排序算法在《C程序设计》中的位置还是挺重要的。今天我们来总结一下排序算法。   一、交换法。   在前段时间，我们已经学过了对两个数或者三个数进行排序。用的方法是交换法。 交换法的原理是：要交换a,b杯的水，要借助空杯cup，先把a杯的水倒入cup中，此时a空，再把b杯中的水倒入a中，此时b空，最后把cup中的水倒入b中，实现a，b杯水的交换。 例如，要使a,b两个数由小到大排列。 if(a>b){ cup=a;a=b;b=cup;}   要使a，b，c由小到大排列。 if(a>b){cup=a;a=b;b=cup;} if(a>c){cup=a;a=c;c=cup;} if(b>c){cup=b;b=c;c=cup;}   二、选择法排序。   其原理是：从数据中选择最小的同第一个值交换，在从省下的部分中 选择最小的与第二个交换，这样往复下去。   交换法 选择法 for(i=1;i<=9;i++) for(j=i+1;j<=10;j++) if(a[i]>a[j])  {temp=a[i]; a[i]=a[j]; a[j]=temp; } for(i=1;i<=9;i++) {  min=i; for(j=i;j<=10;j++)   if(a[min]>a[j])min=j;   temp=a[i];   a[i]=a[min]   a[min]=temp; }         三、冒泡法排序，也叫起泡法排序。   冒泡法排序的思路是：将相邻两个数比较，将小的调到前头(由小到大排)。 若有n个数，则有进行n-1趟比较。 在第1趟比较中要进行n-1次两两比较，在第j趟比较中要进行n-j次比较。 请看下图： 如上图：6个数排序，由小到大排序。 第一趟（9-8-5-4-2-0），相邻两个数经过5次两两比较，前一个数比后一个数大的话，就互换，最大值9沉到底部了。到第二趟时就不用再比较那个9了。 第二趟（8-5-4-2），相邻两个数又经过4次两两比较，这四个数中的最大值8又沉到底部。 …………   所以如有n 个数比较，可以用以下语句实现冒泡排序。 假设输入n个数给a[1]到a[n]   for(j=1;j<=n-1;j++)/*j表示第几趟*/ {   for(i=1;i<=n-j;i++)    {      if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}    } }       四、插入法排序   原理：先将数组的头两个元素按顺序排列，接着将第3个元素插入到前面的适当位置，使3个元素按顺序排列，依次往后，将后面的元素插入到前面已排序的元素的适当位置，直到全部排序完毕。   如对以下五个数进行由小到大排序：（青色的与黄色的对比，将青色数插入到前面的适当位置，从它--青色数前面的元素开始往前寻找插入点） 原始数据： 36  28   50  14  68 第 一 趟： 36  28   50  14  68  ---> 28 36  50  14  68 第 二 趟： 28  36   50  14  68  ---> 28 36  50  14  68 第 三 趟： 28  36   50  14  68  ---> 14 28  36  50  68 第 四 趟： 14  28   36  50  68  ---> 14 28  36  50  68   for(i=1;i<n;i++) //共进行n-1趟 {   inserter=a[i];//保存第i个元素   //从第i-1个元素开始往前寻找插入点   j=i-1;   while(j>=0&&inserter<a[j])   {    a[j+1]=a[j];    j--;   }   a[j+1]=inserter;//插入第i个元素 }  

评论