Java -- 排序算法之冒泡排序、快速选择排序、反转排序

快来打我* 2023-07-22 09:24 132阅读 0赞

在程序设计中，经常需要将一组数列进行排序，方便统计和查询。数组有很多常用算法，排序算法是必不可少的，今天给大家简单介绍三种常用的排序算法：冒泡排序、直接选择排序、反转排序。不足之处请指正…

### 冒泡排序 ###

冒泡排序是最常见、最常用的数组排序算法之一。它的工作过程总是将小数往前放，大数往后放，类似于水中气泡上升的动作。  
**1、基本思想**  
基本思想是对比相邻元素值，满足条件就交换元素值，把较小的元素移动到数组的前面，较大元素往后移动，实现把小的元素放到数组前面。  
**2、算法示例**  
冒泡排序是双循环结构，外循环控制排序轮数，内层循环主要用于对比数组中每个相邻元素的大小来确定是否交换位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70_pic_center]  
第一轮外循环时把最大值63排到了最后面，第二轮就不再对比最后一个值。因为他已经是最大的值，应该方法最后，对比剩余其他的值即可。同理第二轮24被放到倒数第二的位置上，以此类推，，，，  
**3、算法实现**

package cn.tedu.test;
    
    //测试冒泡排序
    public class BubbleSort { 
    	public static void main(String[] args) { 
    		//创建一个数组，里面的元素是乱序的
    		int[] array = { 63,4,24,1,3,15};
    		//创建冒泡排序类的对象
    		BubbleSort sorter = new BubbleSort() ;
    		//调用排序方法将数组排序
    		sorter.sort(array);
    	}
    	/* * 冒泡排序，要排序的数组 */
    	public void sort(int[] array) { 
    		for (int i = 1; i < array.length; i++) { 
    			//比较相邻两个元素，较大的数往后冒泡
    			for (int j = 0; j < array.length - i; j++) { 
    				if (array[j] > array[j+1]) { 
    					int temp = array[j];//把第一个元素保存到临时变量中
    					array[j] = array[j+1];//把第二个元素的值保存到第一个里面
    					array[j+1] = temp;//把临时变量的值给第二个元素
    				}
    			}
    		}
    		showArray(array);//输出冒泡排序后的数组元素
    	}
    	/* * 显示数组中的所有元素 */
    	public void showArray(int[] array) { 
    		for (int i : array) { //遍历数组
    			System.out.print(i + " < ");//输出每个数组元素值
    		}
    		System.out.println();
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70]  
通过打印出来的结果可知，数组中的元素已经从大到小排列完成。

> **冒泡排序的主要思想就是：把相邻的两个元素进行比较，满足一定条件就进行交换，每排列完一次就可以将最大（或最小）值放到最后**

### 直接选择排序 ###

直接选择排序是选择排序的一种，速度要比冒泡排序快一些。  
**1、基本思想**  
基本思想是将指定排序位置与其他数组元素分别对比，满足条件就交换元素值。  
直接排序的交换次数要比冒泡排序少很多，所以速度会快  
**2、算法示例**  
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序的放在已排列好的数列的最后，直到全部数据元素排列完成  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70 1]  
**3、算法实现**

package cn.tedu.test;
    
    //测试直接选择排序
    public class SelectSort { 
    	public static void main(String[] args) { 
    		创建一个数组，里面的元素是乱序的
    		int[] array = { 63,4,24,1,3,15};
    		//创建直接排序类的对象
    		SelectSort sorter = new SelectSort() ;
    		//调用排序方法将数组排序
    		sorter.sort(array);
    	}
    	/* * 直接排序算法：要排序的数组 */
    	public void sort(int[] array) { 
    		int index;
    		for (int i = 1; i < array.length; i++) { 
    			index = 0;
    			for (int j = 1; j <= array.length - i; j++) { 
    				if (array[j] > array[index]) { 
    					index = j;
    				}
    			}
    			//交换在位置array.length - i和index（最大值）上的两个数
    			int temp = array[array.length - i];//把第一个元素值保存到临时变量中
    			array[array.length - i] = array[index];//把第二个元素值保存到第一个元素中
    			array[index] = temp;//把临时变量也就是第一个元素值保存到第二个元素中
    		}
    		showArray(array);//输出直接选择排序后的数组
    	}
    	/* * 显示数组中的元素：要显示的数组 */
    	public void showArray(int[] array) { 
    		for (int i : array) { //遍历数组
    			System.out.print(i + " < ");//输出每个数组元素值
    		}
    		System.out.println();
    	}
    }

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

### 反转排序 ###

反转排序就是以相反的顺序把原来数组的内容重新排序。  
**1、基本思想**  
实现思路就是把数组的最后一个元素与第一个元素替换，倒数第二个元素与第二个元素替换，以此类推，直到所有元素反转替换。  
**2、算法示例**  
反转排序是对数组两边的元素进行替换，所以只需要循环数组长度的半数次。元素个数为偶数时除以二，元素个数为奇数时，元素个数减一再除以二，就是需要循环的次数  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70 3]  
**3、算法实现**

package cn.tedu.test;
    
    //测试反转排序
    public class ReverseSort { 
    	public static void main(String[] args) { 
    		//创建一个数组
    		int[] array = { 10,20,30,40,50,60};
    		//创建反转排序类的对象
    		ReverseSort sorter = new ReverseSort();
    		//调用排序对象的方法将数组反转
    		sorter.sort(array);
    	}
    	/* * 要排序的数组 */
    	public void sort(int[] array) { 
    		System.out.println("数组原来的内容");
    		showArray(array);//输出排序前的数组值
    		int temp;
    		int len = array.length;
    		for (int i = 0; i < len/2; i++) { 
    			temp = array[i];
    			array[i] = array[len - 1 - i];
    			array[len - 1 - i] = temp;
    		}
    		System.out.println("数组反转后的样子：");
    		showArray(array);//输出排序后的数组值
    	}
    	/* * 显示数组中所有的元素：要显示的数组 */
    	public void showArray(int[] array) { 
    		for (int i : array) { 
    			System.out.print(i + " 、 ");
    		}
    		System.out.println();
    	}
    	
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70 4]  
![图片是借鉴来的][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70 5]

理解的不深，勉强能写出来，有不足之处请指正。大家有更好的建议可以留言。。。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/e9b1378591f448838919904ee091f08a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70]: /images/20230528/3c495e693dcd4d0281c87dfba5cc478d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/d17d5db8e44640249b2a10087a5595ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70 2]: /images/20230528/29e76d3b1fe74d7dbfeb155a6ccfc670.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70 3]: /images/20230528/3da318e328a44afa91324e525cbaa7f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70 4]: /images/20230528/7840989c0a7e4b27a3ba6693403a8af4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTgwODgxNDAyNQ_size_16_color_FFFFFF_t_70 5]: /images/20230528/e10d4a12c8bb4515a733f5db3e0b2578.png