数据结构与算法 快速排序

 

package endual.huafen.quickly.writeagain;

/**
 * 快速排序1：
 * 
 * 其思想也是递归排序的，首先我们要有划分，随便选取一个key值，小的数放在这个key的左边，大的数就放在key的右边
 * 然后递归就OK了。放在key值的左边和右边的数并没被排序好的，所以还是要进行排序的
 * 
 * 
 * @author Endual
 *
 */
public class QuickSort1 {

	private long[] theArray ; //创建了一个数组，这个数组是用来存放要进行的排序的数据的
	private int    nElems ; //记录有多少个数据要进行排序的
	
	public QuickSort1(int max) {
		this.theArray = new long[max] ; //存入数据的最大的个数吧
		this.nElems = 0 ; //初始化记录的个数
	}
	//插入数据的，一次插入一次
	public void insert(long value) {
		
		this.theArray[this.nElems] = value ; 
		this.nElems++ ; //插入一次记录就增加一次
	}
	//返回当前数组中有多少个数据要进行排序
	public int size() {
		
		return this.nElems ;
	}
	
	//显示当前数据的排序
	public void display() {
		int size = this.size() ;
		for (int i=0; i < size; i++) {
			
			System.out.println(this.theArray[i]);
		}
	}
	
	//快速排序的调用方法
	public void qucikSrot() {
		
		recQucikSort(0, this.nElems-1) ;//输入的是数组的最前面一个0 和 最后面一个nElems-1
	}

	
	
	private void recQucikSort(int left, int right) {

		if (right - left <= 0) { //递归终止的条件，当开始的标号小于或者等于右边的标号的时候就停止
			return ;
		}
		
		else {
			
			long pivot = this.theArray[right] ; //默认最右边的数据项作为那个key值
			
			
			//返回的是pivot的位子，
			//当然已经进行了划分排序
			//这个是快速排序的核心所在
			int partition = partitionIt(left,right,pivot) ; 
			
			recQucikSort(left, partition-1) ; //递归left到这个key值的这么一段的
			recQucikSort(partition+1, right) ; //递归这个key值+1，这个位子到右边的数据
			
		}
		
	}

	//快速排序的划分核心
	private int partitionIt(int left, int right, long pivot) {
		
		int leftPtr = left - 1 ; //左边和右边的两个指针
		int rightPtr = right ;
		
		while (true) {
			
			while (this.theArray[++leftPtr] < pivot) ; //找到大的item,那么就找了左边的位子上，其中一个值是要大于key值的
			
			while (rightPtr > 0 && this.theArray[--rightPtr] > pivot) ; //找到小的item，那么就找了右边的其中一个值是大于key值的 交换位子哦
			
			if (leftPtr >= right) { //终止的条件就是当左边的指针小于右边的指针或者等于右边的时候
				break ; 
			}else {
				swap(leftPtr, rightPtr) ;
			}
		}
		
		this.swap(leftPtr, right) ; //把关键词要交换下位子的
		return leftPtr;
	}

	private void swap(int leftPtr, int rightPtr) {
		
		long temp = this.theArray[leftPtr] ;
		this.theArray[leftPtr] = this.theArray[rightPtr] ;
		this.theArray[rightPtr] = temp ;
		
	}
	
	
}

 

今天很不顺利啊 为什么就不能弄出来呢 ？

 

main:

 

package endual.huafen.quickly.writeagain;

public class QuickSort1App {

	
	public static void main(String[] args) {
		
		QuickSort1 app = new QuickSort1(19) ;

		app.insert(4) ;
		app.insert(56) ;
		app.insert(21) ;
		app.insert(5) ;
		app.insert(43) ;
		app.insert(9) ;
		app.insert(45) ;
		
		app.display() ;
		System.out.println("--------------");
		app.qucikSrot() ;
		
		app.display() ;
		
		
	}

}

 

排序结果

 

4
56
21
5
43
9
45
--------------
56
9
4
21
5
43
45