排序算法

public class Sort {

	public static void main(String[] args) {

		int[] values = new int[] { 1, 4, 45, 6, 7, 43, 77, 0, 2, 21, 34, 55, 222, 110 };
		// bubbleSort(values);
		// easySelectSort(values);
		//directInsertSort(values);
		//halfInesrtSort(values);
		//shellSort(values);
		
//		int[] values={1,2,3,3,2,21,5,6,7,78,5,65,8,7,6,6,6,6,6,9,56544,354,32,4,456,8,89,-9,0,3,243,-321,321,-3,-2,21};
		
		
		
		stackSort(values);
		print(values);
	}

	public static void print(int[] values)
	{
		for (int i = 0; i < values.length; i++)
		{
			System.out.print(values[i] + " ");
		}
	}

	// 冒泡排序

	public static void bubbleSort(int[] values)
	{
		int temp = 0;
		for (int i = 0; i < values.length; i++)
		{
			for (int j = 0; j < values.length - i - 1; j++)
			{
				if (values[j] > values[j + 1])
				{
					temp = values[j];
					values[j] = values[j + 1];
					values[j + 1] = temp;
				}
			}
		}
	}

	// 直接插入排序

	public static void directInsertSort(int[] values)
	{
		for (int i = 1; i < values.length; i++)
		{
			int k = values[i];
			int j = i - 1;
			while (j >= 0 && k < values[j])
			{
				values[j + 1] = values[j];
				j--;
			}
			values[j + 1] = k;
		}
	}

	// 简单选择排序

	public static void easySelectSort(int[] values)
	{
		for (int i = 0; i < values.length; i++)
		{
			int min = i;
			for (int j = i + 1; j < values.length; j++)
			{
				if (values[min] > values[j])
					min = j;
			}
			int temp = values[i];
			values[i] = values[min];
			values[min] = temp;
		}
	}
	
	//折半插入排序
	
	public static void halfInesrtSort(int[] values)
	{
		int temp = 0;
		for(int i = 1; i < values.length; i++)
		{
			temp = values[i];
			int smallpoint=0;
			int bigpoint=i-1;
			
			while(bigpoint>=smallpoint){
				int mid=(smallpoint+bigpoint)/2;
				if(temp > values[mid]){
					smallpoint=mid+1;
				}else{
					bigpoint=mid-1;
				}
			}
			
				for(int j=i;j>smallpoint;j--){
					values[j] = values[j-1];
				}
				values[bigpoint+1]=temp;
			}
		}
	
	
	// 希尔排序

	public static void shellSort(int[] values)
	{
		int span = values.length/5;
		if(span==0)span=1;
		while(span>=1){
			for(int i=0;i<span;i++){
				for(int j=i;j<values.length;j=j+span){
				   //组内直接插入排序
					int p = j-span;
					int temp = values[j];
					while( p >=0 && values[p] > temp){
						values[p+span] = values[p];
						p-=span;
						
					}
					values[p + span] = temp;
				}
			}
			span = span/2;
		}
		
	}
	
	//堆排序
	
	public static void stackSort(int[] values)
	{
		int n = values.length;
		for(int i=n/2;i>=0;i--){
			keepHeap(values, n, i);
		}
		//堆顶与最后一个记录交换
		  while(n > 0){
			  swap(values, 0, n-1);
			  //再调整values[0~n-1]为堆
			  keepHeap(values, --n, 0);
		  }
	}
	
	
	private static void keepHeap(int[] a, int n, int i){
		int x = a[i];
		int j = 2 * i + 1;
		while (j <= n - 1){
			if(j < n -1 && a[j] < a[j+1])
				++j;
			if(a[j] > x){
				a[i] = a[j];
			    i = j;
			    j = 2 * i +1;
			} else{
				break;
			}
		}
		a[i] = x;
	}
	
	//交换数组中指定两元素的位置
	
	private static void swap(int[] values, int x, int y)
	{
		int temp = values[x];
		values[x] = values[y];
		values[y] = temp;
		       
	}
	
	
	}