注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zhouhaigang.love的博客

喜欢冬日黄昏那冻住的山

 
 
 

日志

 
 

冒泡排序与快速排序  

2011-02-19 18:24:50|  分类: C语言 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

冒泡算法
冒泡排序的算法分析与改进
交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。

冒泡排序

1
、排序方法
将被排序的记录数组R[1..n]垂直排列,每个记录R看作是重量为R.key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
1)初始
R[1..n]
为无序区。

2)第一趟扫描
从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n]R[n-1])(R[n-1]R[n-2])(R[2]R[1]);对于每对气泡(R[j+1]R[j]),若R[j+1].key<R[j].key,则交换R[j+1]R[j]的内容。
第一趟扫描完毕时,"最轻"的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R[1]上。

程序如下:

void main()

{

       //int a[2][3]={{3,4,5},{0,1,2}};

       //int (*p)[3];

       //p=a;

       //printf("%d\n",*(*(p+1)+1));

       int a[5] ={2,5,4,3,1};

 

       int i=0,j,temp;

       for(i=0;i<5;i++)

       {

              for(j=0;j<=5-i;j++)

              {

                     if(a[j]>a[j+1])

                     {

                       temp=a[j];

                       a[j]=a[j+1];

                       a[j+1]=temp;

                     }

              }

       }

       for(i=0;i<5;i++)

       {

              printf("%4d",a[i]);

       }

       printf("\n");

 

       return;

 

}

 快速排序

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。一趟快速排序的算法是:

  1)设置两个变量IJ,排序开始的时候:I=0J=N-1

  2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0]

  3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key的值A[J],并与A[I]交换;

  4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于keyA[I],与A[J]交换;

  5)重复第345步,直到 I=J (3,4步是在程序中没找到时候j=j-1i=i+1,直至找到为止。找到并交换的时候i j指针位置不变。另外当i=j这过程一定正好是i+j+完成的最后另循环结束)

  例如:待排序的数组A的值分别是:(初始关键数据:X=49)注意关键X永远不变,永远是和X进行比较,无论在什么位子,最后的目的就是把X放在中间,小的放前面大的放后面。

  A[0] A[1] A[2] A[3] A[4] A[5] A[6]

  49 38 65 97 76 13 27

  进行第一次交换后: 27 38 65 97 76 13 49

 

#include <stdio.h>

int arr[] = {14,10,11,5,6,15,0,15,16,14,0,8,17,15,7,19,17,1,18,7};

/* swap函数:交换v[k]v[j]的值 */

 void swap(int v[], int k, int j)

{

       int temp;

       temp = v[k];

       v[k] = v[j];

       v[j] = temp;

}

void qsort(int v[], int left, int right)

{

       int j, last;

       if (left >= right) /* 若数组包含的元素个数少于两个 */

              return; /* 则不执行任何操作 */

       swap(v, left, (left + right)/2); /* 将划分子集的元素移动到V[0] */

       last=left; /* last记录中比关键字小间的最右位置*/

       for (j = left+1; j <= right; j++) /* 划分子集 */

       {

       if (v[j] < v[left])

       {

       swap(v, last, j);

       }

 

       }

 

       qsort(v, left, last-1);

       qsort(v, last+1, right);

}

void main()

{

       int j;

      

       qsort(arr, 0, 19);

      

       for(j=0; j<=19; j++)

       {

              printf("%d ", arr[j]);

       }

      

       printf("\n");

}

  评论这张
 
阅读(68)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017