排序算法

 /**
 * 排序算法总结（冒泡排序、选择排序、插入排序、快速排序）
 * 
 * @author bruce
 *
 */
public class Sort {
	
	
	/**
	 * 冒泡排序
	 * 
	 * 每一趟不停的比较交换出最大值放在数组尾部
	 * @param arr
	 */
	public void bubbleSort(int[] arr){
		for(int i=arr.length-1;i>=0;i--){
			for(int j=0;j<i;j++){
				if(arr[j]>arr[j+1]){
					int temp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}
			}
		}
	}
	
	
	
	/**
	 * 选择排序
	 * 
	 * 和冒泡排序类似，只是选择排序只比较并记录最大值，最后再交换
	 * @param arr
	 */
	public void selectionSort(int[] arr){
		for(int i=0;i<=arr.length-1;i++){
			int temp=i;
			for(int j=i+1;j<=arr.length-1;j++){
				if(arr[j]<arr[temp]){
					temp=j;
				}
			}
			if(i!=temp){
				int t=arr[i];
				arr[i]=arr[temp];
				arr[temp]=t;
			}
		}
	}
	
	
	/**
	 * 插入排序
	 * 
	 * 遍历数组的过程中，保持数组前面部是有序的，然后不停的将当前值插入到有序数组中。
	 * @param arr
	 */
	public void insertSort(int[] arr){
		for(int i=1;i<arr.length;i++){
			int temp=arr[i];
			int t=i;
			while(t>0 && arr[t-1]>temp){
				arr[t]=arr[t-1];
				t--;
			}
			arr[t]=temp;
		}
	}
	
	
	/**
	 * 快速排序(一趟)
	 * 
	 * 选定第一个元素作标准，从后面遍历比较，比此元素小时就交换，从前面遍历比较，比此元素大时就交换。
	 * @param arr
	 * @param begin
	 * @param end
	 * @return
	 */
	private int quickSort(int arr[],int begin,int end){
		int temp=arr[begin];
		while(begin<end){
			while(begin<end && arr[end]>=temp){
				end--;
			}
			if(begin<end){
				arr[begin++]=arr[end];
			}
			while(begin<end && arr[begin]<=temp){
				begin++;
			}
			if(begin<end){
				arr[end--]=arr[begin];
			}
		}
		
		arr[begin]=temp;
		return begin;
	}
	
	
	/**
	 * 快速排序
	 * 
	 * 递归排序
	 * 
	 * 在大多数情况下，该算法的排序是最快的，快速排序也因此而得名。
	 * @param arr
	 * @param begin
	 * @param end
	 */
	public void qSort(int arr[],int begin,int end){
		if(begin<end){
			int t=quickSort(arr,begin,end);
			qSort(arr,begin,t-1);
			qSort(arr,t+1,end);
		}
	}
	
	
	public static void main(String[] args){	
		int[] arr={2,1,5,3,7,4,9,5,6};
		Sort sort=new Sort();
		// sort.bubbleSort(arr);
		// sort.selectionSort(arr);
		// sort.insertSort(arr);
		 sort.qSort(arr, 0, arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
	
}

 

 

 

 

 

 

1：冒泡排序效果图：

 

 

 

 

 

 

 

 

2：选择排序效果图

 

 

 

 

 

3:插入排序效果图

 

 

 

 

4：快速排序效果图

 

 

 

评论

2 楼 xieyaxiong 2012-08-23  

songbin0201 写道

整篇文章的精华在那些gif图片上

这话说得可不爱听了 人家可是花了一天写的程序 三分钟到网上找的图片 

1 楼 songbin0201 2012-08-23  

整篇文章的精华在那些gif图片上