Java 排序算法总结

1）分类：

1）插入排序（直接插入排序、希尔排序）

2）交换排序（冒泡排序、快速排序）

3）选择排序（直接选择排序、堆排序）

4）归并排序

5）分配排序（箱排序、基数排序）

所需辅助空间最多：归并排序

所需辅助空间最少：堆排序

平均速度最快：快速排序

不稳定：快速排序，希尔排序，堆排序。

 

2）选择排序算法的时候

1.数据的规模 ；  2.数据的类型 ；  3.数据已有的顺序 
一般来说，当数据规模较小时，应选择直接插入排序或冒泡排序。任何排序算法在数据量小时基本体现不出来差距。

考虑数据的类型，比如如果全部是正整数，那么考虑使用桶排序为最优。 

考虑数据已有顺序，快速排序是一种不稳定的排序（当然可以改进），对于大部分排好的数据，快速排序会浪费大量不必要的步骤。数据量极小，而起已经基本排好序，冒泡是最佳选择。我们说快速排序好，是指大量随机数据下，快排效果最理想。而不是所有情况。

 

3）总结：

 

排序方法	平均时间	最坏时间	辅助存储
简单排序	O(n^2)	O(n^2)	O(1)
快速排序	O(n log n)	O(n^2)	O(log n)
堆排序	O(n log n)	O(n log n)	O(1)
归并排序	O(n log n)	O(n log n)	O(n)
基数排序	O(d(n+rd))	O(d(n+rd))	O(rd)

 

——按平均的时间性能来分：
     1）时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；
     2）时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；
     3）时间复杂度为O(n)的排序方法只有，基数排序。
当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
——按平均的空间性能来分（指的是排序过程中所需的辅助空间大小）：
     1） 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；
     2） 快速排序为O(logn )，为栈所需的辅助空间;
     3） 归并排序所需辅助空间最多，其空间复杂度为O(n );
     4）链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。
——排序方法的稳定性能：
     1） 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和 经过排序之后，没有改变。
     2） 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。
     3） 对于不稳定的排序方法，只要能举出一个实例说明即可。
     4） 快速排序，希尔排序和堆排序是不稳定的排序方法。

 

 

 

4）各排序算法分析

 

 （下面的算法除了主程序外，其他方法可以用final 修饰，在java编译时期，可以直接插入到主程序中，提高效率，下面的方法没有声明，只是在这里说明下）

共用方法：

 

/**
	 * 交换元素
	 * @param <AnyType>
	 * @param a
	 * @param fromIndex
	 * @param toIndex
	 */
	private static<AnyType extends Comparable<? super AnyType>>
	void swapReferences(AnyType[]a,int fromIndex,int toIndex){
		AnyType tmp=a[fromIndex];
		a[fromIndex]=a[toIndex];
		a[toIndex]=tmp;
	}

 

 

1、插入排序

   该算法在数据规模小的时候十分高效，该算法每次插入第K+1到前K个有序数组中一个合适位置，K从0开始到N-1,从而完成排序。

 

 

/**
	 * 插入排序
	 * @param <AnyType>
	 * @param a
	 */
	public static<AnyType extends Comparable<? super AnyType>> 
	void insertionSort(AnyType[] a){
		int j;
		for(int p=1;p<a.length;p++){
			//保存需插入的值
			AnyType tmp=a[p];
			//将p位置前的元素（已排序）向左移动，直到它在前p+1个元素前被找到
			for(j=p;j>0&&tmp.compareTo(a[j-1])<0;j--){
				a[j]=a[j-1];
			}
			a[j]=tmp;
		}
	}

 

 

2、希尔排序

   Shell排序可以理解为插入排序的变种，它充分利用了插入排序的两个特点：
1）当数据规模小的时候非常高效
2）当给定数据已经有序时的时间代价为O(N)
   所以，Shell排序每次把数据分成若个小块，来使用插入排序，而且之后在这若个小块排好序的情况下把它们合成大一点的小块，继续使用插入排序，不停的合并小块，知道最后成一个块，并使用插入排序。

这里每次分成若干小块是通过“增量” 来控制的，开始时增量交大，接近N/2,从而使得分割出来接近N/2个小块，逐渐的减小“增量“最终到减小到1。

   一直较好的增量序列是2^k-1,2^(k-1)-1,.....7,3,1,这样可使Shell排序时间复杂度达到O(N^1.5)，所以我在实现Shell排序的时候采用该增量序列。

 

	/**
	 * 希尔排序（也叫缩减增量排序）
	 * 选取增量序列有关
	 * 它通过比较相距一定间隔的元素（用插入排序进行排序）来工作，各趟比较所用的距离随算法的进行而减小，
	 * 直到比较间隔为1的元素为止。
	 * 其实希尔排序是多次的插入排序，只是在移动位置的次数上的区别。
	 * @param <AnyType>
	 * @param a
	 */
	public static<AnyType extends Comparable<? super AnyType>>
	void shellSort(AnyType[] a){
		int j;
		//gap 为增量，这里只是选取数组长度的一半，在应用中可适当调整
		for(int gap=a.length/2;gap>0;gap/=2){
			for(int i=gap;i<a.length;i++){
				AnyType tmp=a[i];
				//和插入排序的不同，进入这个循环的次数会减少。因为希尔排序是进行多次插入排序后的部分相对有序
				for(j=i;j>=gap&&tmp.compareTo(a[j-gap])<0;j-=gap){
					a[j]=a[j-gap];
				}				
				a[j]=tmp;
			}
		}
	}

 

 

 

3、归并排序

   算法思想是每次把待排序列分成两部分，分别对这两部分递归地用归并排序，完成后把这两个子部分合并成一个序列。
归并排序借助一个全局性临时数组来方便对子序列的归并，该算法核心在于归并。

 

	/**
	 * 归并排序
	 * 算法的最坏时间是：O(N log N) 占用空间：排序数组容量的两倍
	 * 思想：采用分治法，递归的把数组从中间分成两个数组，最后为两个长度为1的数组，然后进行合并。
	 * 归并排序的运行时间严重依赖于比较元素和在数组（以及临时数组）中移动元素的相对开销，这些开销是和语言有关的。
	 * 在java 中，当执行一次泛型排序（使用Comparator时），进行一次元素比较可能是昂贵的（因为比较可能
	 * 不容易内嵌，从而动态调度的开销可能会减慢执行的速度），但是移动元素则是省时的（因为他们是引用的赋值，
	 * 而不是庞大对象的拷贝（C++ 是对象的拷贝））,归并排序使用所有流行的排序算法中最少的比较次数，
	 * 因此是使用java 的通用排序算法中的上好的选择。事实上，它就是标准java 类库中泛型排序所使用的算法。
	 * @param <AnyType>
	 * @param a
	 */
	public static<AnyType extends Comparable<? super AnyType>>
	void mergeSort(AnyType[] a){
		//合并过程的临时数组（减少了排序消耗的空间）
		AnyType[] tmpArray=(AnyType[])new Comparable[a.length];
		//正式的归并排序开始
		mergeSort(a,tmpArray,0,a.length-1);
	}

/* ------------------ 归并排序私有方法----------------------*/
	/**
	 * 正式的归并排序方法
	 */
	private static<AnyType extends Comparable<? super AnyType>>
	void mergeSort(AnyType[] a,AnyType[] tmpArray,int left,int right){
		//递归的开始
		if(left<right){
			int center=(left+right)/2;
			mergeSort(a,tmpArray,left,center);//归并左边的数组
			mergeSort(a,tmpArray,center+1,right);//归并右边的数组
			merge(a,tmpArray,left,center+1,right);//合并两个数组
		}
	}
	/**
	 * 合并两个数组
	 * @param <AnyType>
	 * @param a 排序数组
	 * @param tmpArray 临时数组
	 * @param leftPos 排序数组的左子数组开始下标（归并的左数组）
	 * @param rightPos 排序数组的右子数组开始下标(归并的右数组)
	 * @param rightEnd 排序数组的右子数组结束下标
	 */
	private static<AnyType extends Comparable<? super AnyType>>
	void merge(AnyType[] a,AnyType[] tmpArray,int leftPos,int rightPos,int rightEnd){
		int leftEnd=rightPos-1;
		int tmpPos=leftPos;
		int numElements=rightEnd-leftPos+1;
		//合并比较的开始
		while(leftPos<=leftEnd&&rightPos<=rightEnd){
			if(a[leftPos].compareTo(a[rightPos])<=0)
				tmpArray[tmpPos++]=a[leftPos++];
			else
				tmpArray[tmpPos++]=a[rightPos++];
		}
		//复制剩余的左子数组
		while(leftPos<=leftEnd)
			tmpArray[tmpPos++]=a[leftPos++];
		//复制剩余的右子数组
		while(rightPos<=rightEnd)
			tmpArray[tmpPos++]=a[rightPos++];
		//把临时数组的值重新复制到排序数组
		for(int i=0;i<numElements;i++,rightEnd--)
			a[rightEnd]=tmpArray[rightEnd];
	}

 

 

4、堆排序

   堆是一种完全二叉树，一般使用数组来实现。
   堆主要有两种核心操作，
1）从指定节点向上调整(上滤)(percUp)
2）从指定节点向下调整(下滤)(percDown)
   建堆，以及删除堆定节点使用shiftDwon,而在插入节点时一般结合两种操作一起使用。
   堆排序借助最大值堆来实现，第i次从堆顶移除最大值放到数组的倒数第i个位置，然后shiftDown到倒数第i+1个位置,一共执行N此调整，即完成排序。
   显然，堆排序也是一种选择性的排序，每次选择第i大的元素。

 

	/**
	 * 堆排序
	 * 思想：第一步以线性时间建立一个堆，然后通过每次将堆中的最后元素与第一个元素交换，
	 * 执行N-1次deleteMax 操作，每次将堆的大小缩减1并进行下滤，
	 * 当算法终止时，数组则以排好的顺序包含这些元素。
	 * @param <AnyType>
	 * @param a
	 */
	public static<AnyType extends Comparable<? super AnyType>>
	void heapSort(AnyType[] a){
		//创建堆
		for(int i=a.length/2;i>=0;i--)
			percDown(a,i,a.length);
		//删除最大的元素
		for(int i=a.length-1;i>0;i--){
			swapReferences(a,0,i);
			percDown(a,0,i);
		}
	}

/* ------------------ 堆排序私有方法----------------------*/
	/**
	 * 返回左孩子
	 * @param i
	 * @return
	 */
	private static int leftChild(int i){
		return 2*i+1;
	}
	/**
	 * 堆的下滤操作
	 * @param <AnyType>
	 * @param a
	 * @param i
	 * @param n
	 */
	private static<AnyType extends Comparable<? super AnyType>>
	void percDown(AnyType[] a,int i,int n){	
		int child;
		AnyType tmp;//保留父节点值
		//目的是比较它和它两个孩子，找到三个中最大的替换成相应两个的父节点
		for(tmp=a[i];leftChild(i)<n;i=child){			
			child=leftChild(i);
			//如果左孩子<右孩子 ，则把child指向右孩子
			if(child!=n-1&&a[child].compareTo(a[child+1])<0)
				child++;
			//如果孩子比父节点大，则替换之
			if(tmp.compareTo(a[child])<0)
				a[i]=a[child];
			else
				break;
		}
		a[i]=tmp;
	}

 

 

5、快速排序

   快速排序是目前使用可能最广泛的排序算法了。
一般分如下步骤：
1）如果子数组中元素的个数为0或者1，则返回。
2）选择一个枢纽元素（有很多选法，好的枢纽元素，能有效提高排序效率，这里的实现里采用三数中值分割法）。
3）使用该枢纽元素分割数组，使得比该元素小的元素在它的左边，比它大的在右边。并把枢纽元素放在合适的位置。
4）根据枢纽元素最后确定的位置，把数组分成三部分，左边的，右边的，枢纽元素自己，对左边的，右边的分别递归调用快速排序算法即可。
   快速排序的核心在于分割算法，也可以说是最有技巧的部分。
三数中值分割法：选取相应数组最左边、中间和最右边值，选取三个中的中间值作为枢纽元素。且在这里用了个取巧的办法，把最大的放在最右边，最小的放在最左边，中间值放在right-1的位置，以后分割的时候就可以不去管这三个值了。
分割算法：由于三数中值法已经把right和right-1的 位置排好，i ong 一个元素开始，j  right-1 位置开始，分别和枢纽元素比较，i>枢纽元素 停止，j<枢纽元素 停止，然后交换两个值。i>=j 时候结束。

	/**
	 * 快速排序
	 * 关键在于选取好枢纽元
	 * @param <AnyType>
	 * @param a
	 */
	public static<AnyType extends Comparable<? super AnyType>>
	void quickSort(AnyType[] a){
		quickSort(a,0,a.length-1);
	}
	/* ------------------ 快速排序私有方法----------------------*/
	/**
	 * 真正快速排序方法
	 * @param <AnyType>
	 * @param a
	 * @param left
	 * @param right
	 */
	public static<AnyType extends Comparable<? super AnyType>>
	void quickSort(AnyType[] a,int left,int right){
		if(left<right){
			AnyType pivot=median3(a,left,right);//选取枢纽元素，好的枢纽元素能有效提高算法的效率
			int i=left,j=right-1;
			for(;;){
				while(a[++i].compareTo(pivot)<0){}//i索引移动到大于枢纽元的位置停止
				while(a[--j].compareTo(pivot)>0){}//j索引移动到小于枢纽元的位置停止
				if(i<j)
					swapReferences(a,i,j);//交换停止后的i、j 索引上的值
				else
					break;
			}
			if(i!=right)
				swapReferences(a,i,right-1);//恢复枢纽元素的值到正确的位置
			quickSort(a,left,i-1);//递归左数组
			quickSort(a,i+1,right);//递归右数组
			
		}else{
			return;
		}
		
		
	}
	/**
	 * 三数中值分割法，选取三个值中的中间值，并排序
	 * @param <AnyType>
	 * @param a
	 * @param left
	 * @param right
	 * @return
	 */
	public static<AnyType extends Comparable<? super AnyType>>
	AnyType median3(AnyType[] a,int left,int right){
		int center=(left+right)/2;
		//下面是把最左边、中间位置、最右边的元素进行排序
		if(a[center].compareTo(a[left])<0)
			swapReferences(a,left,center);
		if(a[right].compareTo(a[left])<0)
			swapReferences(a,left,right);
		if(a[right].compareTo(a[center])<0)
			swapReferences(a,center,right);
		//把枢纽元素放在最右边的倒数第二个
		swapReferences(a,center,right-1);
		return a[right-1];
	}

 

6、冒泡排序

    这可能是最简单的排序算法了，算法思想是每次从数组末端开始比较相邻两元素，把第i小的冒泡到数组的第i个位置。i从0一直到N-1从而完成排序。（当然也可以从数组开始端开始比较相邻两元素，把第i大的冒泡到数组的第N-i个位置。i从0一直到N-1从而完成排序。)

	/**
	 * 冒泡排序
	 * @param <AnyType>
	 * @param a
	 */
	public static<AnyType extends Comparable<? super AnyType>> 
	void bubbelSort(AnyType[] a){
		for(int i=0;i<a.length;i++){
			for(int j=i;j<a.length;j++){
				if(a[i].compareTo(a[j])>0){
					swapReferences(a, i, j);
				}
			}
		
		}
	}

 

 

7、选择排序

    选择排序相对于冒泡来说，它不是每次发现逆序都交换，而是在找到全局第i小的时候记下该元素位置，最后跟第i个元素交换，从而保证数组最终的有序。
    相对与插入排序来说，选择排序每次选出的都是全局第i小的，不会调整前i个元素了。

 

/**
	 * 选择排序
	 * @param <AnyType>
	 * @param a
	 */
	public static<AnyType extends Comparable<? super AnyType>> 
	void selectSort(AnyType[] a){
		for(int i=0;i<a.length;i++){
			int smallest=i;//记录最小的索引
			for(int j=i;j<a.length;j++){
				//如果比最小的索引的值还小，则记录在smallest中
				if(a[smallest].compareTo(a[j])>0)
					smallest=j;
			}
			//替换
			swapReferences(a, smallest,i);
		}
	}

 

 

（下面两个算法的程序由于未能理解所以尚未给出，等过几天补上）
 

8、桶式排序

    桶式排序不再是基于比较的了，它和基数排序同属于分配类的排序，这类排序的特点是事先要知道待排序列的一些特征。
   桶式排序事先要知道待排序列在一个范围内，而且这个范围应该不是很大的。
比如知道待排序列在[0,M）内，那么可以分配M个桶，第I个桶记录I的出现情况，最后根据每个桶收到的位置信息把数据输出成有序的形式。
   这里我们用两个临时性数组，一个用于记录位置信息，一个用于方便输出数据成有序方式，另外我们假设数据落在0到MAX,如果所给数据不是从0开始，你可以把每个数减去最小的数。

 

   下面的程序只是简单的用了int 数组来写，如果用其他的Comparable 子类也可以，不过麻烦了点，但原理是一样的 。

还有下面计算重复的值的时候用了个取巧的办法，程序也可以用链式桶式排序来写，即每个桶位为一个链表，当遇到重复的时候，排序桶上面的链表，再输出就行了。

 

	public static void bucketSort(int[] keys,int max){ 
		int[] temp=new int[keys.length];//创建临时数组
		int[] count=new int[max];//创建桶
		//进桶，如果有重复的，那桶里的值为重复的次数
		for(int i=0;i<keys.length;i++){
			count[keys[i]]++;
		}
		//计算keys 数组的索引值，keys数组索引值和前面count索引相加的值是相同的，重复的除外，但下面的方法也计算了重复的值
		for(int i=1;i<max;i++){
			count[i]=count[i]+count[i-1];
		}	
		//复制数组
		System.arraycopy(keys, 0, temp, 0, keys.length);
		//根据上一个for 循环计算的索引值进行计算，当遇到重复值的时候，--count[temp[k]]起了作用。
		for(int k=keys.length-1;k>=0;k--){
			keys[--count[temp[k]]]=temp[k];
		}
	}

 

 

 

9、基数排序

   基数排序可以说是扩展了的桶式排序，比如当待排序列在一个很大的范围内，比如0到999999内，那么用桶式排序是很浪费空间的。而基数排序把每个排序码拆成由d个排序码，比如任何一个6位数（不满六位前面补0）拆成6个排序码，分别是个位的，十位的，百位的。。。。
  排序时，分6次完成，每次按第i个排序码来排。
一般有两种方式:
1) 高位优先(MSD)： 从高位到低位依次对序列排序
2）低位优先(LSD)： 从低位到高位依次对序列排序
  计算机一般采用低位优先法（人类一般使用高位优先），但是采用低位优先时要确保排序算法的稳定性。
  基数排序借助桶式排序，每次按第N位排序时，采用桶式排序。对于如何安排每次落入同一个桶中的数据有两种安排方法：
1）顺序存储：每次使用桶式排序，放入r个桶中，，相同时增加计数。
2）链式存储：每个桶通过一个静态队列来跟踪。