本文共 3163 字，大约阅读时间需要 10 分钟。

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

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://tkows.baihongyu.com/