（排序一）冒泡排序+选择排序+归并排序

冒泡排序：

从数组末尾开始依次与姓林的进行比较，如果a[i]<a[i+1] 交换位置，这样在第一轮比较后最大的冒在第0位置，然后再从末尾开始比较，然后次大的在第1的位置，依此类推

时间复杂度：O（n^2）

额外空间复杂度：O（1）

public static void popsort(int []arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for(int i=0;i<arr.length-1;i++) {
			for(int j=arr.length-1;j>i;j--){
				if (arr[j-1] < arr[j]) 
					swap(arr, j, j - 1);
			}
		}
	}

选择排序：

从第0个位置开始，遍历一遍数组选择最大的放在第一个位置，然后遍历2~n位置，选最大的放在第二个位置。每次遍历一遍得到最大的放在第i位置

时间复杂度：O（n^2）

额外空间复杂度：O（1）

public static void choosort(int []arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for(int i=0;i<arr.length-1;i++) {
			for(int j=i+1;j<arr.length;j++) {
				if(arr[i]<arr[j])
					swap(arr, i, j);
			}
		}
	}

代码2：

	public static void choosort2(int []arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for(int i=0;i<arr.length-1;i++) {
			int maxIndex=i;
			for(int j=i+1;j<arr.length;j++) {
				if(arr[maxIndex]<arr[j])
					maxIndex=j;
			}
			swap(arr,maxIndex,i);
		}
	}

插入排序：

从第1位置开始，与前面的比较

第i次循环，第i位置的数与前面的依次比较，如果大于前面的，交换，继续比较，直到前面的数比自己大停止。

时间复杂度：O（n^2）

额外空间复杂度：O（1）

public static void insertsort(int []arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for(int i=1;i<arr.length;i++) {
			for(int j=i;j>0;j--)
			{
				if(arr[j]>arr[j-1])
					swap(arr,j,j-1);
				if(arr[j]<=arr[j-1])
					break;
			}
		}
	}

---

swap函数：

private static void swap(int [] arr,int i, int j) {
		int t;
		t=arr[i];
		arr[i]=arr[j];
		arr[j]=t;	
	}

三个排序的稳定性分析：

插入排序和冒泡排序可以做到稳定性（相同大小的数保持原来位置）

选择排序不可以（在进行交换时，比如第2位置是一个较小的数数字0与后面的选择出来的最大的数交换时，可能会越过中间的数字0）