JAVA各种排序思想和示例

JAVA里面几种排序算法的原理

序号	名称	原理
1	冒泡排序	冒泡排序   排序原理： 通过两层循环控制， 外层循环，控制查找第i层的数，在余下的数据里最小或最大的   内层循环，负责依次比较下标相邻的两个数的大小，并负责将小数或大数的位置替换     每次的比较，都是上次在内存中替换完的新数组比较
2	选择排序	选择排序     对比数组中前一个元素跟后一个元素的大小， 如果后面的元素比前面的元素小则用一个变量k来记住他的位置，   接着第二次比较，前面“后一个元素”现变成了“前一个元素”， 继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量 k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最 小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，   就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中 第二小的数，让他跟数组中第二个元素交换一下值，以此类推。       a）第一次循环：记录第一个数的下标 b）将第一个数的值与后面的值相比、如果比后面值大、则将下标值改为后面值所对应的下标。 c）   第一次循环结束后、如果下标值有改动、说明后面有比此数值小的元素、交换两者位置 d）重复上述操作、直到所有数值都已排序
3	插入排序	插入排序 基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排   好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数 也是排好顺序的。如此反复循环，直到全部排好顺序。
4	希尔排序	基本思想：　    先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
5	快速排序	快速排序的原理   对于一个数组，进行按照某个key值进行拆分，   key值左边的数，统一小于key，key值右边统一大于key   然后递归对两边的的数组进行排序，   最后结果整体有序     怎么找到某个key值的点，默认按照取最后一个的数值来进行划分
6	桶排序	桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
7	堆排序	堆积排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法，辅助空间为O(1)， 最坏时间复杂度为O(nlog2n) ，堆排序的堆序的平均性能较接近于最坏性能。
8	归并排序	归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤
9	基数排序	(radix sort）则是属于“分配式排序”（distribution sort），基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。

package com.sanjiesanxian.sort.test;

/**
 * 所有排序算法的集合
 * **/
public class AllSort {

	static int datas[] = { 5, 2, 1, 3, 6,100,0,-9,999,12 };

	public static void main(String[] args) {

		// bubbleSort();
		// selectSort();
		//insertSort();
//	/	print("打印数组", datas);
 
		
		
		//shellSort1(datas, datas.length);
		
		//quickSort(datas, 0, datas.length-1);
	 	//print("\n打印数组", datas);
		
		
		
	}
	
	/**
	 * @param a 待排序的数组
	 * @param n 数组的长度
	 * 
	 * **/
	public static void shellSort1(int []a,int n){
		//gap为步长，每次减为原来的一半
		for(int gap=n/2;gap>0;gap/=2){
			//共有gap个组,对每一个组都执行直接插入排序
			
			for(int i=0;i<gap;i++){
				
				for(int j=i+gap;j<n;j+=gap){
					//如果a[j]<a[j-gap].则寻找a[j]位置，并将后面的数据的位置都后移
				if(a[j]<a[j-gap]){
					int tmp=a[j];
					int k=j-gap;
					while(k>=0&&a[k]>tmp){
						a[k+gap]=a[k];
						k-=gap;
					}
					a[k+gap]=tmp;
				}	
					
					
				}
			}
			
			
			
		}
		
	}
	
	
	/**
	 * 
	 * 对希尔排序中的单个组进行排序
	 * 
	 * @param a 待排序的数组
	 * @param n 数组总的长度
	 * @param i 组的起始位置
	 * @param gap 组的增量间隔
	 * 
	 *拆开2个方法
	 * 
	 * **/
	public static void groupSort(int[] a,int n,int i,int gap){
		
		for(int j=i+1;j<n;j+=gap){
			//如果a[j]<a[j-gap].则寻找a[j]位置，并将后面的数据的位置都后移
		if(a[j]<a[j-gap]){
			int tmp=a[j];
			int k=j-gap;
			while(k>=0&&a[k]>tmp){
				a[k+gap]=a[k];
				k-=gap;
			}
			a[k+gap]=tmp;
		}	
			
			
		}
		
		
	}
	
	/**
	 * 希尔排序，拆分版
	 * @param a 待排序的数组
	 * @param n 数组的长度
	 * 
	 * */
	public static void shellSort2(int []a ,int n){
		
		
		//gap为增量，每次减少为原来的一半
		for(int gap=n/2;gap>0;gap/=2){
			//共gap个组，对每一组都执行直接插入排序
			for (int i = 0; i < gap; i++) {
				groupSort(a, n, i, gap);
			}
		}
		
		
	}
	
	
	
	
	
	
	

	/**
	 * 冒泡排序
	 * 
	 * 排序原理： 通过两层循环控制， 外层循环，控制查找第i层的数，在余下的数据里最小或最大的
	 * 内层循环，负责依次比较下标相邻的两个数的大小，并负责将小数或大数的位置替换
	 * 
	 * 每次的比较，都是上次在内存中替换完的新数组比较
	 * 
	 * **/
	public static void bubbleSort() {

		System.out.print("排序前： ");
		for (int t : datas) {
			System.out.print(t + " ");
		}

		System.out.println();
		for (int i = 0; i < datas.length; i++) {

			for (int j = i + 1; j < datas.length; j++) {
				int temp = 0;
				System.out.println("i=" + i + " datas[i]=" + datas[i] + "  , "
						+ "j=" + j + " datas[j]=" + datas[j]);
				if (datas[i] > datas[j]) {
					temp = datas[j];
					datas[j] = datas[i];
					datas[i] = temp;
				}
				System.out.print("数组内容: ");
				for (int t : datas) {
					System.out.print(t + " ");
				}
				System.out.println("");

			}

			System.out.println("\n===========外部下面=============");
			for (int t : datas) {
				System.out.print(t + " ");
			}
			System.out.println("");

		}
		// System.out.print("排序后： ");
		// for(int t:datas){
		// System.out.print(t+" ");
		// }

	}
	
	/**
	 * 
	 * 快速排序的原理
	 * 
	 * 对于一个数组，进行按照某个key值进行拆分，
	 * key值左边的数，统一小于key，key值右边统一大于key
	 * 然后递归对两边的的数组进行排序，
	 * 最后结果整体有序
	 * 
	 * 怎么找到某个key值的点，默认按照取最后一个的数值来进行划分
	 * 
	 * 
	 * 
	 * 
	 * 
	 * 
	 * 快速排序
	 * @param arr 要排序的数组
	 * @param from 开头
	 * @param to 结尾
	 * 
	 * **/
	public static void quickSort(int arr[],int from ,int to){
		//1,5,2,4
		if(from<to){//仅当form<to时，才进行排序
			int temp=arr[to];//temp等于数组最后一位数字
			int i=from-1;//i等于-1；
			for(int j=from;j<to;j++){//j=0；j小于最大的长度to，j++
				if(arr[j]<=temp){//如果arr[j]的元素小于等于最后一位 数字
					i++;//i++；0
					int tempValue=arr[j];
					arr[j]=arr[i];
					arr[i]=tempValue;
				}
				
			//	print("\n循环中的 ", arr);
				
			}
			arr[to]=arr[i+1];
			arr[i+1]=temp;
			//System.out.println("轴的位置: "+arr[i]);
			quickSort(arr, from, i);
			quickSort(arr, i+1, to);
			
		}
		
		
		
		
	}
	
	
	
	

	/**
	 * 打印排序
	 * **/
	public static void print(String info, int datas[]) {
		System.out.print(info + ": ");
		for (int i : datas) {
			System.out.print(i + " ");
		}
	}

	/**
	 * 选择排序
	 * 
	 * 对比数组中前一个元素跟后一个元素的大小， 如果后面的元素比前面的元素小则用一个变量k来记住他的位置，
	 * 接着第二次比较，前面“后一个元素”现变成了“前一个元素”， 继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量
	 * k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最 小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，
	 * 就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中 第二小的数，让他跟数组中第二个元素交换一下值，以此类推。
	 * 
	 * 
	 * a）第一次循环：记录第一个数的下标 b）将第一个数的值与后面的值相比、如果比后面值大、则将下标值改为后面值所对应的下标。 c）
	 * 第一次循环结束后、如果下标值有改动、说明后面有比此数值小的元素、交换两者位置 d）重复上述操作、直到所有数值都已排序
	 * 
	 * 
	 * 
	 * 
	 * 
	 * **/
	public static void selectSort() {

		print("排序前", datas);
		for (int i = 0; i < datas.length; i++) {

			int lowIndex = i;// 最小值的下标
			for (int j = i + 1; j < datas.length; j++) {
				if (datas[j] < datas[lowIndex]) {
					lowIndex = j;
				}
			}

			// 当lowindex的值与i的不一致时，就进行交换
			if (lowIndex != i) {
				int temp = datas[i];
				datas[i] = datas[lowIndex];// 找到最小值付给当前的值
				datas[lowIndex] = temp;// 最小值下标的等于
			}
			// print("\n排序", datas);

		}

		print("\n排序后", datas);
	}

	/**
	 * 插入排序 基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排
	 * 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
	 * 也是排好顺序的。如此反复循环，直到全部排好顺序。
	 * 
	 * 
	 * 
	 * **/
	public static void insertSort() {

		print("插入排序前: ", datas);
		for (int i = 0; i < datas.length; i++) {
			// 取出当前要插入的值
			int insertVal = datas[i];
			// 拿当前要插入的值和前一位比，一直比到第一位
			int index = i - 1;
			while (index >= 0 && datas[index] > insertVal) {
				// 如果插入的值比前一位小，则将前一位的值，赋给插入位置，再拿当前值，和前一位比
			   //每次迭代都把最小的值放在前面
				datas[index + 1] = datas[index];
				index--;
			}
			datas[index + 1] = insertVal;
			
			
			print("\n排序中: ", datas);
		}

		print("\n插入排序后: ", datas);

	}

}

package com.sanjiesanxian.sort.test;

/**
 * 桶排序
 * 
 * */
public class BucketSort {

	
	
	/**
	 * 桶排序
	 * @param a 待排序数组
	 * @param max 数组a中最大值的范围
	 * **/
	public static void bucketSort(int[] a,int max){
		int buckets[];
		if(a==null||max<1){
			return;
		}
		//创建一个为max的数组buckets，并且将buckets中所有数据初始化为0
		buckets=new int[max];
		//1，计数
		for(int i=0;i<a.length;i++){
			buckets[a[i]]++;
		}
		
		//排序
		
		for(int i=0,j=0;i<max;i++){
			while((buckets[i]--)>0){
				a[j++]=i;
			}
		}
		buckets=null;
		
	}
	
	public static void print(String info,int a[]){
		System.out.print(info);
		for(int aa:a){
			System.out.print(aa+"  ");
		}
		System.out.println();
	}
	
	
	public static void main(String[] args) {
		
		//不支持负数排序
		int a[]={1,5,2,88,9};
		print("排序前: ", a);
		bucketSort(a, 89);
		print("排序后: ", a);
	}
	
	
	
}

package com.sanjiesanxian.sort.test;

/**
 * 堆排序
 * 
 * **/
public class HeapSort {

	
	/**
	 * 最大堆的向下调整算法
	 * 
	 * 数组实现的堆中，第N个节点左孩子的索引值是2N+1，右孩子的索引值是2N+2
	 * 其中，N为数组下标索引值，如数组中第一个数对应的N为0
	 * 
	 * @param a  待排序的数据
	 * @param start 被下调节点的起始位置 一般从0开始，表示从第一个开始
	 * @param  end  截至范围一般为数组中最后一个元素索引
	 * 
	 * **/
	public static void maxHeapDown(int []a ,int start,int end){
		int c=start; //当前节点的位置
		int l=2*c+1; //左孩子的位置
		
		int tmp=a[c]; //当前节点的大小
		for(;l<=end;c=l,l=2*l+1){
			//l 是左孩子，l+1是右孩子
			
			if(l<end&&a[l]<a[l+1]){//最大堆
			//	if(l<end&&a[l]>a[l+1]){//最小堆
				 
				l++; //左右两孩子里面选择较大者，即为_heap[l+1]
			}
			if(tmp>a[l]){//最大堆
				//if(tmp<=a[l]){//最小堆
				break;
			}else{
				a[c]=a[l];
				a[l]=tmp;
				
			}	
		}
		
	}
	
	 /**
	  * 堆排序从小到大
	  * 
	  * @param a  排序的数组
	  * @param n  数组的长度
	  * 
	  * */
	public static void heapSortAsc(int [] a,int n){
		int i,tmp;
		//从(n/2-1)--->0逐次遍历，遍历之后，得到的数组，实际上是一个最大的二叉堆
		
		for(i=n/2-1;i>=0;i--){
			maxHeapDown(a, i, n-1);
		}
		
		//从最后一个元素开始对序列，进行调整，不断的缩小调整的范围，知道第一个元素
		for(i=n-1;i>0;i--){
			//交换a[0]和a[i],交换后a[i]是0....i中最大的
			tmp=a[0];
			a[0]=a[i];
			a[i]=tmp;
			//调整a[0.....i-1],使得a[0....i-1]中最大的
			//即,保证a[i-1]是[0...i-1]中最大的值
			maxHeapDown(a, 0, i-1);
		}
		
		
		
		
	}
	
	
	public static void main(String[] args) {
		
	             int i;
	             int a[] = {1,4,-2,2,7,0,5};
	      
	               print("排序前:", a);
	              
	              heapSortAsc(a, a.length);//升序排列
	              
	               print("排序后:", a);
	                 
	}
	
	public static void print(String info,int a[]){
		System.out.print(info);
		for(int aa:a){
			System.out.print(aa+"  ");
		}
		System.out.println();
	}
	
	
	
	
	
	
	
	
	
	
}

package com.sanjiesanxian.sort.test;


/**
 * 
 * 归并排序
 * 
 * */
public class MergeSort {

	/**
	 * 将一个数组中两个相邻有序的区间合并成一个
	 * 
	 * @param a 包含有序区间的数组
	 * @param start  第一个有序区间的开始地址
	 * @param mid  第一个有序区间的结束地址，也是第二个有序区间的开始地址
	 * @param end 第二个有序区间的结束地址
	 * 
	 * */
	public static void merge(int []a,int start,int mid,int end){
		int []temp=new int[end-start+1];
		int i=start; //第一个有序区索引
		int j=mid+1; //第二个有序区的索引
		int k=0;  //临时区域的索引
		
		while(i<=mid&&j<=end){
			if(a[i]<=a[j]){
				temp[k++]=a[i++];
				
			}else{
				temp[k++]=a[j++];
			}
		}
		
		while(i<=mid){
			temp[k++]=a[i++];
		}
		
		while(j<=end){
			temp[k++]=a[j++];
		}
		
		for(i=0;i<k;i++){
			a[start+i]=temp[i];
		}
		
		
		temp=null;
		
	}
	
	
	
	
	
	
	
	
	/**
	 * 归并排序从上向下
	 * 
	 * a待排序的数组
	 * start数组的起始地址
	 * end 数组的结束地址
	 * 
	 * */
	
	public static void mergeSortUp2Down(int []a,int start,int end){
		if(a==null||start>=end){
			return;
		}
		
		int mid=(end+start)/2;
		mergeSortUp2Down(a, start, mid);//递归排序a[start...mid]
		mergeSortUp2Down(a, mid+1, end);//递归排序a[mid+1...end]
		
		//a[start...mid] 和 [mid+1...end] 两个有序空间
		//将他们排序成一个有序的空间a[start....end]
		merge(a, start, mid, end);
		
	}
	
	/***
	 * 对数组a做若干次合并: 数组a的总长度为len，将它分为若干个长度为gap的子数组；
	 * 将每2个相邻的子数组，进行合并排序
	 * 
	 * @param   a    待排序的数组
	 * @param   len  数组的长度
	 * @param   gap  子数组的长度
	 * **/
	
	public static void mergeGroups(int []a,int len,int gap){
		
		int i;
		int twolen=2*gap; //两个相邻子数组的长度
		
		//将每2ge相邻的子数组，进行合并排序
		for(i=0;i+2*gap-1<len;i+=(2*gap)){
			merge(a, i, i+gap-1, i+2*gap-1);
			
			
			//若i+gap-1< len-1 ,则剩余一个子数组没有配对
			//将该子数组合并到已排序的数组中
			if(i+gap-1<len-1){
				merge(a, i, i+gap-1, len-1);
			}
			
		}
		
	}
	
	/**
	 * 归并排序(从下往上)
	 * 
	 * @param a 待排序的数组
	 * **/
	public static void mergeSortDown2Up(int[]a){
		if(a==null){
			return;
		}
		for(int n=1;n<a.length;n*=2){
			mergeGroups(a, a.length, n);
		}
		
	}
	
	
	public static void main(String[] args) {
		
	 int []a={3,4,-1,44,32,9};
	 
	 print("排序前: ", a);
	 mergeSortUp2Down(a, 0, a.length-1);
	 print("排序后: ", a);
	 
	 
	}
	
	/**
	 * 输出排序
	 * 
	 * */
	private static void print(String info,int arr[]){
		
		System.out.println(info);
		for(int a:arr){
			System.out.print(a+" ");
		}
		System.out.println();
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
}

package com.sanjiesanxian.sort.test;


/***
 * 
 * 不支持负数
 * 基数排序
 * */
public class RadixSort {
	
	 /*
	      * 获取数组a中最大值
	      *
	      * 参数说明：
	      *     a -- 数组
	      *     n -- 数组长度
	      */
	     private static int getMax(int[] a) {
	         int max;
	 
	         max = a[0];
	        for (int i = 1; i < a.length; i++)
	           if (a[i] > max)
	                max = a[i];
	
	         return max;
	     }
	 
	     /*
	      * 对数组按照"某个位数"进行排序(桶排序)
	      *
	      * 参数说明：
	      *     a -- 数组
	      *     exp -- 指数。对数组a按照该指数进行排序。
	     *
	      * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}；
	      *    (01) 当exp=1表示按照"个位"对数组a进行排序
	      *    (02) 当exp=10表示按照"十位"对数组a进行排序
      *    (03) 当exp=100表示按照"百位"对数组a进行排序
	      *    ...
	      */
	     private static void countSort(int[] a, int exp) {
	         //int output[a.length];    // 存储"被排序数据"的临时数组
	         int[] output = new int[a.length];    // 存储"被排序数据"的临时数组
	         int[] buckets = new int[10];
	
	         // 将数据出现的次数存储在buckets[]中
	         for (int i = 0; i < a.length; i++)
	             buckets[ (a[i]/exp)%10 ]++;
	 
	         // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
	         for (int i = 1; i < 10; i++)
	             buckets[i] += buckets[i - 1];

	        // 将数据存储到临时数组output[]中
	         for (int i = a.length - 1; i >= 0; i--) {
	             output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];
	             buckets[ (a[i]/exp)%10 ]--;
	         }
	 
	        // 将排序好的数据赋值给a[]
	         for (int i = 0; i < a.length; i++)
	            a[i] = output[i];
	 
	         output = null;
	         buckets = null;
	     }
	
	     /*
	     * 基数排序
	      *
	      * 参数说明：
	      *     a -- 数组
	    */
	    public static void radixSort(int[] a) {
	        int exp;    // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
	         int max = getMax(a);    // 数组a中的最大值
	 
	         // 从个位开始，对数组a按"指数"进行排序
	         for (exp = 1; max/exp > 0; exp *= 10)
             countSort(a, exp);
	     }

	    public static void print(String info,int a[]){
			System.out.print(info);
			for(int aa:a){
				System.out.print(aa+"  ");
			}
			System.out.println();
		}
		
	    
	    public static void main(String[] args) {
			//不支持负数排序
	    	int a[]={1,5,2,88,9};
			print("排序前: ", a);
			 radixSort(a);
			print("排序后: ", a);
		}
}