快速排序算法java实现（中）

1、快排之单项扫描(java)

用了三个函数，quicksort函数体现了快排的思想，用目标值进行分区（目标值左边都是小于目标值的，目标值右边都是大于目标值的）。

partition函数中定义了两个指针，第一个指针sp从begin+1开始扫描（这里的sp和begin都是指数组下标），第二个指针bigger标记比目标值大的数值下标。如果sp指向的数值大于pivot(开始时即为数组的第一个数)，那么sp与bigger交换，并且bigger-1，即bigger指针前移。反之，则sp+1,即sp指针后移。当sp>biggger时，bigger指的是最后一个小于目标值的数，sp指的是最后一个大于目标值的数，begin于bigger交换，即实现了目标值左边均小于它，目标值右边均大于它。

public static void main(String[] args) {
			// TODO Auto-generated method stub
			int[] arr = { 9, 8, 7, 6, 5, 0, 4, 8, 3, 2, 8, 7, 10 };
			quicksort(arr, 0, arr.length - 1);
			for (int num : arr) {
				System.out.print(num + " ");
			}
		}
private static void quicksort(int arr[],int begin,int end) {
			if(begin<end) {
			int q=partition(arr, begin, end);//找到目标值的下标
			quicksort(arr,begin,q-1);//目标值的左边进行快排
			quicksort(arr, q+1, end);//目标值的右边进行快排
			}
		}
		private static int partition(int arr[],int begin,int end) {
		int sp=begin+1;//第一个指针，用来与目标值作比较
		int bigger=end;//第二个指针，控制目标值右面的数均大于它
		int pivot=arr[begin];//第一个数作为目标值
		while(sp<=bigger) {
			if(arr[sp]<=pivot) {
				sp++;//指针指向的元素小于目标值，指针前移
			}
			else {
				swap(arr,sp,bigger);
				bigger--;//指针指向的元素大于目标值，目标值与bigger交换
			}
		}//当sp大于bigger时，目标值与bigger交换
		swap(arr,begin,bigger);
		return bigger;
		}
		private static void swap(int arr[],int i,int j) {
			int temp;
			temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
		}
           

2、快排之双向扫描

与单向扫描不同，双向扫描是左右两个指针对向扫描left扫描到大于目标值的就会停下来，right扫描到小于目标值的就会停下来，然后left与right交换继续扫描。

public static void main(String[] args) {
			// TODO Auto-generated method stub
			int[] arr = { 9, 8, 7, 6, 5, 0, 4, 8, 3, 2, 8, 7, 10 };
			quicksort(arr, 0, arr.length - 1);
			for (int num : arr) {
				System.out.print(num + " ");
			}
		}
private static void quicksort(int arr[],int begin,int end) {
			if(begin<end) {
			int q=partition2(arr, begin, end);//找到目标值的下标
			quicksort(arr,begin,q-1);//目标值的左边进行快排
			quicksort(arr, q+1, end);//目标值的右边进行快排
			}
		}
private static void swap(int arr[],int i,int j) {
			int temp;
			temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
		}
		private static int partition2(int arr[],int begin,int end) {
			int left=begin+1;
			int right=end;
			int pivot=arr[begin];
			while(left<=right) {
				while(left<=right&&arr[left]<=arr[begin]) {
					left++;
				}
				while(left<=right&&arr[right]>arr[begin]) {
					right--;
				}
				if(left<right)
					swap(arr, left, right);
			}
			swap(arr, begin, right);
			return right;
			
		}