`
liaokang.java
  • 浏览: 157030 次
  • 性别: Icon_minigender_1
  • 来自: 湖南
社区版块
存档分类
最新评论

快速排序

 
阅读更多
   快速排序是在冒泡排序的基础上进行的改装,它的原理是经过一趟排序将数据分割成两部分,左边的数据小于右边的数据,然后分别对这两部分数据用同样的原理进行排序,整个排序过程是用递归实现的,下面来看一个例子

package com.lamp.sort;

public class QuickSort{
	public static void main(String[] args) {
		int[] data = {5,3,9,2,6,1};
		sort(data,0,data.length);
		for (int i = 0; i < data.length; i++) {
			System.out.println(data[i]);
		}
	}
	
	/*	首先我要找到一个位置的数使得其左边的数字比它要小,右边的数字比它要大
		开始的时候数组为5,3,9,2,6,1
		首先从左端下标为++i开始扫描发现3小于5满足条件继续,发现下一个9大于5而此时i的下标值为2
		不满足条件推出左端扫描的while循环,开始从最右端开始扫描,发现最右端第一个数字就小于5,此时
		j的值为5,而i此时是小于j的,交换两位置数据,即一轮循环后的数据为
		5,3,1,2,6,9
		接着从左端开始继续扫描,当扫描到大于5的值的时候,i的值变为4即6所处位置的下标,当从右端
		开始扫描时,扫描到小于5的数字时,j的值变为3,而此时i的值大于j的值不满足条件推出最外的
		while循环,此时数组的数据为
		5,3,1,2,6,9
		然后将第一个数和j处下标的数进行互换,数组变为
		2,3,1,5,6,9
		这样就达到了预期的目标,即下标为3的数据大于其左边的数据且小于其右边的数据
		然后以5为分割点对两边的数据用同样的原理进行排序
	*/
                                                                                                                                                                                                                                                                                                                           
	private static void sort(int[] data, int left, int right) {
		int i = left;
		int j = right;
		int middle = data[left];	//第一次调用时候我选取要排序的数组的第一个数作为关键数据
		while(true){
			while(++i<right-1 && data[i]<middle);
			while(--j>left && data[j]>middle);
			if(i >= j){
				break;
			}       
			swap(data,i,j);   
		}
		data[left] = data[j];
		data[j] = middle;
		
		if(left < j){
			sort(data,left,j);
		}
		if(i < right){
			sort(data,i,right);
		}
	}

	private static void swap(int[] data, int i, int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}
}
分享到:
评论
Global site tag (gtag.js) - Google Analytics