Java---详细解析数组中冒泡排序、选择排序、插入排序的运算过程及运用。

小鱼儿 2023-06-22 06:28 50阅读 0赞

### 冒泡排序法 ###

**特点**  
   1. 相邻两个数进行比较, 大的数往后面冒泡，每一趟比较完毕，最大的数出现在了最后面

2. 一共比较了 arr.length - 1 趟

3. 每一趟比上一趟少比较一次

**代码**

public class BubbleSortDemo {
        
    	public static void main(String[] args) {
        
    		int[] arr = {
        24, 69, 80, 55, 13};
    		System.out.println("排序前: " + Arrays.toString(arr));
    		
    		// 第一趟排序
    		/*
    		 * arr[0] 和 arr[1]
    		 * arr[1] 和 arr[2]
    		 * arr[2] 和 arr[3]
    		 * arr[3] 和 arr[4]
    		 * 
    		 * arr[i] 和 arr[i+1]
    		 * 
    		 * 重复的次数4
    		 */
    		/*for (int i = 0; i < arr.length - 1 - 0; i++) {
    			if (arr[i] > arr[i+1]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[i+1];
    				arr[i+1] = temp;
    			}
    		}
    		System.out.println("第一趟排序后: " + Arrays.toString(arr));
    		
    		// 第二趟排序
    		
    		 * arr[0] 和 arr[1]
    		 * arr[1] 和 arr[2]
    		 * arr[2] 和 arr[3]
    		 * 
    		 * arr[i] 和 arr[i+1]
    		 * 重复的次数3
    		 
    		for (int i = 0; i < arr.length - 1 - 1; i++) {
    			if (arr[i] > arr[i+1]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[i+1];
    				arr[i+1] = temp;
    			}
    		}
    		System.out.println("第二趟排序后: " + Arrays.toString(arr));
    		
    		// 第三趟排序
    		
    		 * arr[0] 和 arr[1]
    		 * arr[1] 和 arr[2]
    		 * 
    		 * arr[i] 和 arr[i+1]
    		 * 重复的次数3
    		 
    		for (int i = 0; i < arr.length - 1 - 2; i++) {
    			if (arr[i] > arr[i+1]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[i+1];
    				arr[i+1] = temp;
    			}
    		}
    		System.out.println("第三趟排序后: " + Arrays.toString(arr));
    		
    		// 第四趟排序
    		
    		 * arr[0] 和 arr[1]
    		 * 
    		 * arr[i] 和 arr[i+1]
    		 * 重复的次数3
    		 
    		for (int i = 0; i < arr.length - 1 - 3; i++) {
    			if (arr[i] > arr[i+1]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[i+1];
    				arr[i+1] = temp;
    			}
    		}
    		System.out.println("第四趟排序后: " + Arrays.toString(arr));*/
    
    		//通过以上代码发现的规律，将代码进行优化的冒泡排序法
    		for (int i = 0; i < arr.length - 1; i++) {
        
    			for (int j = 0; j < arr.length - 1 - i; j++) {
        
    				if (arr[j] > arr[j+1]) {
        
    					int temp = 0;
    					temp = arr[j];
    					arr[j] = arr[j+1];
    					arr[j+1] = temp;
    				}
    			}
    		}
    		System.out.println("冒泡排序后: " + Arrays.toString(arr));
    	}
    }

### 选择排序 ###

**特点**  
    1.选择排序是每个元素依次和后面所有元素进行比较,第一趟排序后,最小的数就出现在做前面

2.一共比较了 arr.length - 1趟

3.每一趟比上一趟少比较1次

4.每一趟比较的数的起始位置是上一趟的起始位置 + 1  
**代码**

public class SelectSortDemo {
        
    	public static void main(String[] args) {
        
    		int[] arr = {
        44, 89, 100, 77, 33};
    		System.out.println("选择排序前: " + Arrays.toString(arr));
    		
    		// 第一趟排序
    		/*
    		 * arr[0] 和 arr[1]
    		 * arr[0] 和 arr[2]
    		 * arr[0] 和 arr[3]
    		 * arr[0] 和 arr[4]
    		 * 
    		 * 一共比较了 arr.length - 1 次
    		 */
    		/*int i = 0; // 5 1 ~ 5 1234
    		for (int j = i + 1; j < arr.length; j++) {
    			if (arr[i] > arr[j]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    		}
    		System.out.println("第一趟排序后: " + Arrays.toString(arr));
    		
    		i = 1; // 5 2 ~ 5 234
    		for (int j = i + 1; j < arr.length; j++) {
    			if (arr[i] > arr[j]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    		}
    		System.out.println("第二趟排序后: " + Arrays.toString(arr));
    		
    		i = 2; // 5 2 ~ 5 234
    		for (int j = i + 1; j < arr.length; j++) {
    			if (arr[i] > arr[j]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    		}
    		System.out.println("第三趟排序后: " + Arrays.toString(arr));
    		
    		i = 3; // 5 2 ~ 5 234
    		for (int j = i + 1; j < arr.length; j++) {
    			if (arr[i] > arr[j]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    		}
    		System.out.println("第四趟排序后: " + Arrays.toString(arr));*/
    		
    		//	//通过以上代码发现的规律，将代码进行优化的选择排序法
    		for (int i = 0; i < arr.length - 1; i++) {
        
    			for (int j = i + 1; j < arr.length; j++) {
        
    				if (arr[i] > arr[j]) {
        
    					int temp = 0;
    					temp = arr[i];
    					arr[i] = arr[j];
    					arr[j] = temp;
    				}
    			}
    		}
    		
    		System.out.println("选择排序后: " + Arrays.toString(arr));
    	}
    }

### 插入排序法 ###

**特点**  
    （Insertion Sort）是一种简单直观的排序算法。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，

找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，

需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

1.从第一个元素开始，该元素可以认为已经被排序

2.取出下一个元素，在已经排序的元素序列中从后向前扫描

3.如果该元素（已排序）大于新元素，将该元素移到下一位置

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5.将新元素插入到该位置后

6.重复步骤2~5  
**代码**

public class InsertSortDemo {
        
    	public static void main(String[] args) {
        
    		int[] arr = {
        69, 24, 15, 31, 13};
    		
    		System.out.println("排序前: " + Arrays.toString(arr));
    		/*
    		 * 第一趟排序
    		 * arr[1] 和 arr[0] 进行比较
    		 * 比较一次
    		 */
    		/*int i = 1;
    		for (int j = 0; j < 1; j++) {
    			if (arr[i] < arr[j]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    		}
    		System.out.println("第一趟排序后: " + Arrays.toString(arr));
    		
    		
    		 * 第二趟排序
    		 * arr[2] 和 arr[0] 进行比较
    		 * arr[2] 和 arr[1] 进行比较
    		 * 比较2次
    		 
    		i = 2;
    		for (int j = 0; j < 2; j++) {
    			if (arr[i] < arr[j]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    		}
    		System.out.println("第二趟排序后: " + Arrays.toString(arr));
    		
    		
    		 * 第二趟排序
    		 * arr[3] 和 arr[0] 进行比较
    		 * arr[3] 和 arr[1] 进行比较
    		 * arr[3] 和 arr[2] 进行比较
    		 * 比较3次
    		 
    		i = 3;
    		for (int j = 0; j < 3; j++) {
    			if (arr[i] < arr[j]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    		}
    		System.out.println("第三趟排序后: " + Arrays.toString(arr));
    		
    		
    		 * 第四趟排序
    		 * arr[4] 和 arr[0] 进行比较
    		 * arr[4] 和 arr[1] 进行比较
    		 * arr[4] 和 arr[2] 进行比较
    		 * arr[4] 和 arr[3] 进行比较
    		 * 比较4次
    		 
    		i = 4;
    		for (int j = 0; j < 4; j++) {
    			if (arr[i] < arr[j]) {
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    		}
    		System.out.println("第四趟排序后: " + Arrays.toString(arr));*/
    		
    		//通过以上代码发现的规律，将代码进行优化的插入排序法
    		for (int i = 1; i < arr.length ; i++) {
        
    			for (int j = 0; j < i; j++) {
        
    				if (arr[i] < arr[j]) {
        
    					int temp = 0;
    					temp = arr[i];
    					arr[i] = arr[j];
    					arr[j] = temp;
    				}
    			}
    		}
    		System.out.println("排序后: " + Arrays.toString(arr));
    	}
    }