各种排序总结

冒泡排序：

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

 选择排序：

public static void selectSort(int[] input){
	for(int i = 0; i < input.length; i++){
		int index = i;
		for(int j = i+1; j < input.length; j++){
			if(input[index]>input[j]){
				index = j;
			}
		}
		if(index != i){
			int temp = input[i];
			input[i] = input[index];
			input[index] = temp;
		}
	}
}

 shell排序

void shellSort(int[] a){
	int i,j,h;
	int r,temp;
	int x=0;
	for(a.length/2;r>=1;r/=2){
		for(i=r;i<a.length;i++){
			temp=a[i];
			j=i-r;
			while(j>=0&&temp<a[j]){
				a[j+r]=a[j];
				j-=r;
			}
			a[j+r]=temp;
		}
		x++;
	}
}

 快速排序

void quickSort(int[] arr,int left,int right){
	int f,t;
	int rtemp,ltemp;
	
	ltemp=left;
	rtemp=right;
	f=arr[(left+right)/2];
	while(ltemp<rtemp){
		while(arr[ltemp]<f){
			++ltemp;
		}
		while(arr[rtemp]>f){
			--rtemp;
		}
		if(ltemp<=rtemp){
			t=arr[ltemp];
			arr[ltemp]=arr[rtemp];
			arr[rtemp]=t;
			--rtemp;
			++ltemp;
		}
	}
	if(ltemp==rtemp){
		ltemp++;
	}
	if(left<rtemp){
		quickSort(arr,left,ltemp-1);
	}
	if(ltemp<right){
		quickSort(arr,rtemp+1,right);
	}
}

 基数排序：

private static void radixSort(int[] array,int d){
	int n=1;	//代表位数对应的数：1,10,100...
	int k=0;	//保存每一位排序后的结果用于下一位的排序输入
	int length=array.length;
	//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
	int[][] bucket=new int[10][length];
	int[] order=new int[length];//用于保存每个桶里有多少个数字
	while(n < d){
	   for(int num:array){
		   int digit=(num/n)%10;
		   bucket[digit][order[digit]]=num;
		   order[digit]++;
	   }
	  
	   //将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
	   for(int i = 0; i < length; i++){
		   //这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组
		   if(order[i] != 0){
			  for(int j = 0; j < order[i]; j++){
				   array[k] = bucket[i][j];
				   k++;
			  }
		   }
		   order[i]=0;//将桶里计数器置0，用于下一次位排序
	   }
	   n*=10;
	   k=0;//将k置0，用于下一轮保存位排序结果
	}  
}

 计数排序：

/**
 *计数排序：下面博客地址讲解的超级详细
 *http://www.cnblogs.com/kaituorensheng/archive/2013/02/23/2923877.html
 **/
public static void countsort(int[] input, int[] output, int k) {
	// input为输入数组，output为输出数组，k表示有所输入数字都介于0到k之间（包含k）
	int[] c = new int[k];// 临时存储区
	int len = c.length;
	// 初始化
	for (int i = 0; i < len; i++) {
	  c[i] = 0;
	}
	// 检查每个输入元素，如果一个输入元素的值为input[i],那么c[input[i]]的值加1，
   //此操作完成后，c[i]中存放了值为i的元素的个数
	for (int i = 0; i < input.length; i++) {
	  c[input[i]]++;
	}
	
   // 通过在c中记录计数和，c[i]中存放的是小于等于i元素的数字个数
	for (int i = 1; i < len; i++) {
	  c[i] = c[i] + c[i - 1];
	}
	
	// 把输入数组中的元素放在输出数组中对应的位置上
	for (int i = input.length - 1; i >= 0; i--) {// 从后往前遍历
	  output[c[input[i]] - 1] = input[i];
	  c[input[i]]--;// 该操作使得下一个值为input[i]的元素直接进入输出数组中input[i]的前一个位置
	}
}

 归并排序：

public class Test {
	public static void main(String[] args) {
		int[] ia = {4,8,9,5,2,1,4,6};
		mergeSort(ia, 0, ia.length-1);
		for(int i : ia){
			System.out.print(i +" ");
		}
	}
	public static void mergeSort(int[] a, int low, int high){
		if(low < high){
			mergeSort(a, low, (high + low)/2);
			mergeSort(a, (low + high)/2+1, high);
			merge(a,low, (high + low)/2, high);
		}
	}
	//将连个数组合并成一个数组
	public static void merge(int[] a,int p,int q,int r){
		int[] b = new int[r-p+1];
		int s = p;
		int t = q+1;
		int k = 0;
		while(s <= q && t <= r){
			if(a[s] < a[t]){
				b[k++] = a[s++];
			}else{
				b[k++] = a[t++];
			}
		}
		while(s <= q){
			b[k++] = a[s++];
		}
		while(t <= r){
			b[k++] = a[t++];
		}
		for(int i = 0; i < b.length; i++){
			a[p+i] = b[i];
		}
	}
}

 堆排序：

public class MaxHeap {
	int[] heap;
	int heapsize;
	public MaxHeap(int[] array){
	    this.heap=array;    
	    this.heapsize=heap.length;
	}
	public void buildMaxHeap(){
	    for(int i=heapsize/2-1;i>=0;i--){
	        maxify(i);//依次向上将当前子树最大堆化
	    }
	}
	public void heapSort(){
	    for(int i=0;i<heap.length;i++){
	        //执行n次，将每个当前最大的值放到堆末尾
	        int tmp=heap[0];
	        heap[0]=heap[heapsize-1];
	        heap[heapsize-1]=tmp;
	        heapsize--;
	        maxify(0);
	    }
	}
	public void maxify(int i){
	    int l=left(i);
	    int r=right(i);
	    int largest;
	    
	    if(l<heapsize&&heap[l]>heap[i])
	        largest=l;
	    else
	        largest=i;
	    if(r<heapsize&&heap[r]>heap[largest])
	        largest=r;
	    if(largest==i||largest>=heapsize)//如果largest等于i说明i是最大元素 largest超出heap范围说明不存在比i节点大的子女
	        return ;
	    int tmp=heap[i];//交换i与largest对应的元素位置，在largest位置递归调用maxify
	    heap[i]=heap[largest];
	    heap[largest]=tmp;
	    maxify(largest);
	}
	public void increaseValue(int i,int val){
	    heap[i]=val;
	    if(i>=heapsize||i<=0||heap[i]>=val)
	        return;
	    int p=parent(i);
	    if(heap[p]>=val)
	        return;
	    heap[i]=heap[p];
	    increaseValue(p, val);
	}
	private int parent(int i){
	    return (i-1)/2;
	}
	private int left(int i){
	    return 2*(i+1)-1;
	}
	private int right(int i){
	    return 2*(i+1);
	}
}
public class Demo {
	
	public static void main(String[] args){
	    int[] array = new int[]{1,2,3,4,7,8,9,10,14,16};
	    MaxHeap heap = new MaxHeap(array);
	    System.out.println("构造一个堆的结构：");
	    printHeapTree(heap.heap);
	    heap.buildMaxHeap();
	    System.out.println("执行最大堆化后堆的结构：");
	    printHeapTree(heap.heap);
	    heap.heapSort();
	    System.out.println("执行堆排序后数组的内容");
	    printHeap(heap.heap);
	}
	
	/** 打印已经构造好的堆  */
	private static void printHeapTree(int[] array){
	    for(int i = 1; i < array.length; i = i*2){
	        for(int k = i-1; k < 2*(i)-1 && k < array.length; k++){
	            System.out.print(array[k]+" ");
	        }
	        System.out.println();
	    }    
	}
	/** 输出调整好后的堆 */
	private static void printHeap(int[] array){
	    for(int i = 0; i < array.length; i++){
	        System.out.print(array[i]+" ");
	    }
	}
}