七种排序

package com.xxa;

public class Paixu {
	//1.冒泡排序(找出每轮比较的最大的数,往上冒)
	public void maopao(int a[]){
		for (int i = 0; i < a.length-1; i++) {
			for (int j = 0; j < a.length-i-1; j++) {
				if (a[j]>a[j+1]) {
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
				}
			}
		}
	}+0

	//2.选择排序(每轮找出最小的对号入座)
	public void xuanzepaixu(int[] a){
		for (int i = 0; i < a.length; i++) {
			for (int j = i+1; j < a.length; j++) {
				if (a[i]>a[j]) {
					int temp=a[i];
					a[i]=a[j];
					a[j]=temp;
				}
			}
		}
	}

	//3.快速排序(定一个中间值,使这个值大于它左边的数,小于它右边的数)
	public void kuaiPaiXu(int sort[]){
		kuaiPaiXu0(sort, 0, sort.length-1);
	}
	public void kuaiPaiXu0(int sort[],int left,int right){
		int i=left;
		int j=right;
		int mid=sort[left];
		while (i<j) {
			while (i<j&&mid<sort[j]) {
				j--;
			}
			if (i<j) {
				int temp=sort[i];
				sort[i]=sort[j];
				sort[j]=temp;
			}
			while (i<j&&mid>sort[i]) {
				i++;
			}
			if (i<j) {
				int temp=sort[i];
				sort[i]=sort[j];
				sort[j]=temp;
			}
		}
		if (i>left) {
			kuaiPaiXu0(sort, left, i-1);
		}
		if (j<right) {
			kuaiPaiXu0(sort, j+1, right);
		}
	}

	//4.插入排序1(使一个有序的数组插入一个数到最后位置,再由后往前做比较,如果如果比这个数大就交换位置)
	public void charupaixu1(int a[]){
		for (int i = 1; i < a.length; i++) {
			for (int j = i; j > 0; j--) {
				if (a[j]<a[j-1]) {
					int temp=a[j];
					a[j]=a[j-1];
					a[j-1]=temp;
				} else {
					break;
				}
			}
		}
	}
	//4.插入排序2(使一个有序的数组插入一个数到最后位置,再由前往后查找一个比它大的数的位置插入进去)
	public void charupaixu2(int a[]){
		for (int i = 1; i < a.length; i++) {
			int ren=a[i];
			int room=i;
			for (int j = 0; j < i; j++) {
				if (a[j]>ren) {
					room=j;
					break;
				}
			}
			for (int j = i-1; j >= room; j--) {
				a[j+1]=a[j];
			}
			a[room]=ren;
		}
	}

	//5.希尔排序
	public void xierpaixu(int a[]){
		int step=a.length%2==1&&a.length!=1?a.length/2+1:a.length/2;
		while (step!=0) {
			for (int i = 0; i < a.length-step; i++) {
				for (int j = i; j < a.length-step; j+=step) {
					if (a[j]>a[j+step]) {
						int temp=a[j];
						a[j]=a[j+step];
						a[j+step]=temp;
					}
				}
			}
			step=step%2==1&&step!=1?step/2+1:step/2;
		}
	}

	//6.堆排序
	public void duipaixu(int a[]){
		int sum=a.length-1;
		while (sum>1) {
			//建堆
			for (int i = sum/2; i >= 1; i--) {
				//在父节点a[i]与左孩子a[2*i],左孩子是a[2*i]比大小
				if (2*i<=sum&&a[i]<a[2*i]) {
					int temp=a[i];
					a[i]=a[2*i];
					a[2*i]=temp;
				}
				//在父节点a[i]与右孩子a[2*i+1],右孩子是a[2*i+1]比大小
				if (2*i+1<=sum&&a[i]<a[2*i+1]) {
					int temp=a[i];
					a[i]=a[2*i+1];
					a[2*i+1]=temp;
				}
			}
			//第一个与最后一个交换 a[1]与a[sum]交换
			int she=a[1];
			a[1]=a[sum];
			a[sum]=she;

			sum--;
		}
	}

	//7.基数排序
	public void jisuPaiXu(int sort[]){
		int maxLen=0;
		for (int i = 0; i < sort.length; i++) {
			int len=(sort[i]+"").length();
			if (len>maxLen) {
				maxLen=len;
			}
		}
		Node[] node={new Node(0),new Node(1),new Node(2),new Node(3),new Node(4),
					 new Node(5),new Node(6),new Node(7),new Node(8),new Node(9)};
		int shi=1;
		for (int i = 0; i < maxLen; i++) {
			for (int j = 0; j < sort.length; j++) {
				int yushu=sort[j]/shi%10;
				Node nd=node[yushu];
				while (nd.next!=null) {
					nd=nd.next;
				}
				nd.next=new Node(sort[j]);
			}
			shi*=10;
			int x=0;
			for (int j = 0; j < node.length; j++) {
				Node nd=node[j].next;
				while (nd!=null) {
					sort[x++]=nd.data;
					nd=nd.next;
				}
				node[j].next=null;
			}
		}
	}

}