package SimpleSort;

public class SimpleSort {
	/**
	 * 冒泡排序：每次循环过程中，小的排在后面的数会像水中的
	 * 气泡一样慢慢往上冒，所以命名为冒泡排序了，我猜是这样子的.....
	 */
	public void BubbleSort(int[] array){
		for(int i=0;i<array.length;i++){
			for(int j=array.length-1;j>i;j--){//注意此处j是从后往前循环
				if(array[j-1]>array[j]){//如果前面的数比其后面的数要大，则交换他们两个的位置
					swap(array,j);
				}
			}
		}
	}
	
	/**
	 * 简单选择排序：基本思想为从第一个数开始，每次选择其后面比他小
	 * 的最小的数与其交换位置
	 * @param array
	 */
	public void SelectSort(int[] array){
		int min;
		for(int i=0;i<array.length-1;i++){
			min=i;
			for(int j=i+1;j<=array.length-1;j++){//选择数组array中i后面的比
				                                //array[i]小的最小的数，并将其下标保存在min中
				if(array[min]>array[j]){
					min=j;
				}
			}
			
			if(min!=i){
				swap(array,i,min);
			}
		}
	}
	
	/**
	 * 直接插入排序:直接插入排序的思想类似于我们日常生活中斗地主时不断摸牌、整理排的过程
	 * 后面摸上来的扑克牌我们都会按照其牌面点数从小到大的插入到对应的位置
	 * @param array
	 */
	public void InsertSort(int[] array){
		int i,j,temp;
		for(i=1;i<array.length;i++){
			if(array[i]<array[i-1]){
				temp=array[i];
				for(j=i-1;j>=0&&array[j]>temp;j--){//注意不要忽略j>=0,否则肯能出现j=-1,造成数组越界
					array[j+1]=array[j];
				}
				array[j+1]=temp;
			}
		}
	}
	
	//交换
	public void swap(int array[],int i,int j){
		int temp=array[i];
		array[i]=array[j];
		array[j]=temp;
	}
	
	//交换
	public void swap(int array[],int j){
		int temp=array[j-1];
		array[j-1]=array[j];
		array[j]=temp;
	}
}

Java数据结构系列之——简单排序：冒泡、简单选择、直接插入