当前位置:首页 > 开发 > 编程语言 > Java > 正文

java实现的9种排序

发表于: 2013-04-23   作者:alask2011   来源:转载   浏览次数:
摘要: 交换排序: 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.冒泡排序
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];
    	}
    }


基数排序

暂无



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

java实现的9种排序

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
闲来无事,自己想起上家公司的笔试题就会考冒泡排序,so,自己就试试写了下,分享下了。 实现: 1 p
前面实现了快速排序算法,其实这个算是难点的,如果是无序打乱的,用快速排序比较好。冒泡排序是从
说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都学过,不过几乎全部忘
1)基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成
快速排序 作者:Legend QQ:158067568 快排是分治法的一个应用,快排主要是通过一个设定枢轴,然后
温故而知新,可以为师矣! 经常温故旧的知识,每次都有新的体会,这种感觉真的很好。 对于排序算法
前面实现了快速排序算法,其实这个算是难点的,如果是无序打乱的,用快速排序比较好。冒泡排序是从
前面实现了快速排序算法,其实这个算是难点的,如果是无序打乱的,用快速排序比较好。冒泡排序是从
说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都学过,不过几乎全部忘
说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都学过,不过几乎全部忘
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号