快速排序算法（自己写）

  快速排序算法的伪代码。

package endual;

public class QuickSortClass {

/**
	public void recQuickSort(int left, int right) {
		
		if(right-left <= 0) {
			
			return ;
			
		}else {
		
			int partition = partitionIn(left,right) ; //返回的是关键词的key经过划分以后的位子
			recQuickSort(left,partition-1); //左边进行划分算法
			recQuickSort(partition+1,right) ; //右边进行划分算法
			
		}

	}
	
	1.把数组或者子数组划分为左边和右边的一组
	2.调用自身对左边的一组数组进行排序（划分排序）
	3.再次调用自身对右边的一组进行排序{划分排序）
	
	这里不需要调用数据项也就是我们说的那个key值。
	选择key值，或者叫做枢纽划分排序的key值
	
	选择枢纽（我喜欢叫做key值）
	partitionInt()方法应该使用什么样的枢纽
	1.应该选择具体的一个数据项的值来作为枢纽，称为数据数列的枢纽可以用单词pivot表示
	2.可以选择任意数据项作为枢纽。为了简便，我们假设总是选择待划分的子数组最右边的数据项作为枢纽的
	3.划分完成以后，如果枢纽被插入到左边和右边数据之间的划分处，那么枢纽就落在排序之后的最终位子了
	听起来虽然似乎不太可能。但是，正因为使用枢纽的关键词的值来划分数组，所以划分之后的左边子数组所包含的
	是所有小于枢纽的数据，右边是大于的。枢纽开始时在右边，但是如果以某种方式把它放在两个字数组之间，枢纽
	就会在正确的位子上了。也就是说，在它最终的位子上了。
	
		public void recQuickSort(int left, int right) {
		
		if(right-left <= 0) {
			
			return ;
			
		}else {
		    long provit = theArray[right] ;
			int partition = partitionIn(left,right,pivot) ; //返回的是关键词的key经过划分以后的位子
			recQuickSort(left,partition-1); //左边进行划分算法
			recQuickSort(partition+1,right) ; //右边进行划分算法
			
		}

	}
	
	当选择右边数组的最右边的数据项作为枢纽的方案的时候，需要修改partitionIntde 方法。从划分过程中，把最右端
	的数据项排除在外面。这个数据项在划分过程中完成之后应该在什么位子已经很清楚了的。
	
	**/
	
	
	
}

 

   划分算法---快速排序算法的核心

 

   快速排序

从划分开始

划分
划分是快速排序的根本机制，但是划分本身也是一个有用的操作，所以我们重点要介绍下划分。
   划分数据就是把数据分为两组，使所有关键词大于特定的数据项在一组，使所有关键词小于特定值的数据项在另一组。
   
 很容易想象划分数据的情况：
     比如现在有工人的信息。将工人的信息分为两组：家住距离工厂15公里以及15公里内的和家住距离工厂15公里以外的。
     比如学习管理者想把学生分成年级平均成绩分为及格和不及格，以此来判定哪些学生应该在主任掌握的名单上。
     
   那么我们来做一个例子吧：
   我们在成绩表上会这样的，按照学号排序着，但是现在要把成绩分为60分以上和60分一下吧，比如用60这个作为关键词（划分点，
   枢纽）。比关键词大的在右边，比关键字小的在左边（来来来，我们想想希尔排序，这个可比希尔排序的基本排序严格多了哦）。
  但是经过划分以后，左边的数据并没排序好的，右边的数据也没排序好的，举个划分好的例子吧：
  
  45,43,54,21,43，【60】，78,98,78,65,67
  
 划分之后的数据还不能称呼为有序的，这只是简单的把数据划分为两组。但是数据还是比没划分之前要更接近有序了。
 划分是不稳定的，也就是说，每一组中的数据项并不是按照它原来的顺序排序的。事实上，划分往往会颠倒组中一些数据的顺序。
 划分有单独的程序。
 划分算法由两个指针开始工作，两个指针分别指向数组的两头。（这里使用指针这个词是指示数组数据项的，而不是C++中所说的指针。
 在左边的指针，leftPtr,向右移动，而在右边的指针，rightPtr,向左边移动。
 
 
 划分算法的效率
 划分算法运算的时间复杂度是N

 

     划分算法的代码

 

   package endual;

//划分数据的程序
public class Partition {

	private long[] theArray ;
	private int nElems ;
	
	public Partition(long[] theArray, int nElems) {
		super();
		this.theArray = theArray;
		this.nElems = nElems;
	}
	
	public void dispay() {
		System.out.println("显示划分好以后的数据") ;
		for (long a : this.theArray) {
			
			System.out.println(a);
			
		}
	}// end dispay
	
	public int partitionIt(int left, int right, long pivot) {
		
		int leftPtr = left - 1 ;
		int rightPtr = right - 1 ;
		
		while (true) {
			
			while (leftPtr < right && theArray[++leftPtr] < pivot) {
				
			}
			
			while (rightPtr < left && theArray[--rightPtr] > pivot) {
				
			}
			
			if (leftPtr >= rightPtr) {
				break ;
			}else {
               
				swap(leftPtr, rightPtr) ;
				
			}	
		}	//end while
		
		return leftPtr ; //返回的是枢纽或者key关键词在数组中的位子
	}

	private void swap(int leftPtr, int rightPtr) {

       long temp ;
       temp = this.theArray[leftPtr] ;
       this.theArray[leftPtr] = this.theArray[rightPtr] ;
       this.theArray[rightPtr] = temp ;
		
	}

}

 

 

  快速排序算法理论

 快速排序的算法

毫无疑问快速排序是最流行的算法。因为有充足的理由，在大多数情况下，快速排序都是最快得。执行时间是NlogN.
这只是在内排序中或者说事在随机存储器而言的，对于在文件中的排序，可能其他的排序算法更加好。快速排序是1962年发现的。



为了理解快速排序算法，我们要非常理解划分算法。快速排序算法本质上通过把一个数组划分为两个数组，然后递归地调用自身为
每个子数组进行快速的排序来实现的。
但是，对于这个基本的设计还需要进行一些加工。算法还必须需要选择key值以及对于小的划分区域进行排序。看过这个主要算法的简化
代码以后。还需要对其进行求精。

   在理解快速排序的道理之前想知道快速排序干的是什么，我们先给出了快速排序的代码吧
   
   

 

代码