lcg_magic算法笔记：冒泡排序

Love The Way You Lie 2021-09-24 22:30 287阅读 0赞

### 文章目录 ###

*  冒泡排序
 *   *  1. 思想
     *  2. 算法
     *  3. 代码
     *  4. 结果
     *  5. 疑问
     *  6. 改进
     *  7. 更新
     *  8. 比较
     *  9. 源码
     *  10. 文件

# 冒泡排序 #

## 1. 思想 ##

**冒泡排序，人如其名，排序过程就是一个不断冒泡的过程。**  
**在冒泡过程中，值较大的元素下沉，值较小的元素上浮，逐渐形成有序。**

--------------------

若序列  A A A 中有  n n n 个元素，通常需要进行  n − 1 n-1 n−1 轮。  
第 1 轮，针对  A \[ 1 \] A\[1\] A\[1\] 至  A \[ n \] A\[n\] A\[n\] 元素进行排序；  
第 2 轮，针对  A \[ 1 \] A\[1\] A\[1\] 至  A \[ n − 1 \] A\[n-1\] A\[n−1\] 元素进行排序；  
……；  
第  n − 1 n-1 n−1 轮，针对  A \[ 1 \] A\[1\] A\[1\] 至  A \[ 2 \] A\[2\] A\[2\] 元素进行排序。

每一轮进行的过程：比较相邻的两个元素，如果不满足相对顺序，则进行交换；否则，不进行操作。  
直到这一轮中所有的元素和相邻元素的相对顺序正确。

## 2. 算法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center]

## 3. 代码 ##

public class BubbleSort
    { 
    	/** * 交换数组中的两个元素 * * @param array 一维数组 * @param firstIndex 待交换的第一个元素下标 * @param secondIndex 待交换的第二个元素下标 */
    	public static void swap(int[] array, int firstIndex, int secondIndex)
    	{ 
    		int buffer = array[firstIndex];
    		array[firstIndex] = array[secondIndex];
    		array[secondIndex] = buffer;
    	}
    	
    	/** * 冒泡排序 * * @param array 待排序的数组，也作为排序后的数组 */
    	public static void bubbleSort(int[] array)
    	{ 
    		for (int i = 0; i < array.length - 1; ++i)
    		{ 
    			for (int j = 0; j < array.length - 1 - i; ++j)
    			{ 
    				if (array[j] > array[j + 1])
    				{ 
    					swap(array, j, j + 1);
    				}
    			}
    			System.out.println("第 " + (i + 1) + " 轮：" + Arrays.toString(array));
    		}
    	}
    }

## 4. 结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 1]

结论：数组中的元素按照非递减顺序存储，排序结果正确。

## 5. 疑问 ##

观察输出结果可以发现：

> 第 6 轮排序的结果已经是最终的结果，第 7 ~ 9 轮排序无意义（浪费时间）。

是否可以改进上面的算法，使得在中间某一轮达到最终排序结果的时候，停止冒泡算法呢？  
答案是：可以！

## 6. 改进 ##

观察第 6 轮和第 7 轮冒泡排序，发现第 7 轮和第 6 轮排序后的结果完全一致。也即是说，第 7 轮冒泡排序没有交换任意两个元素。那么这一条件，可以作为冒泡排序算法的终止条件。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 2]

## 7. 更新 ##

public class BubbleSort
    { 
    	/** * 交换数组中的两个元素 * * @param array 一维数组 * @param firstIndex 待交换的第一个元素下标 * @param secondIndex 待交换的第二个元素下标 */
    	public static void swap(int[] array, int firstIndex, int secondIndex)
    	{ 
    		int buffer = array[firstIndex];
    		array[firstIndex] = array[secondIndex];
    		array[secondIndex] = buffer;
    	}
    	
    	/** * 冒泡排序改进版 * * @param array 待排序数组，也作为排序后的数组 */
    	public static void bubbleSortAdvanced(int[] array)
    	{ 
    		boolean swapFlag = true;
    		for (int i = 0; swapFlag && i < array.length - 1; ++i)
    		{ 
    			swapFlag = false;
    			for (int j = 0; j < array.length - 1 - i; ++j)
    			{ 
    				if (array[j] > array[j + 1])
    				{ 
    					swap(array, j, j + 1);
    					if (!swapFlag)
    					{ 
    						swapFlag = true;
    					}
    				}
    			}
    			System.out.println("第 " + (i + 1) + " 轮：" + Arrays.toString(array));
    		}
    	}
    }

结论：数组中的元素按照非递减顺序存储，排序结果正确。

## 8. 比较 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 3]

## 9. 源码 ##

package louis;
    
    import java.util.Arrays;
    
    public class BubbleSort
    { 
    	/** * 交换数组中的两个元素 * * @param array 一维数组 * @param firstIndex 待交换的第一个元素下标 * @param secondIndex 待交换的第二个元素下标 */
    	public static void swap(int[] array, int firstIndex, int secondIndex)
    	{ 
    		int buffer = array[firstIndex];
    		array[firstIndex] = array[secondIndex];
    		array[secondIndex] = buffer;
    	}
    	
    	/** * 冒泡排序 * * @param array 待排序的数组，也作为排序后的数组 */
    	public static void bubbleSort(int[] array)
    	{ 
    		for (int i = 0; i < array.length - 1; ++i)
    		{ 
    			for (int j = 0; j < array.length - 1 - i; ++j)
    			{ 
    				if (array[j] > array[j + 1])
    				{ 
    					swap(array, j, j + 1);
    				}
    			}
    			System.out.println("第 " + (i + 1) + " 轮：" + Arrays.toString(array));
    		}
    	}
    	
    	/** * 冒泡排序改进版 * * @param array 待排序数组，也作为排序后的数组 */
    	public static void bubbleSortAdvanced(int[] array)
    	{ 
    		boolean swapFlag = true;
    		for (int i = 0; swapFlag && i < array.length - 1; ++i)
    		{ 
    			swapFlag = false;
    			for (int j = 0; j < array.length - 1 - i; ++j)
    			{ 
    				if (array[j] > array[j + 1])
    				{ 
    					swap(array, j, j + 1);
    					if (!swapFlag)
    					{ 
    						swapFlag = true;
    					}
    				}
    			}
    			System.out.println("第 " + (i + 1) + " 轮：" + Arrays.toString(array));
    		}
    	}
    	
    	/** * main 函数，进行测试。 * * @param args 系统输入的参数 */
    	public static void main(String[] args)
    	{ 
    		int[] array = new int[]{ 43, 32, 76, -98, 0, 64, 33, -21, 32, 99};
    		bubbleSort(array);
    		System.out.println("Bubble Sort 最终结果：" + Arrays.toString(array));
    		
    		array = new int[]{ 43, 32, 76, -98, 0, 64, 33, -21, 32, 99};
    		bubbleSortAdvanced(array);
    		System.out.println("Bubble Sort Advanced 最终结果：" + Arrays.toString(array));
    	}
    }

## 10. 文件 ##

源代码文件已放至我的 Github 仓库中，如有需要请自行下载。  
链接：[Github(domagic)：BubbleSort.][Github_domagic_BubbleSort.]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/353de82f3ce943ac875e32b06bbd0125.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210923/c27e1e8a208c459991312e97afba523d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210923/2d383f749701484bb2ff92c2c8c754f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20210923/f871d06bc69c46dfad5344c34305c6a5.png
[Github_domagic_BubbleSort.]: https://github.com/domagic/Algorithms/blob/master/BubbleSort.java