Java算法之 快速排序的实现

刚刚找到工作，但是发现自己虽然对数据结构的知识了解原理，但是实现的话，仍然有很大的麻烦。决定在大学的最后几个月对数据结构进行一个系统的详细的学习。好了，第一篇：快速排序的算法。由于我只是想实现一个简单的原理，所以类的构造就比较简单了，比较的原型都死int型的。

快速的排序的定义我不说了，直接贴源代码：

public class BaseQuickSort implements QuickSortExecutor{

	private int[] arrays;

	@Override
	public void executor() {
		if(arrays == null || arrays.length == 0)
		{
			throw new IllegalArgumentException("array can not be null or length is zero");
		}
		
		quickSort(0,arrays.length - 1);
	}

	private void quickSort(int low,int high)
	{
		
		int key  = arrays[high];
		int begin = low;
		int end   = high;
		int position  = high;
		int temp ;
		
		while(begin <  end){
			if(position  == end){
				if(arrays[begin] <= key)
					begin++;
				else {
					temp = arrays[begin];
					arrays[begin] = key;
					arrays[position]  = temp;
					position  = begin;
					end--;
				}
			}else if(position == begin)
			{
				if(arrays[end] >= key)
				{
					end--;
				}else{
					temp  = arrays[end];
					arrays[end] = key;
					arrays[position]  = temp;
					position  = end;
					begin++;
				}
			}
		}
		
		if(low < position - 1)
			quickSort(low, position - 1);
		
		if(position + 1 < high)
			quickSort(position + 1,high);
	}
	
	public int[] getArrays() {
		return arrays;
	}

	public void setArrays(int[] arrays) {
		this.arrays = arrays;
	}
	
	public static void main(String[] args) {
		BaseQuickSort sort  = new BaseQuickSort();
		
		int[] arrays = new int[]{128,137,1898989,55,532,99,12,3,1000,255};
		
		sort.setArrays(arrays);
		
		sort.executor();
		
		for(int i  = 0;i< arrays.length ;i++)
		{
			System.out.print(arrays[i] + "  ");
		}
	}
}

这个的实现是使用的是递归结构，所以说还是比较简单的。下面是一个实现了不使用系统的递归函数，自己定义的一个栈，用来排序，也是快速排序的算法实现：

public class NoStackQuickSort implements QuickSortExecutor{

	
	int[] arrays;
	
	@Override
	public void executor() {
		
		if(arrays == null || arrays.length == 0)
		{
			throw new IllegalArgumentException("array can not be null or length is zero");
		}
		int[] stack  = new int[arrays.length];
		
		int stacktop  = 0;
		
		stack[stacktop] = 0;
		stacktop++;
		stack[stacktop] = arrays.length-1;
		stacktop++;
		while(stacktop != 0)
		{
			stacktop--;
			int uhigh  = stack[stacktop];
			stacktop--;
			int ulow   = stack[stacktop];
			
			if(uhigh > ulow)
			{
				// 进行排序 获得mid值
				int mid = spitArrays(ulow, uhigh);
				if(mid - ulow > uhigh - mid)
				{
					stack[stacktop] = ulow;
					stacktop++;
					stack[stacktop] = mid - 1;
					stacktop++;
					if(uhigh > mid)
					{
						stack[stacktop] = mid+1;
						stacktop++;
						stack[stacktop] = uhigh;
						stacktop++;
					}
				}else{
					stack[stacktop] = mid + 1;
					stacktop++;
					stack[stacktop] = uhigh;
					stacktop++;
					if(mid > ulow)
					{
						stack[stacktop] = ulow;
						stacktop++;
						stack[stacktop] = mid - 1;
						stacktop++;
					}
				}
			}
		}
		
	}

	private int spitArrays(int low,int high){
		
		int key  = arrays[high];
		int begin = low;
		int end   = high;
		int position  = high;
		int temp ;
		
		while(begin <  end){
			if(position  == end){
				if(arrays[begin] <= key)
					begin++;
				else {
					temp = arrays[begin];
					arrays[begin] = key;
					arrays[position]  = temp;
					position  = begin;
					end--;
				}
			}else if(position == begin)
			{
				if(arrays[end] >= key)
				{
					end--;
				}else{
					temp  = arrays[end];
					arrays[end] = key;
					arrays[position]  = temp;
					position  = end;
					begin++;
				}
			}
		}
		
		return position;
	}
	
	
	
	
	public int[] getArrays() {
		return arrays;
	}

	public void setArrays(int[] arrays) {
		this.arrays = arrays;
	}

	public static void main(String[] args) {
		
		//设置十万个随机数
		
		int length  = 10 * 10000;
		
		int[] arrays  = new int[length];

		int[] copyArrays = new int[length];
		
		int[] bubbleArrays  = new int[length];
		
		//开始使用内存的算法
		
		Random random  = new Random();
		
		for(int i  = 0;i< length;i++)
		{
			arrays[i]  = random.nextInt(Integer.MAX_VALUE);
		}
		
		System.arraycopy(arrays, 0, copyArrays, 0, length);
		System.arraycopy(arrays, 0, bubbleArrays, 0, length);
		
		//初始化进行测试
		for(int i = 0;i<length ;i++)
		{
			if(arrays[i]  != copyArrays[i])
				throw new IllegalArgumentException();
		}
		
		for(int i = 0;i<length ;i++)
		{
			if(arrays[i]  != bubbleArrays[i])
				throw new IllegalArgumentException();
		}
		
		BaseQuickSort stackExecutor = new BaseQuickSort();
		NoStackQuickSort noStackExecutor  = new NoStackQuickSort();
		BubbleSortExecutor  bubbleExecutor  = new BubbleSortExecutor();
		
		stackExecutor.setArrays(arrays);
		noStackExecutor.setArrays(copyArrays);
		bubbleExecutor.setArrays(bubbleArrays);
		
		long begin = System.currentTimeMillis();
		
		stackExecutor.executor();
		
		long end   = System.currentTimeMillis();
		
		System.out.println("运行时间：使用栈：" + (end  - begin));
		//--------------------------------------
		begin = System.currentTimeMillis();
		
		noStackExecutor.executor();
		
		end   = System.currentTimeMillis();
		
		System.out.println("运行时间:不使用栈:" + (end - begin));
		
		//-------------------------------------
		begin   = System.currentTimeMillis();
		
		bubbleExecutor.executor();
		
		end  = System.currentTimeMillis();
		
		System.out.println("运行时间,冒泡:" + (end - begin));
		
		
	
		//测试是否排序正确
		for(int i = 0;i<length ;i++)
		{
			if(arrays[i]  != copyArrays[i])
				throw new IllegalArgumentException();
		}
		
		for(int i = 0;i<length ;i++)
		{
			if(arrays[i]  != bubbleArrays[i])
				throw new IllegalArgumentException();
		}
		
	}
}

最后的main函数里面，我对算法进行了测试，发现，快速算法确实比冒泡算法实现快多了，
之所以不设置太多的随机数排序，是因为在冒泡算法的运行效率实在是太低了，在这个算法的测试中，我的冒泡算法的时间通常达到34秒，但是快速排序却是15ms，差距很大啊。

这个测试中，如果仅仅是区别快速排序的两种实现的话，我们可以发现，快速排序的递归函数的时间消耗是小于我们自己写的不是递归的构造快速排序算法。但是在十万的数据一下，二者的时间是相同的。只是在百万的数据量下，才能显示是也是微小的时间差距。

好了，快速排序写完了