冒泡排序，选择排序，插入排序，快速排序，归并排序，计数排序

 1. 冒泡排序，
package 排序算法;

public class MaoPaoPaiXu {

	public static void main(String[] args) {
		int [] maopao= {1,3,45,3,7,2,5,65,12};
		int temp;
		/**
		 * 外循环轮 内循环比较
		 * 从第一个元素开始相邻的两个元素比较,把小的元素往前调或者把大的元素往后调
		 * */
		for(int i=0;i<maopao.length-1;i++) {
			for(int j=0;j<maopao.length-i-1;j++) {
				/**稳定性排序：
				 * 排序前array[i]在array[j]前面排序后仍然在其前面,
				 * array[i]和array[j]指的是相等的元素,
				 * 改变稳定性：将：maopao[i]>maopao[j]改为;maopao[i]>maopao[j]
				 * */
				if(maopao[j]>maopao[j+1]) {	
					temp=maopao[j];
					maopao[j]=maopao[j+1];
					maopao[j+1]=temp;
				}
			}
		}
		for(int mp:maopao) {
			System.out.println(mp);
		}
	}
}
 2.选择排序，
package 排序算法;

public class XuanZePaiXu {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		/**
		 * 选择排序法 是对 定位比较交换法（也就是冒泡排序法） 的一种改进。
		 * 选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
		 * 基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
		 * 
		 * 
		 * 简单选择排序的基本思想：
		 * 第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；
		 * 第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；
		 * 以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，
		 * 使有序序列不断增长直到全部排序完毕。
		 * */
		int [] choose= {1,3,45,3,7,2,5,65,12};
		int temp;
		for(int i=0;i<choose.length-1;i++) {
			
			for(int j=i+1;j<choose.length;j++) {
				if(choose[i]>choose[j]) {
					temp=choose[i];
					choose[i]=choose[j];
					choose[j]=temp;
				}
			}
		}
		for(int cc:choose){
			System.out.println(cc);
		}
	}

}
3.插入排序.
package 排序算法;

public class ChaRuPaiXu {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		/**
		 * 简单的说，就是插入排序总共需要排序N-1趟，
		 * 从index为1开始，讲该位置上的元素与之前的元素比较，放入合适的位置，
		 * 这样循环下来之后，即为有序数组。
		 * */
		int [] charu= {21,44,76,74,8,2,89,54,21,45,44};
		int temp;
		for(int i=1;i<charu.length;i++) { 
			for(int j=0;j<i;j++) {
				if(charu[i]<charu[j]) {
					//把小的拿出来,把前面的往后覆盖到该位置
					temp=charu[i];
					for(int k=i;k>j;k--) {
						charu[k]=charu[k-1];
					}
					charu[j]=temp;
				}
			}
		}
		for(int cr:charu) {
			System.out.println(cr);
		}
	}

}
4.快速排序
package 排序算法;

import java.util.Arrays;

public class KuaiSuPaiXu {

	/*
	 * 递归
	 * 1）递归是一个普通独立的方法
	 * 自己调用自己的
	 * 2）递归一定找出口
	 * 	递归结束的条件
	 * 3）相同规律
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr1={34,56,78,90,12,32,1,23,45,36,36,56};
		System.out.println(Arrays.toString(arr1));
		//
		quickSortLeft(arr1, 0, arr1.length-1);
		System.out.println(Arrays.toString(arr1));
	}
	
	/*
	 * 参数列表：
	 * int[] 数组  大数组
	 * int left 小集合的左侧边界
	 * int right  小集合的右侧边界
	 * 
	 */
	public static void quickSortLeft(int [] arr,int left,int right){
		if(left>=right){
			//找递归出口
			return;
		}else {
			/**满足条件:找分界线的最终位置 */
			int index=getIndex(arr,left,right);
			
			//左侧开始递归
			quickSortLeft(arr, left, index-1);
			//右侧开始递归
			quickSortLeft(arr, index+1, right);
		}
		
	}
	//获取每次分界线的最终位置的方法：
	public static int getIndex(int [] arr,int left,int right) {
		//初始化分界线	每一个小数据集合的最左侧的元素
		int key=arr[left];
		//循环遍历比较
		while(left<right){//外层循环一次内层循环所有
			while(arr[right]>=arr[left]&&left<right){
				//先从右想做比较	从右向左获取每一个值 大于分界点：数组下标向前移动一位：right--
				right--;
			}
			//出了循环：交换位置
			int temp;
			temp=arr[left];
			arr[left]=arr[right];
			arr[right]=temp;
			//从左向右比较	从左向右比较获取的每个值小于分解点 数组下包向后移动一个位置 left++
			while(arr[left]<=arr[right]&&left<right){
				left++;
			}
			//出了循环：交换位置
			temp=arr[left];
			arr[left]=arr[right];
			arr[right]=temp;
			
		}
		//出了循环	最终的界限定了 left=right
		//给分界点赋值
		arr[left]=key;
		//返回分界点的下标
		return left;
	}
	
}
5.归并排序
package 排序算法;

import java.util.Arrays;

/**
 *归并排序
 *排两个有序数组
 */
public class GuiBingPaiXu {

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr1={1,2,4,5,7};
		int[] arr2={2,4,6,8,10,11};
		int []mergeSort = mergeSort(arr1,arr2);
		System.out.println(Arrays.toString(mergeSort));
	}
	//
	//参数：两个有序数组
	private static int[] mergeSort(int[] arr1, int[] arr2) {
		//创建一个大数组，用来存放最终结果
		int [] newarr=new int[arr1.length+arr2.length];
		//比较的过程
		int m=0;//用来记录arr1的下标
		int n=0;//用来记录arr2的下标
		int index=0;//用来记录大数组newarr的下标
		//只要两个小数组都有元素一直重复比较
		while(m<=arr1.length-1&&n<=arr2.length-1){
			//
			if(arr1[m]<arr2[n]){//arr1<arr2
				newarr[index]=arr1[m];
				m++;
				index++;
//				newarr[index++]=arr1[m++];
			}else{//arr1>arr2
				newarr[index++]=arr2[n++];
			}
		}
		//说明有一个数组已经没有元素的
		//另一个数组只需要全部过去
		while(m<=arr1.length-1){//arr1还有元素
			newarr[index++]=arr1[m++];
		}
		while(n<=arr2.length-1){//arr2还有元素
			newarr[index++]=arr2[n++];
		}
		return newarr;
	}
		
}
6.计数排序
package 排序算法;

/**
 * 计数排序：用空间换时间  适用于整数
 *基本思想：将数组的值放在新数组的下标里 对应下标的值存放原数组值对应值出现的次数
 *然后循环遍历输出
 */
public class JiShuPaiXu {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr={6,3,2,4,1,5,6,2,3,4,1,2,4,2};
		jisguSort(arr);
	}

	private static void jisguSort(int[] arr) {
		//求原数组的最大值 来确定新数组的最大下标和数组的长度
		int max=arr[0];
		for(int a:arr) {
			if(max<a) {
				max=a;
			}
		}
		//创建以个新数组 存储最终结果
		int newarr[]=new int[max+1];
		//循环遍历原始数组放在新数组中
		/*新数组的下标==原始数组的值
		 * 新数组的值为原始数组值出现的次数   默认为零
		 * */
		for(int a:arr) {
			//次数增加一次
			newarr[a]=newarr[a]+1;
		}
		/*循环遍历输出新数组
		 * 输出的下标按照次数
		 * **/
		for(int i=0;i<newarr.length;i++) {
			//按照次数进行输出或者放在数组里排好序了
			for(int j=1;j<=newarr[i];j++) {
				System.out.println(i+"\t");
			}
		}
		
		
	}

}