package test1;

public class Test {
	/**
	 * 交换数组中两个数
	 * @param nums
	 * @param i
	 * @param j
	 */
	public static void swap(int nums[],int i,int j){
		int temp;
		temp = nums[i];
		nums[i] = nums[j];
		nums[j]=temp;
	}
	/**
	 * 冒泡排序
	 * @param nums
	 */
	public static void bubbleSort(int nums[]){
		for(int i = 0;i<nums.length;i++){
			for(int j = 0;j<nums.length-i-1;j++){
				if(nums[j]>nums[j+1]){
					swap(nums,j,j+1);
				}
			}
		}
	}
	/**
	 * 改进的冒泡排序
	 * @param nums
	 */
	public static void improvedBubbleSort(int nums[]){
		for(int i = 0;i<nums.length;i++){
			boolean isChanged = false;//标记一轮中，是否发生交换
			for(int j = 0;j<nums.length-i-1;j++){
				if(nums[j]>nums[j+1]){
					swap(nums,j,j+1);
					isChanged = true;
				}
			}
			if(!isChanged){//如果没有发生交换，则已经有序，直接结束排序
				break;
			}
		}
	}
	/**
	 * 插入排序
	 * @param nums
	 */
	public static void insertSort(int nums[]){
		int len = nums.length;
		for(int i = 1;i<len;i++){
			if(nums[i]<nums[i-1]){//如果有逆序，则向前找到一个不大于该值的位置，插到它后面
				int temp = nums[i];//保存当前值
				int j;
				//向前寻找
				for(j = i-1;j>=0&&nums[j]>temp;j--){
					nums[j+1] = nums[j];
				}
				nums[j+1] = temp;//赋值
			}
		}
	}
	/**
	 * 引入二分查找的插入排序
	 * @param nums
	 */
	public static void insertBinarySort(int nums[]){
		int len = nums.length;
		for(int i = 1;i<len;i++){
			if(nums[i]<nums[i-1]){//如果有逆序，则向前找到一个不大于该值的位置，插到它后面
				int temp = nums[i];//记录当前值
				int low = 0,h = i-1,mid=0;//二分查找的low,high,mid位置标记
				while(low<=h){
					mid = (low+h)/2;
					if(temp>nums[mid]){//如果当前值大于中间位置的值，则区间改为[mid+1,h]
						low = mid+1;
					}else{//如果当前值小于中间位置的值，则区间改为[low,mid-1]
						h = mid-1;
					}
				}
				//找到位置（就是low）后，从后向前移动数组，以腾出位置
				for(int j = i;j>low;j--){
					nums[j] = nums[j-1];
				}
				nums[low] = temp;//赋值
			}
		}
	}
	/**
	 * 希尔排序
	 * @param nums
	 */
	public static void shellSort(int nums[]){
		int len = nums.length;
		for(int gap = len/2;gap>0;gap/=2){//gap每次减半
			for(int i = 0;i<len;i+=gap){//比较的时候，每隔gap个数比较一次
				int temp = nums[i];//记录当前值
				int j;
				//如果当前值小于前面对应的gap位置的数，则把前面的数赋值到当前位置
				//j-=gap,将索引又移到前面gap处，以便于交换
				for(j = i;j>=gap&&temp<nums[j-gap];j-=gap){
					nums[j] = nums[j-gap];
				}
				//再把当前值赋值到前面的位置，本质就是交换了当前值和前面对应gap位置的数
				nums[j] = temp;
			}
		}
	}
	/**
	 * 选择排序
	 * @param nums
	 */
	public static void selectSort(int nums[]){
		int len = nums.length;
		for(int i = 0;i<len-1;i++){
			int min = i;//记录最小值的位置
			for(int j = i+1;j<len;j++){
				if(nums[j]<nums[min]){//如果有更小的，则更新最小值的位置
					min = j;
				}
			}
			//如果最小值位置改变了（不是i了），则交换，就是将最小值从后面换到前面
			if(min!=i){
				swap(nums,i,min);
			}
		}
	}
	/**
	 * 分而治之，找到划分基准，并交换
	 * @param nums
	 * @param left
	 * @param r
	 * @return
	 */
	public static int partation(int nums[],int left,int r){
		int pv = nums[left];//以最左边的数为基准
		int p = left;//记录基准位置
		//遍历数组，如果小于基准，则与基准交换
		for(int i = p+1;i<=r;i++){
			if(nums[i]<pv){
				p++;//基准前移
				if(p!=i){//如果是基准位置的下一个位置，则不用交换
					swap(nums,p,i);
				}
			}
		}
		//最后，将新的基准的值赋值给最左边
		nums[left] = nums[p];
		nums[p] = pv;//将基准赋值到中间，划分位置
		return p;//返回划分位置
	}
	/**
	 * 快速排序
	 * @param nums
	 * @param left
	 * @param r
	 */
	public static void quickSort(int nums[],int left,int r){
		if(left<r){//切记，一定要左边小于右边时才分部处理
			int p = partation(nums,left,r);//找到一个基准位置p
			quickSort(nums,0,p-1);//以p为中心，将数组分成两个子数组，分而治之
			quickSort(nums,p+1,r);
		}
	}
	/**
	 * 快速排序
	 * @param nums
	 */
	public static void quickSort(int nums[]){
		int len = nums.length;
		quickSort(nums,0,len-1);
	}
	
	/**
	 * 合并
	 * @param nums
	 * @param temp
	 * @param left
	 * @param mid
	 * @param r
	 */
	public static void merge(int nums[],int temp[],int left,int mid,int r){
		//拷贝一份数组
		for(int i = left;i<=r;i++){
			temp[i] = nums[i];
		}
		//记录左右部分的索引
		int pa = left,pb = mid+1;
		int index = left;//合并后数组的索引
		
		while(pa<=mid&&pb<=r){
			if(temp[pa]<=temp[pb]){//哪一部分小，就拷贝哪一部分到新数组
				nums[index++] = temp[pa++];
			}else{
				nums[index++] = temp[pb++];
			}
		}
		//处理没有拷贝完的部分，直接赋值到新数组
		while(pa<=mid){
			nums[index++] = temp[pa++];
		}
		while(pb<=r){
			nums[index++] = temp[pb++];
		}
		
		
	}
	/**
	 * 归并排序
	 * @param nums
	 * @param temp
	 * @param left
	 * @param r
	 */
	public static void mergeSort(int nums[],int temp[],int left,int r){
		if(left<r){//左边小于右边时，分而治之
			int mid = (left+r)/2;
			mergeSort(nums,temp,0,mid);
			mergeSort(nums,temp,mid+1,r);
			//合并
			merge(nums,temp,left,mid,r);
		}
	}
	/**
	 * 归并排序
	 * @param nums
	 */
	public static void mergeSort(int nums[]){
		int len = nums.length;
		int temp[] = new int[len];
		mergeSort(nums,temp,0,len-1);
	}
	/**
	 * 调整堆
	 * @param nums
	 * @param i
	 * @param len
	 */
	public static void adjustHeap(int nums[],int i,int len){
		int temp = nums[i];//记录当前节点值（父节点）
		//向下遍历子节点
		for(int k = 2*i+1;k<len;k = k*2+1){
			//如果存在右子节点，且右子节点大于左子节点
			if(k+1<len&&nums[k]<nums[k+1]){
				k++;//指向右子节点
			}
			//如果子节点比当前节点（父节点）大，则将子节点值赋给父节点
			if(nums[k]>temp){
				nums[i] = nums[k];
				i = k;//记录父节点的位置，最终要落到的位置
			}else{//如果子节点小于父节点，则调整结束
				break;
			}
		}
		//将当前父节点的值，最终落位入座
		nums[i] = temp;
	}
	/**
	 * 堆排序，升序，最大堆
	 * @param nums
	 */
	public static void heapSort(int nums[]){
		int len = nums.length;
		// build heap
		for(int i = len/2+1;i>=0;i--){
			//从最后一个非叶节点开始调整，使之满足最大堆
			adjustHeap(nums,i,len);
		}
		// exchange and adjust
		for(int j = len-1;j>=0;j--){
			//交换根节点与最后一个节点
			swap(nums,0,j);
			//调整剩下的节点，使它们满足最大堆
			adjustHeap(nums,0,j);//j是当做长度传过去的，所以，去掉了最后一个节点
		}
		
	}
	
	public static void main(String[] args) {
		
		int nums[] = {2,4,5,7,2,3,4};
		System.out.println("-----排序前-----");
		for(int n:nums){
			System.out.println(n);
		}
//		bubbleSort(nums);//冒泡排序
//		improvedBubbleSort(nums);//改进的冒泡排序
//		insertSort(nums);//插入排序
//		insertBinarySort(nums);//二分插入排序
//		shellSort(nums);//希尔排序
//		selectSort(nums);//选择排序
//		quickSort(nums);//快速排序
//		mergeSort(nums);//归并排序
		heapSort(nums);//堆排序
		
		System.out.println("------排序后-----");
		for(int n:nums){
			System.out.println(n);
		}
		
 }

}