정렬 알고리즘 기초 총화

	/***
	 * @    
	 * @BubbleSort
	 * @param arr
	 */
	public static void BubbleSort(int[] arr){
		if(arr == null || arr.length<2){
			return;
		}
		for(int i = arr.length-1;i>0;i--){
			for(int j=0;j<i;j++){
				if(arr[j]>arr[j+1])
					swap(arr,i,j);
			}
		}
	}

	/***
	 * @    
	 * @SelectionSort     ，      ，         
	 * @param arr
	 */
	public static void SelectionSort(int[] arr){
		if(arr == null || arr.length<2){
			return;
		}
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
			}
			swap(arr, i, minIndex);
		}
	}

	/***
	 * @    
	 * @InsertionSort
	 * @param arr
	 */
	public static void InsertionSort(int[] arr){
		if(arr == null || arr.length<2){
			return;
		}
		for(int i = 1 ; i < arr.length;i++){
			for(int j = i-1 ; j >=0;j--){
				if(arr[j]<arr[j+1])
					swap(arr,j,j+1);
				else
					break;
			}
		}
	}

	/***
	 * @    
	 * @mergeSort
	 * @param arr
	 */
	public static void mergeSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		mergeSort(arr, 0, arr.length - 1);
	}
	
	public static void mergeSort(int[] arr, int l, int r) {
		if (l == r) {
			return;
		}
		int mid = l + ((r - l) >> 1);
		mergeSort(arr, l, mid);
		mergeSort(arr, mid + 1, r);
		merge(arr, l, mid, r);
	}
	//       (l-m) (m+1 - r)   
	public static void merge(int[] arr, int l, int m, int r) {
		int[] help = new int[r - l + 1];//R-L+1
		int i = 0;
		int p1 = l;
		int p2 = m + 1;
		while (p1 <= m && p2 <= r) {
			help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
		}
		while (p1 <= m) {
			help[i++] = arr[p1++];
		}
		while (p2 <= r) {
			help[i++] = arr[p2++];
		}
		for (i = 0; i < help.length; i++) {
			arr[l + i] = help[i];
		}
	}

	/***
	 * @        ：      
	 * @quickSort
	 * @param arr
	 */
	public static void quickSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		quickSort(arr, 0, arr.length - 1);
	}

	public static void quickSort(int[] arr, int l, int r) {
		if (l < r) {
			swap(arr, l + (int) (Math.random() * (r - l + 1)), r);//    ，L-R        R    
			int[] p = partition(arr, l, r);
			quickSort(arr, l, p[0] - 1);
			quickSort(arr, p[1] + 1, r);
		}
	}

	public static int[] partition(int[] arr, int l, int r) {// R         ，    ，    ，      
		int less = l - 1;
		int more = r;
		while (l < more) {
			if (arr[l] < arr[r]) {
				swap(arr, ++less, l++);
			} else if (arr[l] > arr[r]) {
				swap(arr, --more, l);
			} else {
				l++;
			}
		}
		swap(arr, more, r);
		return new int[] { less + 1, more };
	}

	/***
	 * @   
	 * 1.    
	 * 2.    
	 * 3.  heapify     
	 * @heapSort
	 * @param arr
	 */
	public static void heapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {//       
			heapInsert(arr, i);
		}
		int size = arr.length;
		swap(arr, 0, --size);
		while (size > 0) {
			heapify(arr, 0, size);//      
			swap(arr, 0, --size);
		}
	}
	public static void heapInsert(int[] arr, int index) {//     ，index       
		while (arr[index] > arr[(index - 1) / 2]) {//arr[(0-1)/2] = arr[0]
			swap(arr, index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}
	public static void heapify(int[] arr, int index, int size) {//       arr[0]  ，            
		int left = index * 2 + 1;//index    
		while (left < size) {
			int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;//              
			largest = arr[largest] > arr[index] ? largest : index;//      （    ）      
			if (largest == index) {
				break;
			}
			swap(arr, largest, index);//     
			index = largest;
			left = index * 2 + 1;
		}
	}

	/***
	 * @      
	 * @            
	 * @swap a,b
	 * @param arr
	 * @param i
	 * @param j
	 */
	public static void swap(int[] arr,int i,int j){
		arr[i] = arr[i]^arr[j];
		arr[j] = arr[i]^arr[j];
		arr[i] = arr[i]^arr[j];
	}