for(int i=0;i<length;i++){
	int max=0;
	for(int j=1;j<length-i;j++){
		if(arr[max]<arr[j]){
			max=j;
		}
	}
	Util.exchange(max, length-i-1, arr);
}

for(int i=1;i<length;i++){
	int index=i;
	for(int j=i-1;j>=0;j--){
		if(arr[index]>arr[j]) break;
		Util.exchange(index, j, arr);
		index--;
	}
}

public static void shellSortByGap(int gap, int[] arr){
		int length=arr.length;
		for(int i=0;i<gap;i++){
			for(int j=i+gap;j<length;j=j+gap){
				int index=j;
				while(index>i){
					if(arr[index]>arr[index-gap]) break;
					if(arr[index]<arr[index-gap]){
						Util.exchange(index-gap, index, arr);
						index-=gap;
					}
				}
			}
		}	
	}

public static void locate(int start,int end,int[] arr){
		if(start>=end) return;
		
		int index=start;
		int last=end;
		while(last>index){
			if(arr[index]>arr[index+1]){
				Util.exchange(index, index+1, arr);
				index++;
			}else if(arr[index]<arr[index+1]){
				Util.exchange(index+1, last, arr);
				last--;
			}
		}
		locate(start,index-1,arr);
		locate(index+1,end,arr);
	}

public void sink(int k){
	//check是否有子节点
	while(2*k<=size){
		int bigSonNode=2*k;
		//如果有右子节点且右子节点大于左子节点则 最大子节点指向右子节点
		if((2*k+1<size)&&list.get(2*k)<list.get(2*k+1)){
			bigSonNode=2*k+1;
		}
		
		//比较左子节点，如果小于，就交换
		if(list.get(k)<list.get(bigSonNode)){
			Util.exchangeList(k, bigSonNode, list);
			k=bigSonNode;
			//检查是否存在右子树，如果右且大于父节点就交换
		  }else{
			  break;
		  }
		
	}
}
//通过从N/2开始往堆顶进行sink()操作构建堆有序
public static void buildHeap(MaxPQ pq){
	int N=pq.list.size()-1;
	for(int i=N/2;i>0;i--){
		pq.sink(i);
	}
   }
public static void HeapSort(MaxPQ pq){
	List<Integer> list=pq.getList();
	int size=list.size();
	int tail=size-1;
	for(int i=1;i<size;i++){
		Util.exchangeList(1, tail, list);
		pq.setSize(--tail);
		pq.sink(1);
	}
}

//对一个数组按照下标进行归并排序
//归并排序的精华所在：问题拆分，把一个大问题拆分为N个性质一样但更简单的小问题
public static void mergeSort(int[] arr,int start,int end){
	//这也是递归的终结，当数组拆分到只有1个元素的时候，必然是有序的，否则就继续拆分
	if(start<end){
		//拆分大问题为两个小问题
		int mid=(start+end)/2;
		mergeSort(arr,start,mid);
		mergeSort(arr,mid+1,end);
		//小问题解决完之后，最后父问题
		merge(arr,start,mid,end);
	}
}
//有两个数组，一个数源数组arr1，一个是工具数组是长度一样但是都是null的arr2
//arr1数组中有2个连续且有序的数组 arr11 和 arr12
//low是arr11的start，mid是arr11的end，mid+1是arr12的start，high是arr12的end
//设置了3个游标，i为arr11的游标，j为arr12的游标，k为arr2的游标
//merge的思路是当arr11和arr12中从起始位置开始比较，最小的写到arr2中，一直到有一个掏空了
//假如是arr11先掏空，那么顺序把arr12中的元素顺序写入到arr2中；反之把arr11中剩余元素写入到arr2中
//最后再把工具数组里的数据按照low high位置写回到arr1中，这样可以arr1可以继续比较了
public static int[] arr2=new int[20];
public static void merge(int[] arr1,int low,int mid,int high){
	int i=low,k=low,j=mid+1;
	//当arr11和arr12中从起始位置开始比较，最小的写到arr2中，对应下标移动，一直到有一个掏空了为止
	while(i<=mid&&j<=high){
		if(arr1[i]<arr1[j]){
			arr2[k++]=arr1[i++];
		}else {
			arr2[k++]=arr1[j++];}
	}
	//如果是arr12先被掏空，则arr11中剩余元素写入到arr2中,这里可以优化
	while(i<=mid){
		arr2[k++]=arr1[i++];
	}
	//如果是arr11先被掏空，则arr12中剩余元素写入到arr2中，这里可以优化
	while(j<=high){
		arr2[k++]=arr1[j++];
	}
	//arr2排序结束写回到arr1中相应位置
	for (i = low; i <= high; i++) {
           arr1[i] = arr2[i];
       }
}