一些比较常见的排序算法

采用java编写

插入排序

public static int[] chaRu(int[] ins){//插入排序 时间复杂度：N^2
	//小学生排队，每进来一个人就走到自己的相应位置
	//当前数前面的数对都是有序数对，只需将当前的数插入前面的数对中
	//因为前面的有序数对，最后一个一定是最大的
    //因此，将正确的数插入，只需从有序数对后面判断每个数与他的大小即可
	//如果数对中的数比当前数大，则交换，如果比他小则结束
	for(int i=1;i<ins.length;i++){ //从第二个数开始，第一个数没意义比较
           int temp=ins[i]; //拿出要比较的数
           int j=0;
           for(j=i-1;j>=0;j--){  //i位置之前是已经排好了的，从后往前比较
               if(ins[j]>temp){    //一次比较i位置之前的数，如果比要比较的数小，则把j这个位置的数往后移
            	   int turn=ins[j+1];
            	   ins[j+1]=ins[j];
            	   ins[j]=turn;
               }else {
                   break;
               }
           }
       }
	return ins;
}

冒泡排序

public static int[] mapPao(int[] in){//冒泡排序 时间复杂度：N^2
	//前一个数必须比后一个数小，不然就不是目标数组
	//扫一遍数组，不满足就交换一下
	//比较相邻的元素。如果第一个比第二个大，就交换他们两个。
	//对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
	//针对所有的元素重复以上的步骤，除了最后一个。
	//持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
	//把最大数的冒到最上面，每次可以确定一个最大的数，因此N次一定结束排序
	//交换个数等于逆序对数
	for(int i=0;i<in.length-1;i++){
		for(int j=0;j<in.length-1-i;j++){
			if(in[j]>=in[j+1]){
				int turn=in[j];
				in[j]=in[j+1];
				in[j+1]=turn;
			}
		}
	}
	return in;
}

选择排序

public static int[] xuanZe(int[] in){//选择排序 时间复杂度：N^2
	//老师帮小学生排队，最矮的排在前面
	//前面的是有序数对，并且前面的数对中最大的一个数，都不会比后面的无序数对中最小的数大
	//因此只需找出后面的无序数对中最小的数，放在有序数对最后即可
	for(int i=0;i<in.length;i++){
		int loss=i;//最小数字的索引
		for(int j=i;j<in.length;j++){
			if(in[j]<=in[loss]){
				loss=j;
			}
		}
		//将当前的数字与数组后面最小的数字进行交换
		int turn=in[i];
		in[i]=in[loss];
		in[loss]=turn;
	}
	return in;
}

地精排序

public static int[] diJing(int[] in) {//地精排序  时间复杂度:N^2
	//地精算法，只用一个循环即可完成排序
	//永远将第一个逆序列交换
	//等价于插入排序
	//前面是个有序表，后面的数不停的交换交换，最终移到正确的位置上。
	int i=0;
	int n=in.length;
	while (i<n) {
		if(i==0||in[i-1]<=in[i]){
			i++;
		}else{
			int turn=in[i];
			in[i]=in[i-1];
			in[i-1]=turn;
			i--;
		}
	}
	return in;
}

归并排序

public static void guiBing(int[] nums,int low,int mid,int high) {
	//将两个有序数组合并成一个有序数组成为归并   归并的时间复杂度为in1.length+in2.length
	//两个数组都是排好序的，最小的一定在左边
	//只需创建一个数组，并每次判断两个数组最左边的那个小，那个小就放哪个进结果数组
	int[] temp = new int[high - low + 1];
	int i = low;// 左指针
	int j = mid + 1;// 右指针
	int k = 0;
	// 把较小的数先移到新数组中
	while (i <= mid && j <= high) {
		if (nums[i] < nums[j]) {
			temp[k++] = nums[i++];
		} else {
			temp[k++] = nums[j++];
		}
	}
	// 把左边剩余的数移入数组
	while (i <= mid) {
		temp[k++] = nums[i++];
	}
	// 把右边边剩余的数移入数组
	while (j <= high) {
		temp[k++] = nums[j++];
	}
	// 把新数组中的数覆盖nums数组
	for (int k2 = 0; k2 < temp.length; k2++) {
		nums[k2 + low] = temp[k2];
	}
}

public static void guiBingPaiXu(int[] nums, int low, int high) {
	//当N=1时，数组必定有序，因此将原数组从中间分解，不停递归，最终得到N个长度为1的有序数组
	//将这N个有序数组两两归并，不停递归，最终得到目标数组
	//递归时间复杂度为NlogN
	int mid = (low + high) / 2;
	if (low < high) {
		// 左边
		guiBingPaiXu(nums, low, mid);
		// 右边
		guiBingPaiXu(nums, mid + 1, high);
		// 左右归并
		guiBing(nums, low, mid, high);
	}
}

快速排序

public static void kuaiSuPaiXu( int[] arr,int low,int high) {
	//归并排序是采用下标进行分治
	//快速排序采用值进行分治
	//给出数组A和阈值K，调整A使得左半边都小于K，右半边都大于K，中间一部分等于K,不断迭代
	//写法：1、找中轴，中轴左边的比中轴小，右边的比中轴大
	//2、以中轴分割，左边递归，右边递归，当左指针等于右指针停止递归
	if(low>=high){
		return;
	}
	int zhong=ZhongZhou(arr, low, high);
	kuaiSuPaiXu(arr,low, zhong-1);
	kuaiSuPaiXu(arr,zhong+1, high);

}

public static int ZhongZhou(int[] arr,int low,int high) {//获取中轴
	//中轴左边的数都比中轴数小，右边的数都比中轴数大。
	//设置两个下标，左下标low，右下标high
	int zhongZouZhi=arr[low];
	//以数组第一个元素为参考值
	//先从右边往左边找，如果当前元素比参考值大，则找下一个元素，
	while (low<high) {
		if(arr[high]>=zhongZouZhi && low<high) {
			high--;
		}
		arr[low]=arr[high];//左指针发现当前下标对应的值比参考值大，所以将这个值放到中心值的右边。
		//当左指针交替完后，移动右指针
		while (arr[low]<=zhongZouZhi && low<high) {
			low++;
		}
		arr[high]=arr[low];//右指针发现当前下标对应的值比参考值小，则将这个值放到中心值的左边
		//当右指针交替完后，移动左指针
		//直至左右指针在同一位置
	}
	arr[low]=zhongZouZhi;
	return low;
}

桶排序

public static void tongPaiXu(int[] in){//桶排序排序 时间复杂度：N+max(Ai)
	//很好用，但是数的值不能太大
	//1、桶排序是稳定的
	//2、桶排序是常见排序里最快的一种， 大多数情况下比快排还要快
	//3、桶排序非常快，但是同时也非常耗空间，基本上是最耗空间的一种排序算法
	//遍历数组查找最大数和最小数
	//创建足够容纳最大数和最小数之间所有数字的数组
	//遍历原数组，当前数字i，则tong[i]++
	//最后根据tong数组，输出个数
	int max=0;
	int min=0;
	for(int i=1;i<in.length;i++){
		if(in[i]>=in[max]){
			max=i;
		}else{
			min=i;
		}
	}
	max=in[max];
	min=in[min];


	int[] tong=new int[max-min+1];

	for(int j=0;j<in.length;j++){
		tong[in[j]-min]++;
	}

	for(int ss=0;ss<tong.length;ss++){
		for(int ssr=0;ssr<tong[ss];ssr++){
			System.out.print(ss+min+" ");
		}
	}
}

基数排序（桶排序的升级版）

public static void RadixSort(int[] arr){//基数排序（桶排序的升级版）
	//定义一个二维数组，表示10个桶，每个桶表示从0-9的是个数字
	//桶里的内容表示以当前数字为底的数有哪些
	int[][] tong=new int[10][arr.length];
	//为了记录每个桶中，世纪村放了多少数据，需要定义一个一维数组来记录每个桶的每次放入数据个数
	int[] tongNum=new int[10];
	//获得最大的数
	int maxNum=arr[0];
	for(int i=0;i<arr.length;i++){
		if(arr[i]>maxNum){
			maxNum=arr[i];
		}
	}
	//获得最大数的位数
	int MaxLegth=(maxNum+"").length();

	for(int n=10;n<=MaxLegth*10;n+=10){
		//取出对应的位数，入桶
		for(int i=0;i<arr.length;i++){
			int digitOfElement=arr[i]/n%10;//取出对应的位数
			//放入到对应的桶中
			tong[digitOfElement][tongNum[digitOfElement]]=arr[i];
			tongNum[digitOfElement]++;//记录每个桶中存放了多少数据
		}
		int index=0;//原数组更新到第几个数字
		//按照桶中的顺序，依次将数据取出放回原来的数组。
		for(int j=0;j<tongNum.length;j++){
			//若果桶中有数据才将其放回原数据
			if(tongNum[j]!=0){
				for(int k=0;k<tongNum[j];k++){
					arr[index]=tong[j][k];
					index++;
				}
			}
			//取出后记得清零
			tongNum[j]=0;
		}
	}
	System.out.println(Arrays.toString(arr));
}