Java数据结构和算法-3-数组-简单排序：冒泡排序/选择排序/插入排序

末蓝、 2022-03-10 10:10 218阅读 0赞

前面我们介绍了线性查找和二分查找，二分查找之前，我们需要进行对数组元素排序。本篇就是介绍三个简单的排序，分别是冒泡排序，选择排序，插入排序。可以说说，面试之前，这三个排序算法都是需要复习，哪怕背下来，并且解释出代码的含义和原理。

1、冒泡排序

这里我们新建一个BubbleSort.java用来写冒泡排序，代码如下

package array;
    
    public class BubbleSort {
    	public static void sort(long arr[]) {
    		long tmp = 0;
    		for (int i = 0; i < arr.length - 1; i++) {
    			for (int j = arr.length - 1; j > i; j--) {
    				//判断前面数据大小: 如果后面数据比前面数据还小
    				if(arr[j] < arr[j - 1]) {
    					//进行交换
    					tmp = arr[j];
    					arr[j] = arr[j - 1];
    					arr[j - 1] = tmp;
    				}
    			}
    		}
    	}
        
    	//打印数组显示
    	public static void print(long arr[]) {
    		System.out.print("[");
    		for (int i = 0; i < arr.length; i++) {
    			if (i == arr.length -1) {
    				System.out.print(arr[i]);
    			} else {
    				System.out.print(arr[i] + " ");
    			}
    		}
    		System.out.println("]");
    	}
    }

没什么好解释的，认真看看这双层for循环，和里面的判断条件和交互位置。第二个方法是我们前面写过的打印数组的方法。

测试类

package array;
    
    public class TestBubbleSort {
    	public static void main(String[] args) {
    		long[] arr = {95,23,75,29,1,-6};
    		System.out.print("排序之前的数组为：");
    		BubbleSort.print(arr);
    		
    		BubbleSort.sort(arr);
    		System.out.print("冒泡排序之后的数组为：");
    		BubbleSort.print(arr);
    	}
        
    }

测试结果：

排序之前的数组为：[95 23 75 29 1 -6]
    冒泡排序之后的数组为：[-6 1 23 29 75 95]

2、选择排序

选择排序就是，选择当前的arr\[i\]和数组中没有排序好的最小的元素进行交换位置。有一个参数k，表示数组中还没有排序好这部分里最小元素的下标。

package array;
    
    public class SelectionSort {
    	
    	public static void sort(long[] arr) {
    		int k = 0;
    		long tmp = 0;
    		for (int i = 0; i < arr.length - 1; i++) {
    			k = i;
    			for (int j = i; j < arr.length; j++) {
    				//k是指向最小的元素，发现如果还有比k还小，交换
    				if( arr[j] < arr[k]) {
    					k = j;
    				}
    			}
    			
    			tmp = arr[i];
    			arr[i] = arr[k];
    			arr[k] = tmp;
    		}
    	}
        
    	//打印数组显示
    	public static void print(long arr[]) {
    		System.out.print("[");
    		for (int i = 0; i < arr.length; i++) {
    			if (i == arr.length -1) {
    				System.out.print(arr[i]);
    			} else {
    				System.out.print(arr[i] + " ");
    			}
    		}
    		System.out.println("]");
    	}
    }

测试选择排序

package array;
    
    public class TestSelectionSort {
    	public static void main(String[] args) {
    		long[] arr = {34,23,-4,48,17};
    		System.out.print("排序之前的数组为：");
    		SelectionSort.print(arr);
    		
    		SelectionSort.sort(arr);
    		System.out.print("选择排序之后的数组为：");
    		SelectionSort.print(arr);
    	}
        
    }

运行结果：

排序之前的数组为：[34 23 -4 48 17]
    选择排序之后的数组为：[-4 17 23 34 48]

3、插入排序

插入排序就行玩牌过程中整理排的场景。在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。

package array;
    
    
    public class InsertSort {
    	
    	public static void sort(long[] arr) {
    		long tmp = 0;
    		
    		for(int i = 1; i < arr.length; i++) {
    			tmp = arr[i];
    			int j = i;
    			while(j > 0 && arr[j - 1] >= tmp) {
    				// 整体右侧移动一个位置
    				arr[j] = arr[j - 1];
    				j--;
    			}
    			arr[j] = tmp;
    		}
    	}
        
    	//打印数组显示
    	public static void print(long arr[]) {
    		System.out.print("[");
    		for (int i = 0; i < arr.length; i++) {
    			if (i == arr.length -1) {
    				System.out.print(arr[i]);
    			} else {
    				System.out.print(arr[i] + " ");
    			}
    		}
    		System.out.println("]");
    	}
    }

测试插入排序代码

package array;
    
    public class TestInsertSort {
    	public static void main(String[] args) {
    		long[] arr = {95,23,75,29,1,-6};
    		System.out.print("排序之前的数组为：");
    		InsertSort.print(arr);
    		
    		InsertSort.sort(arr);
    		System.out.print("插入排序之后的数组为：");
    		InsertSort.print(arr);
    	}
        
    }

运行结果：

排序之前的数组为：[95 23 75 29 1 -6]
    插入排序之后的数组为：[-6 1 23 29 75 95]

推荐一个常见排序的动画演示效果的网站，[http://www.jsons.cn/sort/][http_www.jsons.cn_sort]

[http_www.jsons.cn_sort]: http://www.jsons.cn/sort/