【交换排序】
是一种主要以交换的方式对序列进行排序的方法。
其实排序的基本方法或手段主要就是比较和交换,像选择法等都借助了交换的手段,但都不是主要以交换为手段,在直接选择排序的时候,一轮比较就能确定最大元素的位置,然后再进行交换,也就是说这样的交换是“稳定”的。
【冒泡排序法】
也叫起泡排序法,过程跟气泡从水里冒出来类似。一轮交换对相邻元素进行比较,如果逆序则交换,作用只能使一个元素到达最终位置,而其它的交换是多余的,如果只进行比较而不交换的话,就跟直接选择排序法一样,不同的是,它是不稳定的。
void bubblesort(int n,list r)
{
for (i=1;i=n-1,i++)
{
flag=1;//标记是否有交换
for (j=1;j=n-1;j++)
if (r[j].key>r[j+1].key)
{
flag=0;
swap(r[j],r[j+1]);//交换相邻元素
}
if(flag)return;//如果一轮比较没有元素交换则说明整体有序,直接退出
}
}
【快速排序法】
也是一种交换排序法,实际上它是冒泡法的改进。
【算法】
思想是:一次划分使整个元素部分有序,即从序列中任选一个元素,然后对其它元素进行这样的划分,使得所有比它小(大)的元素在左侧而所有比它大(小)的元素在右侧,然后用分治的思想对左右侧的序列同样的处理,直到只有一个元素为止。
一次划分的算法如下:
int quickpass(list r,int low,int high)
{
int i=low; j=high; x=r[i]; //置初值,i指最左端,j指最右端,选第i个元素为划分比较元素x
while (i<j)
{
while ((r[j].key>=x.key)&&(i<j))--j;
//自尾端进行比较,因为i处为空
if (i<j)
{
r[i]=r[j]; i++;//填入i处
while ((r[i].key<=x.key&&(i<j)++i;
//自首端进行比较,j处已空
if (i<j){r[j]=r[i];j--;}
}
}
r[i]=x;//一趟快速排序结束,将x移至正确位置
return i;//返回划分比较元素的位置
}
整个快速排序的过程用递归算法设计,思想当然是分治的思想:
void quicksort(list r,int low,int high)
//对r[low],r[low+1],...r[high]进行快速排序
{
if(low<high)
{
int k;
k=quickpass(r,low,high);//一次划分
quicksort(r,low,k-1);//对左侧元素以同样的方法对待
quicksort(r,k+1,high);//对右侧元素以同样的方法对待
}
}
正文
排序由浅入深(二)::交换排序2005-05-22 19:38:00
【评论】 【打印】 【字体:大 中 小】 本文链接:http://blog.pfan.cn/rickone/1240.html
阅读(9558) | 评论(1)
版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!
评论