排序法图文并茂.doc

一冒泡排序
1 算法思路:
冒泡排序首先通过两两比较,如果a>ai+1则交换位置,否则不交换,这样往往使
最后一个数据最大。而对于这个最大的数据前面的数据还不是有序的,因此还要对这个最大数据前面的数列继续采用两两交换的方法,并且它后面的数不用排序。以此类推直到“最大数“前面只有一个数为止,这样就形成了一个有序的数列。
操作步骤如下图:
原始数据: (两两比较)
第一次排序后: (最后一个最大)
无序
无序
第二次排序后:
第三次排序后:
a<ai+1,不用交换
第四次排序后
最后一个元素已
(注:从左到右两两比较交换后,再看下一组,如ai,ai+1为一组比较后,ai+1,ai+2为一组在比较)
2、算法实现:
#include<>
void main()
{
int a[]={100,12,6,9,2,13},i,j,tmp;
for(i=0;i<6;i++)
{
for(j=0;j<6-1-i;j++) //两两比较次数
{
if(a[j]>a[j+1])
{
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
for(i=0;i<6;i++)
{
printf("%d,",a[i]);
}
}
3、算法复杂性:
(n-1) + (n-2) + ... + 1 = n * (n - 1) / 2=T(n)=O(f(n))(最坏情况)
T(n)=O(n)(最优情况);
二、直接插入排序
1、算法思路:(主要通过文字与图形结合阐述原理)
该算法的基本思想是,把待比较的数列从第一个取出看成一个有序新数列,第二次
时把第二个数“取出”放到刚才只有一个数的有序数列中并进行比较后放到相应位
置。后面第三个也是同样的放到由两个数组成的有序数列中,依次类推直到后面没 数可“取”为止。
操作步骤如下图:
3
4
数列1
数列4
第四步
数列3
数列2
第三步
第二步
第一步
原始数据
1
4
3
2
0
1
0
4
2
3
4
2
3
2
4
2
2

0
第五步
数列5
每次当一个数据要插入到数列时,由于数列是有序的,因此插入的数据只需从
右(最大)往左依次与每个元素比较,只要它小于(按升序排时)左边元素就交换。
2、算法实现:
由C语言编程实现,定义一个数组用来存放待排序的数据,由于数组的第一 个序列只有一个数据——(数组的第一个元素)有序数列就是它本身,从数 组的第二个元素开始插入进行真正的排序。因此采用两个函数,一个取出要 插入的元素,另一个函数用于插入时在前面有序的数列中进行排序。
代码如下:
#include<>
void ch(int x[],int i)
{
int tmp;
while(i>0)
{
if(x[i]<x[i-1]) //用待插入的数据依次与有序数列从右到左依次排序
//遇到比它大的就交换;
{
tmp=x[i];
x[i]=x[i-1];
x[i-1]=tmp;
}
else break; //由于是插入到有序数列,因此只要一遇到比它小的,那么
//前面的都比它小。就退出。
i--;
}
}
void main()
{ int a[]={29,4,10,1,6,2,7},i,j,tmp;
for(i=1;i<7;i++)
{
if(a[i]<a[i-1]) //a[i]为被插入数据。如果它比有序数列中的第一个
//大,那么则把的下标记。
{
j=i;
ch(a,j);
}
}
for(j=0;j<7;j++)
{
printf("%d,",a[j]);
}
}
3算法复杂度T(n)=O(n^2).

三、希尔排序算法
1、算法思路
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
图中箭头之间的数列为两个数的数列进行直接插入排序后和它们之间原来已有的数据。
具体实施以下图为列:选择一个增量t(t<n/待排元素个数),而要进行直接排序的数据的下标相差t,也就是a0与a0+t进行直接插入排序,第二组为a1与a1+t进行直接插入排序,依次类推到最后一个数数据,(注:第二组必须在第一组进行完后得到的结果上才开始)再开始下一次这样从头到尾的直接插入排序,只是每一次的开始t增量都要减1,知道t=1,才结束。