Java常见排序算法

排序可以分为两大类:内排序外排序
  

引用
在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。

内排序有可以分为以下几类:

  (1)、插入排序:直接插入排序、二分法插入排序、希尔排序。

  (2)、选择排序:简单选择排序、堆排序。

  (3)、交换排序:冒泡排序、快速排序。

  (4)、归并排序

  (5)、基数排序


/**
 * 直接插入排序:
 * 先将array中的第一位作为一个有序数列,然后取第二位放入T中,将第二位留出,
 * 然后与第一位比较,如果第一位大的话,将第一位的元素放入留出的第二位中,由于i自减,第一位就放入T中的元素。
 * 然后一次将第二位后的元素取出放入T中,逐个与前面有序的序列中的每个元素比较,通过交换,可以得到最终结果。
 * @author xiaodai
 *
 */
public class InsertionSort {
	public static void main(String[] args) {
		int[] array=new int[]{2,13,1,6,26,11,17};
		/*for (int i = 1; i < array.length; i++) {
			int t=array[i];
			while(i > 0 && t < array[i-1]){
				array[i]=array[i-1];
				i--;
			}
			array[i]=t;
		}*/
		for (int i = 1; i < array.length; i++) {
			int temp=array[i];
			int j;
			for (j = i-1; j >= 0; j--) {
				if(temp < array[j]){
					array[j+1]=array[j];
				}else{
					break;
				}
			}
			array[j+1]=temp;
		}
		for (int i : array) {
			System.out.print(i+" ");
		}
	}
}


/**
 * 二分法排序:
 * 在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们 
 * 中间的那个元素比,如果小,则对前半再进行折半,否则对后半
 * 进行折半,直到left>right,然后再把第i个元素前1位与目标位置之间
 * 的所有元素后移,再把第i个元素放在目标位置上。
 * @author xiaodai
 *
 */
public class DichotomySort {
	public static void main(String[] args) {
		int[] array=new int[]{2,13,1,6,26,11,17};
		for (int i = 0; i < array.length; i++) {
			int start=0;
			int end=i-1;
			int mid=0;
			int temp=array[i];
			while(end>=start){
				mid=(start+end)/2;
				if(temp > array[mid]){
					end=mid-1;
				}else{
					start=mid+1;
				}
			}
			for (int j = i-1; j > end; j--) {
				array[j+1]=array[j];
			}
			array[end+1]=temp;
		}
		for (int i : array) {
			System.out.print(i+" ");
		}
	}
}

/**
 * 希尔排序:
 * 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。
 * 所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;
 * 然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),
 * 即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
 * @author xiaodai
 *
 */
public class ShellSort {
	public static void main(String[] args) {
		int[] array=new int[]{2,13,1,6,26,11,17};
		int group=array.length;
		while(true){
			group=group/2;
			for (int i = 0; i < group; i++) {
				for (int j = i+group; j < array.length; j=j+group) {
					int temp=array[j];
					int k;
					for (k = j-group; k >= 0 && temp < array[k]; k=k-group) {
							array[k+group]=array[k];
					}
					array[k+group]=temp;
				}
			}
			if(group == 1){
				break;
			}
		}
		for (int i : array) {
			System.out.print(i+" ");
		}
	}
}


/**
 * 选择排序:
 * 选择排序是假定第一个为最大,将第一个的下标赋给max,所以外层循环需要array.length-1次,
 * 内层循环从外层循环选取的第一个元素后一位进行比较,选取第一个元素后面最大元素的下标,
 * 使其与外层循环所选元素的下标进行交换,
 * 最后在外层循环通过下标进行数值交换。
 * @author xiaodai
 *
 */
public class Selectionsort {
	public static void main(String[] args) {
		int[] array=new int[]{2,13,1,6,26,11,17};
		for (int i = 0; i < array.length-1; i++) {
			int max=i;
			for (int j = i+1; j < array.length; j++) {
				if(array[max]<array[j]){
					max=j;
				}
			}
			if(max!=i){
				int temp=array[i];
				array[i]=array[max];
				array[max]=temp;
			}
		}
		for (int i : array) {
			System.out.print(i+" ");
		}
	}
}


/**
 * 堆排序:初始时把要排序的数的序列看作是一棵顺序存储的二叉树,
 * 调整它们的存储序,使之成为一个 堆,这时堆的根节点的数最大。
 * 然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。
 * 依此类推,直到只有两个节点的堆,并对 它们作交换,最后得到有n个节点的有序序列。
 * 从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。
 * 所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。
 * @author xiaodai
 *
 */
public class HeapSort {
	public static void main(String[] args) {
		int[] array=new int[]{2,13,1,6,26,11,17};
		int arrayLength=array.length;
		for (int i = 0; i < array.length-1; i++) {
			buildMaxHeap(array, arrayLength-1-i);
			swap(array, 0, arrayLength-1-i);
		}
		for (int i : array) {
			System.out.print(i+" ");
		}
	}
	public static void buildMaxHeap(int[] data, int lastIndex){
		for(int i=(lastIndex-1)/2;i>=0;i--){
			    //k保存正在判断的节点 
			int k=i;
			//如果当前k节点的子节点存在  
			while(k*2+1<=lastIndex){
			    //k节点的左子节点的索引 
			    int biggerIndex=2*k+1;
			    //如果biggerIndex小于lastIndex,即biggerIndex+1代表的k节点的右子节点存在
			    if(biggerIndex<lastIndex){  
			        //若果右子节点的值较大  
			        if(data[biggerIndex]<data[biggerIndex+1]){  
			            //biggerIndex总是记录较大子节点的索引  
			            biggerIndex++;  
			        }  
			    }  
			    //如果k节点的值小于其较大的子节点的值  
			    if(data[k]<data[biggerIndex]){  
			        //交换他们  
			        swap(data,k,biggerIndex);  
			        //将biggerIndex赋予k,开始while循环的下一次循环,重新保证k节点的值大于其左右子节点的值  
			        k=biggerIndex;  
			    }else{  
			        break;  
			    }  
			}
		}
	}
	public static void swap(int[] data, int i, int j){
		int temp=data[i];
		data[i]=data[j];
		data[j]=temp;
	}
}


/**
 * 冒泡排序:
 * 进行冒泡排序需要从数组的开始元素开始,依次两两比较,这就需要比较length-1次(只有0~length-2需要比较,
 * length-1不需要比较)。所以外层循环需要array.length-1次。
 * 外层循环进行每次比较都会排除一个最大或者最小值,所以内层循环只需要比较j < array.length-1-i次。
 * 在进行比较的时候,两两交换(次序可以有小到大,也可以由大到小)。
 * @author xiaodai
 *
 */
public class BubbleSort {
	public static void main(String[] args) {
		int[] array=new int[]{2,13,1,6,26,11,17};
		for (int i = 0; i < array.length-1; i++) {
			for (int j = 0; j < array.length-1-i; j++) {
				if(array[j]>array[j+1]){
					int temp=array[j];
					array[j]=array[j+1];
					array[j+1]=temp;
				}
			}
		}
		for (int i : array) {
			System.out.print(i+" ");
		}
	}
}


/**
 * 快速排序:选择一个基准元素,通常选择第一个元素或者最后一个元素,
 * 通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,
 * 此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
 * @author xiaodai
 *
 */
public class QuickSort {
	public static void main(String[] args) {
		int[] array=new int[]{2,13,1,6,26,11,17};
		qs(array, 0, array.length-1);
		for (int i : array) {
			System.out.print(i+" ");
		}
	}
	public static void qs(int[] data, int left, int right){
        if(left < right){
                int key = data[left];
                int low = left;
                int high = right;
                while(low < high){
                        while(low < high && data[high] > key){
                                high--;
                        }
                        data[low] = data[high];
                        while(low < high && data[low] < key){
                                low++;
                        }
                        data[high] = data[low];
                }
                data[low] = key;
                qs(data,left,low-1);
                qs(data,low+1,right);
        }
    }
}


/**
 * 归并排序:
 * 将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。
 * 然后再把有序子序列合并为整体有序序列。
 * @author xiaodai
 *
 */
public class MergeSort {
	public static void main(String[] args) {
		int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
		    mergeSort(a,0,a.length-1);
		    System.out.println();
		    System.out.println("排序之后:");
		    for (int i = 0; i < a.length; i++) {
		        System.out.print(a[i]+" ");
		    }
	}
	private static void mergeSort(int[] a, int left, int right) {
		    if(left<right){
		        int middle = (left+right)/2;
		        //对左边进行递归
		        mergeSort(a, left, middle);
		        //对右边进行递归
		        mergeSort(a, middle+1, right);
		        //合并
		        merge(a,left,middle,right);
		    }
		}
		
		private static void merge(int[] a, int left, int middle, int right) {
		    int[] tmpArr = new int[a.length];
		    int mid = middle+1; //右边的起始位置
		    int tmp = left;
		    int third = left;
		    while(left<=middle && mid<=right){
		        //从两个数组中选取较小的数放入中间数组
		        if(a[left]<=a[mid]){
		            tmpArr[third++] = a[left++];
		        }else{
		            tmpArr[third++] = a[mid++];
		        }
		    }
		    //将剩余的部分放入中间数组
		    while(left<=middle){
		        tmpArr[third++] = a[left++];
		    }
		    while(mid<=right){
		        tmpArr[third++] = a[mid++];
		    }
		    //将中间数组复制回原数组
		    while(tmp<=right){
		        a[tmp] = tmpArr[tmp++];
		    }
		}
}


/**
 * 基数排序:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。
 * 然后,从最低位开始,依次进行一次排序。
 * 这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
 * @author xiaodai
 *
 */
public class RadixSort {
	public static void main(String[] args) {
		    int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
		    //基数排序
		    sort(a);
		    System.out.println("排序之后:");
		    for (int i = 0; i < a.length; i++) {
		        System.out.print(a[i]+" ");
		    }
		}
		
		private static void sort(int[] array) {
		    //找到最大数,确定要排序几趟
		    int max = 0;
		    for (int i = 0; i < array.length; i++) {
		        if(max<array[i]){
		            max = array[i];
		        }
		    }
		    //判断位数
		    int times = 0;
		    while(max>0){
		        max = max/10;
		        times++;
		    }
		    //建立十个队列
		    List<ArrayList> queue = new ArrayList<ArrayList>();
		    for (int i = 0; i < 10; i++) {
		        ArrayList queue1 = new ArrayList();
		        queue.add(queue1);
		    }
		    //进行times次分配和收集
		    for (int i = 0; i < times; i++) {
		        //分配
		        for (int j = 0; j < array.length; j++) {
		            int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
		            ArrayList queue2 = queue.get(x);
		            queue2.add(array[j]);
		            queue.set(x,queue2);
		        }
		        //收集
		        int count = 0;
		        for (int j = 0; j < 10; j++) {
		            while(queue.get(j).size()>0){
		                ArrayList<Integer> queue3 = queue.get(j);
		                array[count] = queue3.get(0);
		                queue3.remove(0);
		                count++;
		            }
		        }
		    }
	}
}


本页内容版权归属为原作者,如有侵犯您的权益,请通知我们删除。

迭代器学习(转) - 2016-09-25 16:09:33

迭代器(Iterator) 迭代器是一种设计模式,它是一个对象,它可以遍历并选择序列中的对象,而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象,因为创建它的代价小。 Java中的Iterator功能比较简单,并且只能单向移动: (1) 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时,它返回序列的第一个元素。注意:iterator()方法是java.lang.Iterable接口,被Collection继承。 (2) 使用nex
转自: http://blog.csdn.net/luanlouis/article/details/41576373?utm_source=tuicoolutm_medium=referral   HashMap在Java开发中有着非常重要的角色地位,每一个Java程序员都应该了解HashMap。     本文主要从源码角度来解析HashMap的设计思路,并且详细地阐述HashMap中的几个概念,并深入探讨HashMap的内部结构和实现细节,讨论HashMap的性能问题,并且在文中贯穿着一些关于Hash

波浪文字 - 2016-09-25 14:09:08

最近写了一段波浪文字代码 /* dkplus专业搜集和编写实用电脑软件教程,搜集各种软件资源和计算机周边(java网络编程,seo网站优化,web开发,lnmp,java网络编程,毕业论文设计),独立制作视频和ppt和音频微信公众号,点击进入 dkplus官方博客http://dkplus.iteye.com 微信搜索dkplus关注公众号可获取海量计算机周边资源。 */ import java.awt.*;import java.applet.*;//Download by http://www.cod
一 自动类型转换 1 自动类型转换图   数范围小的向数范围大的进行自动类型转换,如同把小瓶的水倒入大瓶,不会有任何问题。Java支持自动类型转换。 2 代码示例 public class AutoConversion{public static void main(String[] args){int a = 6;// int可以自动转换为float类型float f = a;// 下面将输出6.0System.out.println(f);// 定义一个byte类型的整数变量byte b = 9;//
深刻理解IdentityHashMap: http://donald-draper.iteye.com/blog/2326264 方法说明: public staticK,V MapK,V unmodifiableMap(Map?extendsK,?extendsVm) 返回指定映射的不可修改视图。此方法允许模块为用户提供对内部映射的“只读”访问。 在返回的映射上执行的查询操作将“读完”指定的映射。试图修改返回的映射 (不管是直接修改还是通过其collection视图进行修改)将导致抛出Unsupporte

storm部署详细步骤 - 2016-09-24 19:09:04

1.修改主机名: vim /etc/sysconfig/network NETWORKING=yes HOSTNAME=MASTER   2.修改IP: vim /etc/sysconfig/network-scripts/ifcfg-eth0 BOOTPROTO="static" HWADDR="00:0C:29:FC:62:B6" IPV6INIT="yes" NM_CONTROLLED="yes" ONBOOT="yes" TYPE="Ethernet" UUID="d0731a46-36df-4a
①前端接收enum时,将它放入一个容器script type="text/javascript"var App = {};App.module = 'merchantManage';App.mydata = {"data":[#{list items:memberStatus, as:'status'}{'title':'${status?.title}','name':'${status}'},#{/list}#{list items:memberOperationTypes, as:'target'}
多线程使用的主要目的在于: 1、吞吐量:你做WEB,容器帮你做了多线程,但是他只能帮你做请求层面的。简单的说,可能就是一个请求一个线程。或多个请求一个线程。如果是单线程,那同时只能处理一个用户的请求。 2、伸缩性:也就是说,你可以通过增加CPU核数来提升性能。如果是单线程,那程序执行到死也就利用了单核,肯定没办法通过增加CPU核数来提升性能。 鉴于你是做WEB的,第1点可能你几乎不涉及。那这里我就讲第二点吧。 --举个简单的例子: 假设有个请求,这个请求服务端的处理需要执行3个很缓慢的IO操作(比如数据库

博客搬家咯 - 2016-09-24 14:09:07

博客搬家了,最新地址: http://blog.uyiplus.com

关于java的10个谎言 - 2016-09-24 14:09:07

关于java的10个谎言 面试中总遇到各种奇葩的问题,小编在兄弟连网站上找到了下面的这些都算是比较高级的问题了,面试中一般也很少问到,因为它们可能会把面试者拒之门外。不过你可以自己找个时间来实践一下。 1. System.exit(0)会跳过finally块的执行 System.setSecurityManager(new SecurityManager() {         @Override         public void checkExit(int status) {