三大排序

1、冒泡排序

       优：简单，稳定，空间复杂度较低

       缺：慢，时间复杂度较高

	public static void main (String []args){
		int []a ={1,6,2,4,9,0,3,7,5,8};
		sort(a);
		for(int i:a){
			System.out.print(i+"\t");
		}
	}
	/**
	 * 冒泡排序
	 * @param a
	 */
	public static void sort(int []a){
		int length = a.length;
		int tem = 0;
		for(int i = 0; i<length-1; i++){
			for(int j = i+1; j<length;j++){
				if(a[i]>a[j]){	//交换数据
					tem = a[i];
					a[i] = a[j];
					a[j] = tem;
				}
			}
		}
	}

2、插入排序

       优：快，稳定

       缺：比较次数不一定，比较次数少，则数据移动多

	public static void main (String []args){
		int []a ={1,6,2,4,9,0,3,7,5,8};
		insertSort(a);
		for(int i:a){
			System.out.print(i+"\t");
		}
	}
	/**
	 * 插入排序
	 * @param a
	 */
	public static void insertSort(int []a){
		for(int i = 1 ; i < a.length ; i++){
			int j = i - 1;
			int tem = a[i];
			while(j>=0 && a[j]>tem){
				a[j+1] = a[j];
				j--;
			}
			a[j+1] = tem;
		}
	}

 

3、快速排序

       优：快，数据移动少

       缺：不稳定

	public static void main (String []args){
		int []a ={1,6,2,4,9,0,3,7,5,8};
		quickSort(a,0,a.length-1);
		for(int i:a){
			System.out.print(i+"\t");
		}
	}
	/**
	 * 快速排序
	 * @param a
	 * @param low
	 * @param height
	 */
	public static void 	quickSort(int []a , int low , int height){
		if(low < height){
			int tem = quick(a,low,height);
			quickSort(a,low,tem-1);
			quickSort(a,tem+1,height);
		}
	}
	public static int quick(int a[],  int low, int height){
		int n = low;
		int x = a[low];
		while(low < height){
			if(a[height] < x){
				if(a[low] > x){
					int tem = a[low];
					a[low] = a[height];
					a[height] = tem;
				}else{
					low++;
				}
			}else{
				height--;
			}
		}
		a[n] = a[low];
		a[low] = x;
		return low;
	}