冒泡法排序c++

《冒泡法排序c++》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、冒泡排序是非常容易理解和实现，，以从小到大排序举例：设数组长度为N。1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。3．N=N-1，如果N不为0就重复前面二步，否则排序完成。按照定义很容易写出代码：//冒泡排序1voidBubbleSort1(inta[],intn){inti,j;for(i=0;ia[j])Swap(a[j-1],a[j]);}下面对其进行优化，设置一个标志，如果这

2、一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。//冒泡排序2voidBubbleSort2(inta[],intn){intj,k;boolflag;k=n;flag=true;while(flag){flag=false;for(j=1;ja[j]){Swap(a[j-1],a[j]);flag=true;}k--;}}再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必

3、定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。//冒泡排序3voidBubbleSort3(inta[],intn){intj,k;intflag;flag=n;while(flag>0){k=flag;flag=0;for(j=1;ja[j]){Swap(a[j-1],a[j]);flag=j;}}}冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。白话经典算法系列之二直接插入排序的三种实现分类：白话经典算法系列2011-08-0619:2723895人阅读评论(

4、32)收藏举报算法直接插入排序(InsertionSort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。设数组为a[0…n-1]。1.初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=12.将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。3.i++并重复第二步直到i==n-1。排序完成。下面给出严格按照定义书写的代码（由小到大排序）：[cpp]viewplaincopyprint?1.voidInsertsort1(inta[],intn)2.{3.inti,j,

5、k;4.for(i=1;i=0;j--)8.if(a[j]j;k--)6.a[k+1]=a[k];7.//将a[i]放到正确位置上8.a[k+1]=temp;9.}10.}11.}voidInsertsort1(inta[],intn){inti,j,k;for(i=1;i<

6、n;i++){//为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置for(j=i-1;j>=0;j--)if(a[j]j;k--)a[k+1]=a[k];//将a[i]放到正确位置上a[k+1]=temp;}}}这样的代码太长了，不够清晰。现在进行一下改写，将搜索和数据后移这二个步骤合并。即每次a[i]先和前面一个数据a[i-1]比较，如果a[i]>a[i-1]说明a[0…i]也是有序的，无须调整。否则就令j=i

7、-1,temp=a[i]。然后一边将数据a[j]向后移动一边向前搜索，当有数据a[j]=0&&a[j]>temp;j--)9.a[j+1]=a[j];10.a[j+1]=temp;1