排序算法总结
在第七章《数组》中涉及到选择法排序以及冒泡法排序，排序算法在《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++) if(a[i]>a[j]) |
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个元素
}
评论