交换排序之冒泡排序详解

朴灿烈づ我的快乐病毒、 2023-07-20 05:37 29阅读 0赞

## 1.核心思想 ##

从数组第一个数字开始和第二个数字比较，将较大值交换给后者，然后第二个数字和第三个数字比较，同样，将较大值给后者，这样一趟下来，最大值就在数组的末尾，多次这样的操作，数组就变得有序了，就是相互比较，把最大值往后传递的过程

## 2.图解 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70][]  
将1与7比较，1比7小，不需要进行交换位置，指针后移，继续后面的比较  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 1][]  
7比3大，3和7交换，指针后移，进行后面的比较  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 2][]  
7比9小，不需要交换，后移  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 3][]  
9比4大，交换，然后后移  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 4][]  
9比2小交换，然后后移  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 5][]  
9比5大，交换，后移  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 6][]  
到末尾了，第一轮结束，最大的数已经在末尾，通过多轮这样的操作，可将数组排成升序，

## 3.完整代码 ##

c语言

#include<stdio.h>
    int main(){ 
    	int nums[]={ 1,7,3,9,4,5,2};
    	int t,i,j,len=sizeof(nums)/sizeof(nums[0]);
    	for(i=0;i<len;i++){ 
    		for(j=0;j<len-i-1;j++){ //每一趟需要排序的数字在减少，已经排好的数量是i 
    			if(nums[j]>nums[j+1]){ //若后者数字小于前者，交换，将大的数字放在后者的位置 
    				t=nums[j];
    				nums[j]=nums[j+1];
    				nums[j+1]=t;
    			}
    		}
    	}
    	for(i=0;i<len;i++)
    		printf("%d ",nums[i]);
    	return 0;
    }

java

public class BubbleSort { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		int[] nums=new int[] { 1,7,3,9,4,5,2};
    		for(int i=0;i<nums.length;i++) { 
    			for(int j=0;j<nums.length-i-1;j++) { 
    				if(nums[j]>nums[j+1]) { 
    					int t=nums[j];
    					nums[j]=nums[j+1];
    					nums[j+1]=t;
    				}
    			}
    		}
    		for(int e:nums)
    			System.out.print(e+" ");
    	}
    
    }

## 时间复杂度 ##

最好的情况是已经有序，O(n),最差的情况是O(n²),平均是O(n²)  
是稳定的算法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70]: /images/20230528/7d1e4a10388a464cbb53f6cbb42c8060.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 1]: /images/20230528/ea7a49f0cd44451a828818464c6c1e7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 2]: /images/20230528/b0b4307e9da345f28b5a1dbe3547fb44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 3]: /images/20230528/ece6961fce8f4289a9c1af7e9535a83d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 4]: /images/20230528/1426cea8095940999e1f7b2cd18747e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 5]: /images/20230528/5ce1e813e87e4ff59542c085a9908c7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 6]: /images/20230528/ce897e5d15d243b3abc673f1dab42152.png