常用排序算法

生活中常用的排序算法：冒泡排序、插入排序、快速排序

package com.tao.bao;


/**
 * @author Administrator
 *
 */
public class SortAll {

	/**
	 * @param args
	 * 插入排序
	 */
	public int[] insertionSort(int[] arr){
		int j;
		for(int p=1;p<arr.length;p++){
			int tmp=arr[p];
			for(j=p;j>0&&arr[j-1]>tmp;j--)	
			{
				arr[j]=arr[j-1];
			}
			 arr[j]=tmp;
		}
		return arr;
	}
	
	/**
	 * ，冒泡排序
	 * @param arr
	 * @return
	 */
	public int[] maoPaoSort(int[] arr){
		for(int i=0;i<arr.length;i++){
		   for(int j=0;j<arr.length-i-1;j++){
			   if(arr[j]>arr[j+1])
			   {
				   int tmp = arr[j];
				   arr[j]=arr[j+1];
				   arr[j+1]=tmp;
			   }
		   }
		}
		return arr;
	}
	
	/*
	 * 快速排序
	 */
	public int partition(int[] arr,int left,int right){
		int x = arr[right]; //选取最后一个元素为主元，算法导论中算法
		int i = left-1;
		for(int j=left;j<right;j++){
			if(arr[j]<=x){
				i=i+1;
				swap(arr,i,j);
			}
		}
		swap(arr,i+1, right);
		return i+1;
		
	}
	
	public int[] quicksort(int[] arr,int left,int right){
		if(left<right){
			int q = partition(arr, left, right);//关键
			quicksort(arr, left, q-1);
			quicksort(arr, q+1, right);
			return arr;
		}
		return null;	
	}
	
	public static void swap(int arr[],int a,int b){
		int temp = 0;
		 temp = arr[a];
		 arr[a] =arr[b];
		 arr[b] = temp;
	}
	

	
	public static void main(String[] args) {
		SortAll all = new SortAll();
		int arr[] = {2,8,7,1,3,5,6,4};
		int newarr1[] = all.insertionSort(arr);
		System.out.println("insertionSort方法");
		for(int i=0;i<newarr1.length;i++){
			System.out.print(newarr1[i]+" ");
		}
		System.out.println();
		int newarr[] = all.maoPaoSort(arr);
		System.out.println("maoPaoSort方法");
		for(int i=0;i<newarr.length;i++){
			System.out.print(newarr[i]+" ");
		}
		System.out.println();
		
		int arrquick[] = all.quicksort(arr, 0, arr.length-1);
		System.out.println("arrquick方法");
		for(int i=0;i<arrquick.length;i++){
			System.out.print(arrquick[i]+" ");
		}
		System.out.println();
	}

}