java实现的9种排序

交换排序：
1.冒泡排序

public static void bubble(int arr[]){
		for(int i=1;i<arr.length;i++){//控制次数
			for(int j=0;j<arr.length-i;j++){//控制当前比较到那个位置
				if(arr[j]>arr[j+1]){
					swap(arr,j,j+1);
				}
			}
		}
	}

2.快排

	public static void quickSort(int a[],int left,int right){
		int i;
		if(left<right){
			i=partition(a,left,right);
			quickSort(a,left,i-1);
			quickSort(a,i+1,right);
		}
	}
	
	public static int partition(int a[],int left,int right){
		int base = a[left];
		while(left<right){
			while(left<right && a[right]>=base) {--right;}
			a[left] = a[right];
			while(left<right && a[left]<=base)  {++left;}
			a[right] = a[left];
		}
		a[left] = base;//a[right]=base;  right==left;
		return left;
	}

选择排序
1.直接选择

	public static void select(int a[]){
		int index;
		for(int i=0;i<a.length-1;i++){
			index = i;
			for(int j=i+1;j<a.length;j++){
				if(a[j]<a[index]){
					index = j;
				}
			}
			if(index!=i){
				swap(a,index,i);
			}
		}
	}

2.堆排序

public static void  heap(int[] data)
	{
		int n = data.length;
		for(int i=n/2-1;i>=0;i--){//从中间有叶子节点的数据开始
			 keepHeap(data,i,n);
		}
		while (n > 0) {
		  swap(data, 0, n-1);//把第一个和本次建堆的最后一个交换
		  keepHeap(data, 0,--n);//排除最后一个继续建堆
		}
	}
	
	/**
	 * 建（大/小顶）堆操作
	 * @param r
	 * @param index 本次建堆的起始下标
	 * @param length 本次建堆的数据长度
	 */
	 private static void keepHeap(int[] r, int index,int length) {
		 int x = r[index];
		 int j = 2 * index + 1;
		 while (j < length ) {//注意是： 下标 < 长度（不是 下标＜最长的下表）
		 if (j < length - 1 && r[j] < r[j + 1])//判断是否存在右节点，且和左节点比较大小
		    ++j;
		 if (r[j] > x) {
		    r[index] = r[j];//上面小的变成下面大的
		    index = j;
		    j = 2 * index + 1; //继续向下
		   }else{
			   break;
		   }
		 }
		 r[index] = x;
	}

插入排序

1.直接插入排序

public static void insert(int a[]){
		for(int i=1;i<a.length;i++){
			int t = a[i];
			int j = i-1;
			while(j>=0 && t<a[j]){
				a[j+1] = a[j];
				j--;
			}
			a[j+1] = t;
		}
		
	}

2.折半插入排序

	public static void halfInsert(int a[]){
		for(int i=1;i<a.length;i++){
			int t = a[i];
			int big = i-1, small = 0;
			while(big>=small){
				int mid = (big+small)/2;
				if(a[mid]<t){
					small = mid+1;
				}else{
					big = mid-1;
				}
			}
			//(i-1）->small 数值 均向前移动一位 
			for(int j=i;j>small;j--){
				a[j] = a[j-1];
			}
			a[big+1] = t;
		}
	}

3.希尔排序
方法1.

	public static void shell(int a[]){
		for(int span=a.length/2;span>=1;span--){
			for(int i=span;i<a.length;i++){
				int tmp = a[i];
				int j = i-span;
				while(j>=0 && a[j]>tmp){
					a[j+span] = a[j];
					j -= span;
				}
				a[j+span] = tmp;
			}
		}
	}

方法2：

	public static  void  shell2(Number[] data)
	{
		int span=data.length/7;
		if(span==0)span=1;
		while(span>=1){
			for(int i=0;i<span;i++){
				for(int j=i;j<data.length;j=j+span){
					//组内直接插入排序	
					int p = j-span;
					Number temp = data[j];
					while( p >=0 && data[p].doubleValue() > temp.doubleValue()){
						data[p+span] = data[p];
						p -=span;
					}
					data[p + span] = temp;
				}
			}
			span=span/2;
		}
	}

方法1和2的微妙之处，至于1是在span之内先增加i,遇到块便向后查询
2是先循环一个块上的数据来排序，然后在span之内在递增
二者最外层都是在缩小span；
解释的不是很清楚，需要阅读代码
其他：

归并排序

/** 
	* 分治和归并 
	* @param a 
	* @param low 
	* @param high 
	* @param b 
	*/ 
    public static void mergeSort(int a[],int low,int high,int b[]){
    	int mid;
    	if(low<high){
    		mid = (low+high)/2;//分治位置 
    		mergeSort(a, low, mid, b);
    		mergeSort(a,mid+1,high,b);
    		merge(a,low,mid,high,b);//归并 
    	}
    }
    
    
    /** 
     * 合并两个有序子序列 
     * @param a 
     * @param low 
     * @param mid 
     * @param high 
     * @param b 辅助数组 
     */ 
    public static void merge(int a[],int low,int mid,int high,int b[]){
    	int i = low;
    	int j = mid+1;
    	int p = 0;
    	while(i<=mid&&j<=high){
    		b[p++] = (a[i]<=a[j])?a[i++]:a[j++];
    	}
    	//如果子序列1没有合并完则直接复制到辅助数组中去 
    	//复制low mid段未被copy的部分
    	while(i<=mid){
    		b[p++] = a[i++];
    	}
    	//如果子序列2没有合并完则直接复制到辅助数组中去 
    	//复制mid+1 high段未被copy的部分
    	while(j<=high){
    		b[p++] = a[j++];
    	}
    	
    	//把辅助数组的元素复制到原来的数组中去 
    	//复制b[0 ~ p-1]到a[low ~ high]
    	for(p=0,i=low;i<=high;i++,p++){
    		a[i] = b[p];
    	}
    }

基数排序

暂无



本文参照了网上一些文章，对此如有版权问题，请与我联系，放在这里主要是为了共同学习。