算法导论学习之第七章－快速排序

      快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

      不说废话，我们先看代码，然后举个具体例子进行分析。

package chapter7;

import java.util.Arrays;

public class QuickSort {
	public void sort(int a[],int l,int r){
		if(l<r){
			int q=partition1(a,l,r);
			sort(a,l,q);
			sort(a,q+1,r);
		}
	}
	
	public void sort(int a[]){
		sort(a,0,a.length-1);
	}
	
	private int partition1(int a[],int i,int j)
	{
		int key=a[(i+j)/2];
		while(i<j){
			
			while(i<j&&a[i]<key){
				i++;
			}
			
			while(i<j&&a[j]>key){
				j--;
			}
			
			if(i<=j){
				swap(a,i,j);
				j--;
			}
		}
		//System.out.printf("(key=%d,i=%d,j=%d\n,array=%s)\n",key,i,j,Arrays.toString(a));
		return i;
	}
	

	private void swap(int[] a, int i, int j) {
		int t=a[i];
		a[i]=a[j];
		a[j]=t;
	}

	
	
	public static void main(String[] args) {
		int a[]={8,5,7,2,19,3};
		System.out.println("Before "+Arrays.toString(a));
		QuickSort qs=new QuickSort();
		qs.sort(a);
		System.out.println("After "+Arrays.toString(a));
	}
}

 

  对于数组A[0,r]存在分割点p,使得A[0,p]有序，同时A[p+1,r]有序，并且A[0,p]<=A[p]<=A[p+1,r] 。

 

  我们来看看数组a=[8,5,7,2,19,3]是如何进行快速排序的。

   具体代码：

 

private int partition1(int a[],int i,int j)	

{
		int key=a[(i+j)/2];
		while(i<j){
			
			while(i<j&&a[i]<key){
				i++;
			}
			
			while(i<j&&a[j]>key){
				j--;
			}
			
			if(i<=j){
				swap(a,i,j);
				j--;
			}
		}
		//System.out.printf("(key=%d,i=%d,j=%d\n,array=%s)\n",key,i,j,Arrays.toString(a));
		return i;
	}

 

• 获取分割点坐标值i
• 对a[0,i]和a[i+1,length]进行递归排序

      令key=a[2]=7

      第一趟获取分割点：

1.  i=0,j=5,  a[i]=8,a[j]=3,key=7,因为a[i]>key同时a[j]<key 直接交换i,j的值，j向数组左移动 数组A＝[3,5,7,2,19,8]
2.  i=0,j=4,  a[i]=3,a[j]=19,key=7  a[i]<key 那么指针i向右移动 知道i=2
3.  i=2,j=4,  a[i]=7,a[j]=19,key=7 a[i]=key同时a[j]>key ，指针i不移动，指针j继续向左移动
4.  i=2,j=3,  a[i]=7,a[j]=2 ,key=7  a[i]=key同时a[j]<key,因此指针i不移动，指针j继续向左移动，同时交换i,j的值，此时A＝[3,5,2,7,19,8]
5.  i=2,j=2 跳出循环，返回分割点的值为i=2 即完成第一趟分割 。此时A＝[3,5,2,7,19,8]
6. 由于i=j=2,结束递归条件，函数执行完成。

     第二趟获取分割点：

1. 此时快速排序递归调用sort(a,0,p) ,p=2 ，获取数组A‘＝[3,5,2]
2. i=0,j=2,Key=a[1]=5  因为a[i]=3<5 因此 指针i向右移动直到i=1，此时j=2
3. i=1,j=2,key=5, a[i]=5,a[j]=2 ，因为a[j]<key,因此交换i,j的值，并将指针j向左移动，此时A’＝[3,2,5],A=[3,2,5,7,19,8]
4. i=1,j=1,跳出循环，返回分割点的值为i=1，完成第二趟分割。此时A＝[3,2,5,7,19,8]
5. 由于i=j=1,结束递归条件，函数执行完成。

    第三趟获取分割点：

1. 此时快速排序递归调用sort(a,0,p),p=1,令数组A2=[3,2]
2. i=0,j=1 key=a[0]=3 a[i]=3=key，所以指针i不移动，a[j]=2<key，因此需要交换i,j的值，然后将指针j向左移动，此时A2＝[2,3]
3. i=0,j=0 跳出循环，返回分割点的值为i=0,完成第三趟分割。此时A＝[2,3,5,7,19,8]
4. 由于i=j=0,结束递归条件，函数执行完成。

   第四趟获取分割点：

1. 此时快速排序递归调用sort(a,p+1,r),p=2,令数组A3＝[19,8]
2. i=4,j=5 ,key=a[4]=19,a[i]=19,因为a[i]=key,因此指针i不移动，a[j]=8<key，因此需要交换i,j的值，同时j向做移动。此时A3＝[8,9]
3. i=4,j=4 跳出循环，返回分割点i=4,完成第四趟获取分割点。此时A=[2,3,5,7,8,19]
4. 由于i=j=4,结束递归条件，函数执行完成。    

 

     由此我们可以很清晰的知道快速排序的工作原理，关键函数是获取分割点，同时应该注意边界问题。

    欢迎各位拍砖