欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java实现的9种排序

程序员文章站 2024-01-25 18:25:28
...
交换排序:
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];
    	}
    }


基数排序

暂无



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