黑马程序员技术交流社区

标题: 冒泡排序的原理-已解决 [打印本页]
作者: 黑马王冬冬    时间: 2012-8-13 20:21
标题: 冒泡排序的原理-已解决
本帖最后由 黑马王冬冬 于 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.         }
复制代码
这是我写的冒泡排序，运转正常，但神奇的是我自己的不明白该程序的原理，哪位同学帮忙分析一下。我很怀疑这是不是冒泡排序，但如果不是的话，它又是如何成功运转的呢？
作者: pphdsny3    时间: 2012-8-13 20:32
冒泡排序，形象点说就是像冒泡一样，把大的数或则小的数，像气泡一样慢慢的向上移动，这就把这样的排序叫做冒泡排序
它的原理：
依次比较相邻的两个数，将小数放在前面，大数放在后面
1，在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。
2，在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。
3，如此下去，重复以上过程，直至最终完成排序。
由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序
作者: 于启会    时间: 2012-8-13 20:58
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]变为新的有序区。

作者: 官文昌    时间: 2012-8-13 21:10
你这好像不是冒泡排序哦，好像是选择排序哦~~
冒泡排序是：相邻的两个元素进行比较，较大的往后移；（a1，a2，a3，a4，a5）它是a1和a2比较，然后a2和呵a3比较，....
选择排序是：前面的元素依次和后面的元素比较，较大的往前面移动，；（a1，a2，a3，a4，a5）,a1和a2比较，a1和呵a3比较，a1和a4比较.....
作者: 宫明星    时间: 2012-8-14 10:47
显然不是冒泡，应该是正常排序
作者: 黎健东    时间: 2012-8-14 13:33
我把冒泡和选择，折半都写了，你对比着看一下
  1. import java.util.Arrays;
  2. import java.util.Random;

  4. public class Sort {

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


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

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

  136.                 while(min <= max){
  137.                         mid = (min + max) >> 1;
  138.                         if(arr2[mid] < key){
  139.                                 min = mid + 1;
  140.                         }else if(arr2[mid] > key){
  141.                                 max = mid - 1;
  142.                         }else{
  143.                                 return arr2[mid];
  144.                         }
  145.                 }       
  146.                 return - min - 1;               
  147.         }

  149. }
复制代码
作者: 黑马王冬冬    时间: 2012-8-14 13:39
黑马王鹏 发表于 2012-8-13 20:32
冒泡排序，形象点说就是像冒泡一样，把大的数或则小的数，像气泡一样慢慢的向上移动，这就把这样的排序叫做 ...

从冒泡排序的定义上来说，这个程序确实不是冒泡排序，但该程序运转正常，我不明白的是该程序是怎样运转的，他是根据什么原理来进行排序的？
作者: 黎健东    时间: 2012-8-14 13:48
黑马王冬冬 发表于 2012-8-14 13:39
从冒泡排序的定义上来说，这个程序确实不是冒泡排序，但该程序运转正常，我不明白的是该程序是怎样运转的 ...

你是要明白你的程序是怎么运转的，还是冒泡原理及应用是怎么样的
作者: 黑马_许芸    时间: 2012-8-14 15:31
冒泡排序算法原理
（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



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2