【Java】快速排序、归并排序、堆排序、基数排序实现总结

直接上代码，分析注释里

import java.util.Arrays;

public class Test{
	public static void main(String[] agrs){
		//int[] a = new int[]{6,5,7,1,3,9,8,4,2,0,10};
		int[] a = new int[]{6,27,1,3,5,8,24,2,10,5,8,8,8,24};		
		System.out.println(Arrays.toString(a));
		//quickSort(a,0,a.length-1);
		//MergeSort(a,0,a.length-1);
		
		CountSort(a);
		//HeapSort(a);
		//System.out.println("Counts：\n"+Arrays.toString(a));
		
	}
	
	
	public static void Swap(int[] a,int x,int y){
		int t = a[x];
		a[x] = a[y];
		a[y] = t;
	}

/**
	快速排序
	时间复杂度与key值有关，若key是整个数组的最大或最小值，则情况最坏，时间复杂度为O(N^2),
	最好的情况是类似二分，每次都从中间分，时间复杂度为O(N*logN),平均复杂度也是O(N*logN)，
        关于key值有三数取中优化的算法，在我的另一篇博客里有详细的代码实现
*/	
	//1.左右指针法
	public static int parsion1(int[] a,int left,int right){
		int begin = left, end = right;
		int key = a[right];
		while(begin<end){
			while(a[begin]<=key&&begin<end){
				begin++;
			}
			while(a[end]>=key&&begin<end){
				end--;
			}
			Swap(a,begin,end);
		}
		Swap(a,begin,right);
		return begin;
	}
	
	
	//2.挖坑法，类似于左右指针法
	public static int parsion2(int[] a, int left, int right){
		int begin = left, end = right;
		int key = a[right];
		
		while(begin<end){
			while(begin<end&&a[begin]<=key){
				begin++;
			}
			a[end]=a[begin];
			while(begin<end&&a[end]>=key){
				end--;
			}
			a[begin]=a[end];
		}
		a[begin]=key;
		return begin;
	}
	
	
	//3.前后指针法**（难点，我到现在都不能彻底捋顺这个算法，只想说设计这个算法的人脑洞真大！！）
	public static int parsion3(int[] a,int left,int right){
		int cur = left;
		int prev = cur-1;
		while(cur<right){
			if(a[cur]<=a[right]&&++prev!=cur){
				Swap(a,cur,prev);
			}
			cur++;
		}
		Swap(a,++prev,right);
		return prev;
	}
	
	public static void quickSort(int[] a, int left, int right){
		
		if(right<left){
			return;
		}
		int div = parsion3(a,left,right);
		quickSort(a,left,div-1);
		quickSort(a,div+1,right);
		
	}
/**
	归并排序，分治的思想
	分开的复杂度为logN，合并为N,故他的复杂度始终都是O(N*logN),空间复杂度为O(N)
*/	

	public static void Merge(int[] a, int left, int mid, int right){
		int begin1=left, end1=mid, begin2=mid+1, end2=right;
		int[] tmp = new int[right-left+1];
		int index=0;
		while(begin1<=end1&&begin2<=end2){
			if(a[begin1]<=a[begin2]){
				tmp[index++]=a[begin1++];
			}
			else{
				tmp[index++]=a[begin2++];
			}
		}
		
		while(begin1<=end1){
			tmp[index++]=a[begin1++];
		}
		while(begin2<=end2){
			tmp[index++]=a[begin2++];
		}
		for(index=0;index<right-left+1;index++){
			a[index+left]=tmp[index];
		}
		
	}
	
	public static void MergeSort(int[] a,int left, int right){
		int mid = left+((right-left)>>1);
		if(left>=right)
			return;

		MergeSort(a,left,mid);
		MergeSort(a,mid+1,right);
		Merge(a,left,mid,right);
		
	}
	
/**堆排序
	利用向下调整，每次将最大的元素至于a[0]，再将a[0]与最后一个元素交换，依次调整，即可得到有序序列
*/
	public static void AdjustDown(int[] a,int i, int n){
		int parent=i, child = parent*2+1;
		while(child<n){
			child = parent*2+1;
			if(child+1<n&&a[child]<a[child+1])
				child++;
			if(child<n&&a[parent]<a[child]){
				Swap(a,parent,child);
				parent=child;
			}
			else
				break;
		}
	}

	public static void HeapSort(int[] a){
		int i = (a.length-2)/2;	//i为最后一个节点，不是叶子
		for(;i>=0;--i){
			AdjustDown(a,i,a.length);
		}
		System.out.println("1:"+Arrays.toString(a));
		
		for(int j=a.length-1;j>0;--j){
			Swap(a,0,j);
			AdjustDown(a,0,j);
		}
		System.out.println("2:"+Arrays.toString(a));
	}
	
	

/**
	计数排序，将源数组以下标方式放入对应的目标数组里，如元素a[0]=5，放入目标数组的tmp[5]=1;若有两个5，则tmp[5]=2；
		使用BitMap可以大大减少开销空间，但是却不能存入多个数据，不过可以使用2位，或3位来表示存入个数，
		位图多用于查找某个数是否存在，而不考虑个数。
*/
	
	public static void CountSort(int[] a){
		int min=0, max=0;
		
		for(int i=0;i<a.length;++i){
			if(a[min]>a[i])
				min = i;
			if(a[max]<a[i])
				max = i;
		}
		
		int[] tmp = new int[a[max]-a[min]+1];
		
		for(int i=0;i<a.length;++i){
			tmp[a[i]-a[min]]++;
		}
		for(int i=0;i<tmp.length;++i){
			int j=tmp[i];
			while(j!=0){
				System.out.print(i+a[min]+", ");
				j--;
			}
		}
	}

}