黑马程序员技术交流社区

标题: 冒泡法和选择法的区别在哪里啊 [打印本页]
作者: 不土不木008    时间: 2015-12-29 00:04
标题: 冒泡法和选择法的区别在哪里啊
感觉都是一样的啊
作者: 15931110616    时间: 2016-1-5 11:58
原理不一样。。
作者: FYJKL    时间: 2016-1-5 12:31
冒泡排序是对每个相邻元素进行比较
作者: HHE_johnson    时间: 2016-1-5 14:44
本帖最后由 HHE_johnson 于 2016-1-5 14:52 编辑

首先排序的对用对象是数组，可以是整型数组，也可以是字符数组，甚至可以是字符串数组，这里以int数组为例，假设定义数组int  a[6] = {23,78,34,89,12,45}，排序无外乎就是遍历数组元素，比较元素，交换元素。很多人感觉冒泡排序和选择排序是一样的，其实不然，我在这先写一下思想，然后比照代码可以更好的理解 冒泡排序的思想是：                        在第1趟遍历中，依次比较相邻的两个数组元素（如a[0]和a[1]，a[1]和a[2]，a[2]和a[3]，a[3]和a[4]………）让相邻两个元素中较大的值放在下标较大的位置，如：若a[0]>a[1],则交换两个元素，让较大的值放在a[1],否则不交换，若a[1]>a[2],则交换两个元素，让较大的值放在a[2]，交换后a[2]和a[3]重复上述操作，让a[2]和a[3]中较大的值放到a[3]，到此a[3]中存放的是a[0],a[1]，a[2]和a[3]中的最大值，然后继续a[3]和a[4]，a[4]和a[5]，第一趟结束后，数组中的最大值已经移动到a[5];即较大的数沉底，较小的数上浮，所以叫冒泡排序                  
        然后进行第2趟遍历，从a[1到a[4],因为在第1趟中已经确定了最大值，并且放到了a[5],所以不用在比较a[5]了，第2趟结束后，把次大值放到了a[4]中。             第3趟： 遍历a[0]，a[1]，a[2]，a[3]，然后确定其中的最大值放到a[3]中，同理               
        第4趟： 确定a[0]，a[1]，a[2]中的最大值放到a[2]中。               
       第5趟： 确定a[0]，a[1]中的最大值放到a[1]中，这样剩下的a[0]自然是6个数中的最大值，至此排序结束，共遍历数组5趟，第i趟遍历前6-i个元素，确定6-i个元素的最大值，交换到a[6-i-1].               
代码如下：                        
/*   冒泡排序：    冒泡排序的实现方式大体上有两种:大数下沉和小数上浮，本例实现方法时小数上浮                 
1，和选择排序一样比较n-1趟，每一趟遍历前n-i个元素，找出最小的元素放到下标为n-i-1的位置               
2，比较是相邻两个元素比价，让比较小得元素移动到两个元素下标大的地方，这样每一趟结束，都是当前无序数的最小值          */                  /*          选择排序和冒泡排序的区别：    1，选择排序是某个数依次和其他没有序的人依次比较，冒泡的每一趟都是相邻的两个数比较          */                  
  1. # include <stdio.h>      
  2.   int main()        
  3. {            
  4.          void sort(int array[],int length);            
  5.          void sort2(int array[],int length);            
  6.          int a[10]={12,23,34,45,56,67,78,89,90,100};            
  7.       //sort(a,10);            
  8.        sort2(a,10);           
  9.      for(int i=0;i<10;i++)               
  10.       printf("%d ",a);            
  11.      printf("\n");            
  12.      return 0;      
  13.   }        
  14. void sort(int array[],int length)      
  15.    {            
  16. int i,j,temp;            
  17. for(i=0;i<length-1;i++)                 //               
  18.   for(j=0;j<length-i-1;j++)                    
  19. if(array[j]<array[j+1]) // 小数上浮                  
  20.   {                       
  21.   temp = array[j];                       
  22.   array[j] = array[j+1];                       
  23.   array[j+1] = temp;               
  24.      }                        
  25.      }         
  26. void sort2(int array[],int length)      
  27.   {           
  28.   int i,j,temp;         
  29.    for(i=0;i<length-1;i++)                 //               
  30.   for(j=length-i-1;j>0;j--)                    
  31. if(array[j] > array[j-1]) // 大数下沉                  
  32.   {                        
  33. temp = array[j];                        
  34. array[j] = array[j-1];                        
  35. array[j-1] = temp;               
  36.      }                    
  37.   }         
复制代码


选择排序的思想是：                 
        在第1趟遍历中，让第一个元素即a[0],依次与数组的其他元素（a[1]，a[2]，a[3]，a[4]，a[5]）比较，若发现有元素比a[0]小，则立即交换，让较小的元素和a[0],这样第1趟结束后，a[0]存放的就是数组的最小值。                                 
第2趟：因为已经确定了a[0]是数组6个元素的最小值，所以从a[1]开始往后遍历，确定a[1]，a[2]，a[3]，a[4]，a[5]中的最小值，然后放到a[1]中                 
第3趟：同理，遍历a[2]，a[3]，a[4]，a[5]，确定其中的最小值放到a[2]中。                 
第4趟：同理，遍历a[3]，a[4]，a[5]，确定其中的最小值放到a[3]中。               
第5趟：同理，遍历a[4]，a[5]，确定其中的最小值放到a[4]中，自然剩下的肯定是数组元素的最大值了，不用在参与比较                 同样，进过5趟比较后，数组元素已经有序，并且是由大到小，实现代码如下：               
  1. void sort2(int array[],int length)                 
  2. {                    
  3. int i,j,k,temp;                 
  4.     for(i=0;i<length-1;i++)                  
  5.   {                        
  6. for(j=i+1;j<length;j++)                           
  7.   if(array[j]>array)                           
  8.   {                                 
  9. temp = array;                                
  10. array = array[j];                                
  11. array[j] = temp;                             
  12. }                    
  13. }               
  14. }                  
复制代码


改进的选择排序算法：若上述两个排序方法已经掌握，我再给大家说一个改进的选择排序算法：                                 
  1. void selectSort2(int array[],int length)                 
  2. {                     
  3. int i,j,k,temp; //定义用于交换的变量temp                     
  4. for(i=0;i<length-1;i++)                    
  5. {                        
  6. k = i;//记录当前乱序的最大值的下标                        
  7. for(j=i+1;j<length;j++)                           
  8. if(array[j]>array[k])                                
  9. k = j;//发现数据比最大值大，更新下标                        
  10. if(i!=k) // 若i!=k，说明假定的最大值很真实的最大值下标不一样，交换，若一样就不用交换了                     
  11.     {                             
  12. temp = array;                           
  13. array = array[k];                             
  14. array[k] = temp;                       
  15.   }                    
  16. }               
  17. }                 
复制代码


这种方式不像上述选择排序一样，一发现比较小的值就交换，而是额外定义一个变量，存储当前趟遍历元素的最小值的下标，在一趟中每次若发现较小的值，则更新下标变量为较小值的下标，然后在一趟遍历结束的时候，把下标变量记录的元素与第i个元素交换。这样的话可以减少交换的次数，在一定程度上降低了算法的复杂度。
作者: HHE_johnson    时间: 2016-1-5 14:54
这个表述很清楚，理解也特别好，希望能帮到你哈！
作者: ak13211    时间: 2016-1-5 15:45
好复杂啊
作者: sunshine429    时间: 2016-1-5 17:27
冒泡排序是交换类的，选择排序是选择类的，具体你可以再学习下数据结构



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