java实现归并排序,快速排序

快速排序

package com.ycit.sortSelect;

/**
 * @author 江鹏飞
 *	快速排序
 *	[11,4,3,6,5,8,7,12,9]
 *   low			  high
 *	思路:
 *	1.找到一个基准元素进行比较    分别从后往前  从前往后 找到 中间的值middle   此时middle 的位置就是基准元素的位置
 *	并且基准元素左边的所有值都比基准元素小，右边的所有元素都比基准元素大    然后再进行双项迭代
 */
public class QuickSort {
	public void quick(int [] a){
		if(a.length>0){
			quickSort(a,0,a.length-1);
		}
	}
	public void quickSort(int a[],int low,int high){
		if(low<high){
		int middle = getMiddle(a,low,high);
		quickSort(a,0,middle-1);
		quickSort(a,middle+1,high);
	}
	}
	private int getMiddle(int[] a, int low, int high) {
		int temp = a[low];//基准元素
		while(low<high){
		while(low<high && a[high]>=temp){
			high--;
		}
		a[low]=a[high];
		while(low<high && a[low]<=temp){
			low++;
		}
		a[high]=a[low];
		}
		a[low]=temp; 
		
		return low;
	}
	public static void main(String[] args) {
		QuickSort q = new
				 QuickSort();
		int a[]= new int[] { 8, 3, 4, 5, 7, 1, 12, 33, 15 };
		q.quick(a);
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}
	}

}

归并排序

package com.ycit.sortSelect;

/**
 * @author 江鹏飞
 *	归并排序
 *		[4,1,5,7,9,21,86,3,32,12]
 *		left	middle		right
 *	第一次分解: [4,1,5,7,9]      [21,86,3,32,12]
 *			left  mid  rg
 *	最终分解结果:[4] [1] [5] [7] [9] [21] [...]
 *	   两两比较   [1,4,5] [7,9,21] 
 *	三三比较 [1,4,5,7,9,21]
 *	对分解后的数组进行 合并
 *	
 *	思路:
 *		1.利用迭代的方法对数组进行分解    
 */
public class MergeSort {
	//[4,1,5,7,9,21,86,3,32,12]
	public void mergeSort(int a[],int left,int right){
		if(left<right){
			int middle = (left+right)/2;
			mergeSort(a,left,middle);// 把原数组左边拆分成更小的数组
			mergeSort(a,middle+1,right);//把数组右半部分进行拆分成更小的数组  直到数组里面有一个数时停止
			merge(a,left,middle,right);//合并
		}
	}

	private void merge(int[] a, int left, int middle, int right) {
		int [] tempArray = new int[a.length];
		int rightStart = middle+1;
		int temp = left;
		int third = left;
		while(left<=middle && rightStart<=right){
			if(a[left]<=a[rightStart]){
				tempArray[third++] = a[left++];
			}else{
				tempArray[third++] = a[rightStart++];
			}		
		}
		//如果右边已经比较完毕 左边还有元素需要比较  则现在左边元素一定大于右边元素 直接将左边元素插入数组
		while(left<=middle){
			tempArray[third++]=a[left++];
		}											
		//如果左边比较 完毕需要比较左边 则同理把右边元素插入到数组中
		while(rightStart<=right){
			tempArray[third++]=a[rightStart++];
		}
		//新数组排序完毕
		//将新的临时数组赋值给我们要排序的数组 a
		while(temp<=right){
			a[temp]=tempArray[temp++];
		}
		
	}
	public static void main(String args[]){
		int a[] = new int[]{4,1,5,7,9,21,86,3,32,12};
		MergeSort mergeSort =new MergeSort();
		mergeSort.mergeSort(a, 0, a.length-1);
		for(int num:a){
			System.out.print("\t"+num);
		}
	}
}