基本的排序算法

插入排序
选择排序
快速排序
。。。。
后续补充

package org.jf.alg.sort;

/**
 * 
 * 数组排序工具类
 * 
 * 数组中不能有空元素
 * 
 * @author junfeng.chen
 *
 */
public class Sorter {
	
	
	/**
	 * 
	 * 选择排序
	 * 算法思想：将待排序的集合分为两部分，一部分为已排序的部分，一部分为未排序部分
	 * 开始时，未排序部分为整个集合，已排序部分为空
	 * 算法步骤：
	 * 每次从待排序的集合中找出最大(或最小)的元素,将该元素与集合中第一个元素交换；此时该
	 * 元素及以前的元素都为排好序的
	 * 
	 * i<-- [0 - size-1]
	 *   j<-- [i+1 - size-1]//未排好序的元素 i-size-1
	 *    find min from [i+1 - size - 1]
	 *   
	 *  exchange min and a[i]  
	 *   
	 * O(n2)
	 * @param objs
	 */
	public static  void selectSort(Comparable [] objs)
	{
		if(objs==null || objs.length<=1)
			return;
		
		for(int i=0;i<objs.length-1;i++)
		{
			Comparable little = objs[i];
			int little_indx = i;
			for(int j=i+1;j<=objs.length-1;j++)
			{
				if(objs[j].compareTo(little)<0)
				{
					little = objs[j];
					little_indx = j;
				}
			}
			if(little_indx != i)
			{
				Comparable tmp = objs[i];
				objs[i] = objs[little_indx];
				objs[little_indx] = tmp;
			}
		}
	}

	
	/**
	 * 
	 * 将数组分成两部分，一部分为已排序不分，另一部分未排序
	 * 开始时，已排序不分为空集合；未排序不分为整个数组
	 * 每次取未排序部分的第一个元素，插入到已排序部分的适当位置
	 * 
	 * 
	 * 插入排序
	 * @param objs
	 */
	public static void insertSort(Comparable objs[])
	{
		
		for(int i=0;i<objs.length;i++)
		{
			Comparable max = objs[i];
			
			for(int j=0;j<i;j++)
			{
				if(objs[j].compareTo(max)>0)//找到位置
				{
					for(int k = i;k>j;k--)//后面的元素 依次后移
					{
						objs[k] = objs[k - 1];
					}
					objs[j]=max;
					break;
				}
			}
		}
		
	}
	
	
	
	/**
	 * 
	 *取首元素作为基准
	 * @param objs
	 * @param start
	 * @param end
	 */
	public static int partition(Comparable objs[],int  start,int end)
	{
		Comparable pivot = objs[start];
		int left = start;
		int right = end;
		while(left < right)
		{
			while(pivot.compareTo(objs[right])<0)
				right --;
			while(left < right &&
					pivot.compareTo(objs[left])>=0)
			{
				left ++ ;
			}
			
			if(left < right)
			{
				Comparable tmp = objs[left];
				objs[left] = objs[right];
				objs[right] = tmp;
			}

		}
		int pos = right;
		objs [start] = objs[pos];
		objs [pos] = pivot;
		
		return pos;
	}
	
	/**
	 * 三数取中 作为基准
	 * @param objs
	 * @param start
	 * @param end
	 * @return
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static int partition2(Comparable objs[],int start,int end)
	{
		int left = start;
		int right = end;
		int mid_indx = (left+right)/2;
		Comparable mid = objs[(left+right)/2];
		if(objs[left].compareTo(mid)<0)
		{
			if(mid.compareTo(objs[right])<=0)
				mid_indx =mid_indx ;//pivot = mid;
			else
			{
				if( objs[left].compareTo(objs[right])>0)
					mid_indx = left;//pivot = objs[left];
				else 
					mid_indx = right;//pivot = objs[right];
			}
		}else
		{
			if(mid.compareTo(objs[right])>=0)
				mid_indx = mid_indx;//pivot = mid;
			else
			{
				if(objs[left].compareTo(objs[right])>=0)
					mid_indx = right;//pivot = objs[right];
				else
					mid_indx = left;//pivot = objs[left];
				
			}
		}
		
		Comparable tp = objs[start];
		objs[start] = objs[mid_indx];
		objs[mid_indx] = tp;
		
		Comparable pivot = objs[start];
		while(left < right)
		{
			while(pivot.compareTo(objs[right])<0)
				right --;
			while(left < right &&
					pivot.compareTo(objs[left])>=0)
			{
				left ++ ;
			}
			
			if(left < right)
			{
				Comparable tmp = objs[left];
				objs[left] = objs[right];
				objs[right] = tmp;
			}
		}
		int pos = right;
		objs [start] = objs[pos];
		objs [pos] = pivot;
		
		return pos;
	}
	
	public static  void quickSort(Comparable objs[],int start,int end)
	{
		if(start >= end)
			return;
		int pos = partition2(objs,start,end);
		quickSort(objs,start,pos -1);
		quickSort(objs,pos+1,end);
	}
	
	/**
	 * 快速排序
	 * 采用3位取中法 定基准
	 * @param objs
	 */
	public static void quickSort(Comparable objs[])
	{
		quickSort(objs,0,objs.length-1);
	}
}