快速排序挖坑法理解与实现

65 阅读 0 评论 43 点赞

我是靠谱客的博主温柔冰棍，最近开发中收集的这篇文章主要介绍快速排序挖坑法理解与实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

看了这片文章，确实非常形象，http://blog.csdn.net/morewindows/article/details/6684558

自己实现的代码如下

package sort;

/*快速排序
 * 简单理解为找位置排序，每趟排序都为阈值pivot找到其该放的位置，即其左边的全都<=pivot,其右边的全都>pivot；
 * 然后对左右两边分别递归执行之前的步骤；
 * 1 low < high 才需要排序，这个同时也是继续递归的条件，若没有则会导致无线递归；
 * 2 下标R=low,L=high, 确定阈值pivot，这里使用数组的第一个元素array[low],pivot = array[low].赋值后low位置(也就是R)可以看做已空，虚位以待
 * 3 以下所有操作都是在R < L的情况下才继续进行，若R=L则找到了pivot在数组中真正应该放的位置
 * 4 从后往前找到 <= pivot的值，将其放在array[R]
 * 5 从前->后，找到>pivot的值，将其放在array[L]
 * 6 当R=L则找到了pivot在数组中真正应该放的位置。array[R] = pivot;
 * 7 分别对array[R]左右两边的序列做同上的操作，即递归
 * */
public class QuickSort {
	public static void quickSort2(int[] array,int low,int high){
		try{
			if(low < high){ //排序条件，也是递归条件
				int R = low,L = high;
				int pivot = array[R];//挖出R位置的值，放入pivot
				//当R=L时表示找到pivot在数组中真正应该放的位置。array[R] = pivot
				while(R < L){
					//前<-后,从后往前找 <= pivot的值放入R
					while(R < L && array[L] > pivot ){
						L--;
					}
					if(R < L ){
						array[R] = array[L];
					}
					
					//前->后,从前往后找到大于pivot的值，存入L
					while(R <L && array[R] <= pivot){
						R++;
					}
					if(R < L){
						array[L] = array[R];
					}
				}
				array[L] = pivot;
				quickSort2(array,low,L - 1);
				quickSort2(array,L + 1,high);
			}
		
		}
		catch(Exception e){
			e.printStackTrace();
		}
	}
	
	
	
	//将阈值pivot放到正确的位置上，即左边元素<=阈值pivot，右边>阈值pivot
	public static void quickSort(int[] array,int low,int high){
		try{
		if(low < high){ //这里是做什么用？没有的话high会变成-1
			int position = low;//阈值的初始位置为low，即取第一个元素作为阈值。
			int pivot = array[position];//取出pivot，使position空出来
			int  R = low,L = high;
			while(R < L){
				//从后往前找到 <=pivot 的元素，放在R上
				while(R != L && array[L] > pivot){
					L--;
				}
				if(R < L){
					array[R] = array[L];
					R++;
				}
				
				
				//从前往后找 >pivot 的元素，放在L上,因为L的位置已空出来
				while( R != L && array[R] <= pivot){
					R++;
				}
				if(R < L){
					array[L] = array[R];
					L--;
				}
				
				
			}
			
			array[L] = pivot;//找到pivot的正确位置
			quickSort(array,low,L - 1);//对左边继续递归
			quickSort(array,L + 1,high);//对右边继续递归
			//return R;
		}
		}
		catch(Exception e){
			
			e.printStackTrace();
		}
	}
	
	
	public static void main(String[] args) {
		int[] array = {72,6,57,88,60,42,83,73,48,85};
		int[] array2 = {72,6,57,88,60,42,83,73,48,85};
		
		quickSort(array,0,array.length - 1);
		
		for(int i :array){
			System.out.print(i + ",") ; 
			//System.out.print(i + ',') ; //--> 使用单引号会导致 加上字符,的int值
		}
		System.out.println() ; 
		quickSort2(array2,0,array.length - 1);
		for(int i :array){
			System.out.print(i + ",") ; 
			//System.out.print(i + ',') ; //--> 使用单引号会导致 加上字符,的int值
		}
		
	}

}