A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 黑马王冬冬 中级黑马   /  2012-8-13 20:21  /  2724 人查看  /  8 人回复  /   1 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 黑马王冬冬 于 2012-8-15 10:41 编辑
  1. //建立双层for循环,循环取值
  2.         private void Bubble(List<Integer> list){
  3.         
  4.         for(int i = 0;i < (list.size());i++){
  5.                 for(int j = 0;j < (list.size());j++){
  6.                         //内存循环取值与外层值进行对比,true则交换两个元素的值
  7.                         if(list.get(j) > list.get(i)){
  8.                                 Integer in = list.get(j);
  9.                                 list.set(j, list.get(i));
  10.                                 list.set(i, in);
  11.                         }
  12.                 }
  13.         }
  14.         }
复制代码
这是我写的冒泡排序,运转正常,但神奇的是我自己的不明白该程序的原理,哪位同学帮忙分析一下。我很怀疑这是不是冒泡排序,但如果不是的话,它又是如何成功运转的呢?

评分

参与人数 1技术分 +1 收起 理由
张_涛 + 1 赞一个!

查看全部评分

8 个回复

倒序浏览
冒泡排序,形象点说就是像冒泡一样,把大的数或则小的数,像气泡一样慢慢的向上移动,这就把这样的排序叫做冒泡排序
它的原理:
依次比较相邻的两个数,将小数放在前面,大数放在后面
1,在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。
2,在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。
3,如此下去,重复以上过程,直至最终完成排序。
由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序

评分

参与人数 1技术分 +1 收起 理由
张_涛 + 1 赞一个!

查看全部评分

回复 使用道具 举报
1、排序方法
     将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].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]上。

(3)第二趟扫描
     扫描R[2..n]。扫描完毕时,"次轻"的气泡飘浮到R[2]的位置上……
     最后,经过n-1 趟扫描可得到有序区R[1..n]

     第i趟扫描时,R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时,该区中最轻气泡飘浮到顶部位置R[i]上,结果是R[1..i]变为新的有序区。

评分

参与人数 1技术分 +1 收起 理由
张_涛 + 1 赞一个!

查看全部评分

回复 使用道具 举报
你这好像不是冒泡排序哦,好像是选择排序哦~~
冒泡排序是:相邻的两个元素进行比较,较大的往后移;(a1,a2,a3,a4,a5)它是a1和a2比较,然后a2和呵a3比较,....
选择排序是:前面的元素依次和后面的元素比较,较大的往前面移动,;(a1,a2,a3,a4,a5),a1和a2比较,a1和呵a3比较,a1和a4比较.....

评分

参与人数 1技术分 +1 收起 理由
张_涛 + 1 赞一个!

查看全部评分

回复 使用道具 举报
显然不是冒泡,应该是正常排序
回复 使用道具 举报
我把冒泡和选择,折半都写了,你对比着看一下
  1. import java.util.Arrays;
  2. import java.util.Random;

  3. public class Sort {

  4.         //写冒泡排序的时候,想到还有其他的排序方法,就顺道写了选择排序,折半查找
  5.        
  6.         public static void main(String [] args){
  7.                 Sort s = new Sort();
  8.                 int [] arr = s.randomArray();
  9. //                //冒泡排序,降序打印
  10. //                s.bubbleSortASC(arr);
  11. //                //冒泡排序,升序打印
  12. //                s.bubbleSortDESC(arr);
  13.                 //选择排序,升序打印
  14. //                s.selectSortAEC(arr);
  15.                 //优化后的选择排序,降序打印
  16. //                s.selectSortOptDESC(arr);


  17.                
  18.                
  19. //                int [] arr2 = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
  20. //                int key = 12;
  21.                 //自己写的折半查找
  22. //                int find = s.halfOfSearch(arr2, key);
  23.                 //调用API的折半查找
  24. //                int find2 = Arrays.binarySearch(arr2, key);
  25. //                System.out.println("find: " + find);
  26. //                System.out.println("find: " + find2);
  27.                
  28.         }
  29.         //打印排序后
  30.         public static void sortPrint(int []arr){
  31.                 System.out.println("sortPrint:");
  32.                 for(int i : arr){
  33.                         System.out.print( " "  + i + " ");
  34.                 }
  35.                 System.out.println("");
  36.         }
  37.         //打印排序前
  38.         public static void beforePrint(int []arr){
  39.                 System.out.println("beforePrint:");
  40.                 for(int i : arr){
  41.                         System.out.print( " "  + i + " ");
  42.                 }       
  43.                 System.out.println("");
  44.         }
  45.        
  46.         //随机取值
  47.         public int[] randomArray(){
  48.                 Random r = new Random();
  49.                 int arrayLength = 10;
  50.                 int [] arr = new int[arrayLength];
  51.                 for(int i = 0; i < arrayLength; i++){
  52.                         arr[i] = r.nextInt(100);
  53.                 }
  54.                 beforePrint(arr);
  55.                 return arr;
  56.         }
  57.         //交换位置
  58.         public static void swap(int a, int b, int []arr){
  59.                 arr[a] ^= arr[b];
  60.                 arr[b] ^= arr[a];
  61.                 arr[a] ^= arr[b];
  62.         }
  63.         //冒泡排序,升序打印
  64.         public void bubbleSortASC(int []arr){
  65.                
  66.                 for(int i = 0, len = arr.length; i < len - 1; i++){
  67.                         for(int j = 0; j < len - i - 1; j++){
  68.                                 if(arr[j] < arr[j + 1]){
  69.                                         swap(j, j + 1, arr);
  70.                                 }
  71.                         }
  72.                 }
  73.                 sortPrint(arr);
  74.         }
  75.         //冒泡排序,降序打印
  76.         public void bubbleSortDESC(int []arr){
  77.                 for(int i = 0, len = arr.length; i < len - 1; i++){
  78.                         for(int j = 0; j < len - i - 1; j++){
  79.                                 if(arr[j] > arr[j + 1]){
  80.                                         swap(j, j + 1, arr);
  81.                                 }
  82.                         }
  83.                 }
  84.                 sortPrint(arr);               
  85.         }
  86.         //选择排序,升序打印
  87.         public void selectSortAEC(int []arr){

  88.                 for(int i = 0; i < arr.length - 1; i++){
  89.                         for(int j = i; j < arr.length - 1; j++){
  90.                                 if(arr[i] > arr[j + 1]){
  91.                                         swap(i, j + 1, arr);
  92.                                 }
  93.                         }
  94.                 }
  95.                 sortPrint(arr);       
  96.         }
  97.         //选择排序,降序打印
  98.         public void selectSortDESC(int []arr){
  99.                 for(int i = 0; i < arr.length - 1; i++){
  100.                         for(int j = i; j < arr.length - 1; j++){
  101.                                 if(arr[i] < arr[j + 1]){
  102.                                         swap(i, j + 1, arr);
  103.                                 }
  104.                         }
  105.                 }
  106.                 sortPrint(arr);       
  107.         }
  108.         //优化后的选择排序,降序打印
  109.         public void selectSortOptDESC(int []arr){
  110.                 for(int i = 0; i < arr.length - 1; i++){
  111.                         int num = arr[i];
  112.                         int index = i;
  113.                         for(int j = i + 1; j < arr.length; j++){
  114.                                 if(num < arr[j]){
  115.                                         num = arr[j];
  116.                                         index = j;
  117.                                 }
  118.                         }
  119.                         if(index != i){
  120.                                 swap(i, index, arr);
  121.                         }
  122.                 }
  123.                 sortPrint(arr);       
  124.         }
  125.         //折半查找
  126.         public int halfOfSearch(int [] arr2,int key){
  127.                 int min = 0;
  128.                 int max = arr2.length - 1;
  129.                 int mid;

  130.                 while(min <= max){
  131.                         mid = (min + max) >> 1;
  132.                         if(arr2[mid] < key){
  133.                                 min = mid + 1;
  134.                         }else if(arr2[mid] > key){
  135.                                 max = mid - 1;
  136.                         }else{
  137.                                 return arr2[mid];
  138.                         }
  139.                 }       
  140.                 return - min - 1;               
  141.         }

  142. }
复制代码

评分

参与人数 1技术分 +1 收起 理由
张_涛 + 1 赞一个!

查看全部评分

回复 使用道具 举报
黑马王鹏 发表于 2012-8-13 20:32
冒泡排序,形象点说就是像冒泡一样,把大的数或则小的数,像气泡一样慢慢的向上移动,这就把这样的排序叫做 ...

从冒泡排序的定义上来说,这个程序确实不是冒泡排序,但该程序运转正常,我不明白的是该程序是怎样运转的,他是根据什么原理来进行排序的?
回复 使用道具 举报
黑马王冬冬 发表于 2012-8-14 13:39
从冒泡排序的定义上来说,这个程序确实不是冒泡排序,但该程序运转正常,我不明白的是该程序是怎样运转的 ...

你是要明白你的程序是怎么运转的,还是冒泡原理及应用是怎么样的
回复 使用道具 举报
冒泡排序算法原理
(1)分析

    因为每一趟排序都使有序区增加了一个气泡,在经过n-1趟排序之后,有序区中就有n-1个气泡,而无序区中气泡的重量总是大于等于有序区中气泡的重量,所以整个冒泡排序过程至多需要进行n-1趟排序。

    若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程可在此趟排序后终止。为此,在下面给出的算法中,引入一个布尔量exchange,在每趟排序开始前,先将其置为FALSE。若排序过程中发生了交换,则将其置为TRUE。各趟排序结束时检查exchange,若未曾发生过交换则终止算法,不再进行下一趟排序。

(2)具体算法

  void bubbleSort(int * R, int n)

      { //R[0 .. n-1]是待排序的文件,采用自下向上扫描,对R做冒泡排序

          int i,j;
          Boolean exchange; //交换标志


          for(i=0; i<n-1; i++) //最多做n-1趟排序
          {

              exchange=FALSE; //本趟排序开始前,交换标志应为假


              for(j=n-1; j>i;j--) //对当前无序区R[i .. n-1]自下向上扫描
              {

                  if(R[j] < R[j-1]) //交换记录

                  {

                      int tmp=R[j-1]; // 暂存单元

                      R[j-1]=R[j];

                      R[j]=tmp;


                      exchange=TRUE; //发生了交换,故将交换标志置为真
                  }
              }
if(!exchange) //本趟排序未发生交换,提前终止算法

                  return;

          } //endfor(外循环)
      } //bubbleSort
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马