插入排序算法--java

插入排序是一种简单的排序方法，时间复杂度为 O(n*n)，空间复杂度为O(1)，适用于数据已经排好序，插入一个新数据的情况。其算法的基本思想是，假设待排序的数据存放在数组 a[1...n] 中，增加一个节点 x 用于保存当前数据，进行比较，a[1]即作为有序区，a[2...n] 作为无序区。

从 i=2 起直至 i=n 为止，通过循环遍历，将 a[i] 放在恰当的位置，使 a[1...i] 数据序列有序

 例如，我们现在有一个数组 a=[3 2 4 1 6 5 2 7]，需要使用插入排序进行排列。

第0步：[3] 2 4 1 6 5 2 7
第1步：[2 3] 4 1 6 5 2 7
第2步：[2 3 4] 1 6 5 2 7
第3步：[1 2 3 4] 6 5 2 7
第4步：[1 2 3 4 6] 5 2 7
第5步：[1 2 3 4 5 6] 2 7
第6步：[1 2 2 3 4 5 6] 7
第7步：[1 2 2 3 4 5 6 7]

案例：

package Sort;

public class 插入排序 {
	public static void main(String[] args) {
		int[] a = {9,3,1,4,6,8,7,5,2};
		sort(a);
		print(a);
	}
	static void sort(int[] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = i; j > 0; j--) {
				if (a[j] < a[j-1]) {
					swap(a, j, j-1);
				}
				
			}
			
		}
	}
	//排序
	static void swap(int[] a,int i,int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	//打印数组
	static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
			
		}
	}
}

冒泡：基本不用，太慢

选择：基本不用，不稳

插入：样本小且基本有序的时候效率比较高