欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速排序&归并排序

程序员文章站 2022-05-13 19:37:34
...
1、快速排序

快速排序利用分治的思想,首先选取一个哨兵,将数组中大于哨兵的元素放到一边,小于数组的元素放到另一边,然后对两边也进行相同的操作。

public void quickSort(List<Integer> t){
	quickSort(t,0,t.size()-1);
}
private void quickSort(List<Integer> t,int l,int h){
	if( l < h ){
		int mid = patiton(t,l,h);
		quickSort(t,l,mid-1);
		quickSort(t,mid+1,h);
}
//将大于哨兵的放到一边,小于哨兵的放到另一边,这里选取[l,h]区间中第一个元素作为哨兵
private void patition(List<Integer> t,int l,int h){
	int vis = t.get(l);	//选取的哨兵
	while( l < h ){
		while( h > l && t.get(h) >= vis ) h--;	//从h开始找到一个比哨兵小的元素
		t.set(l,t.get(h));
		while( l < h && t.get(l) <= vis ) l++;	//从l开始选取一个比哨兵大的元素
		t.set(h,t.get(l));
	}
	t.set(l,vis);	//将哨兵插在“中间”
	return l;
}
	
3、归并排序

归并排序也是利用分治的思想,假如数据可分成两部分:A和B,且A和B的内部都是有序的,那么可以将A和B合成一个有序的数组,方法是先选取A和B中的第一个元素,并将其中较小的放到数组C中,然后后移A或B中的指针(从哪个数组中选出较小的就下移哪一个),然后再次比较A和B中的元素,选出较小的放到C中,如此循环。
例如: A: 2 5 9 ,B:1 6 7 10
第一次: C : 1
第二次: C : 1、2 (B中选出1后后移指针,用6与2比较)
第三次: C : 1、2、5
。。。

归并排序就是将数组分为两部分,然后将每部分又分为两部分,最后每部分只有一个数据时便向上开始合并。

	//将[l,m]和[m+1,h]两部分合并
	private static void merge(List<Integer> t,int l,int m,int r){
		int len1 = m-l+1;
		int len2 = r-m;
		int i = 0,j = 0;
		int[] a = new int[len1];//将[l,m]存储到a中
		int[] b = new int[len2];//将[m+1,r]存储到b中
		for(i = 0 ; i < len1 ; i++)
			a[i] = t.get(l+i);
		for(i = 0 ; i < len2 ; i++)
			b[i] = t.get(m+1+i);
		i = 0;
		j = 0;
		//合并且存储到t[l,r]中
		for( int k = l ; k <= r ; k++){
			if(i < len1 &&(j >= len2 || a[i] < b[j]) ){
				t.set(k, a[i]);
				i++;
			}
			else if( j < len2 ){
				t.set(k, b[j]);
				j++;
			}
		}
	}
	public static void mergeSort(List<Integer> t){
		mergeSort(t,0,t.size()-1);
	}
	private static void mergeSort(List<Integer> t,int l,int r){
		if( l < r){
			int mid = ( l + r )/2;
			mergeSort(t,l,mid);
			mergeSort(t,mid+1,r);
			merge(t,l,mid,r);
		}
	}