【数据结构】——排序算法——2.2、快速排序

步骤为：

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

public class Qsorta {
	public static void qsort_asc(int source[],int low,int high){
		int i,j,x;
		if(low < high){
			i = low;
			j = high;
			x = source[i];
			while(i<j){
				while(i<j&& source[j]>x ){
					j--;
				}
				if(i<j){
					source[i] = source[j];
					i++;
				}
				while(i<j&& source[i] < x){
					i++;
				}
				if(i<j){
					source[j] = source[i];
					j--;
				}
			}
			source[i] = x;
			qsort_asc(source,low,i-1);
			qsort_asc(source,i+1,high);
		}
		
	}
	
	public static void main(String[] args){
		int[] a = {4,2,1,6,3,-5,85};
		int i;
		qsort_asc(a,a.length-1);
		for(i=0;i<a.length-1;i++)
	 	System.out.println("a" + i + " is "+a[i]);	
	}

}

import java.util.Comparator;
import java.util.Random;
 
public class Quicksort {
    public static final Random RND = new Random();
 
    private static void swap(Object[] array,int i,int j) {
        Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
 
    private static <E> int partition(E[] array,int begin,int end,Comparator<? super E> cmp) {
        int index = begin + RND.nextInt(end - begin + 1);
        E pivot = array[index];
        swap(array,index,end);	
        for (int i = index = begin; i < end; ++ i) {
            if (cmp.compare(array[i],pivot) <= 0) {
                swap(array,index++,i);
            }
        }
        swap(array,end);	
        return (index);
    }
 
    private static <E> void qsort(E[] array,Comparator<? super E> cmp) {
        if (end > begin) {
            int index = partition(array,begin,end,cmp);
            qsort(array,index - 1,index + 1,cmp);
        }
    }
 
    public static <E> void sort(E[] array,Comparator<? super E> cmp) {
        qsort(array,array.length - 1,cmp);
    }
 
}
 
/*
 * more efficient implements for quicksort. <br />
 * use left,center and right median value (@see #median()) for the pivot,and
 * the more efficient inner loop for the core of the algorithm.
 */
class Sort {
 
     public static final int CUTOFF = 11;
 
    /**
     * quick sort algorithm. <br />
     * 
     * @param arr an array of Comparable items. <br />
     */
     public static <T extends Comparable<? super T>> void quicksort( T[] arr ) {
	 quickSort( arr,arr.length - 1 );
     }
 
 
     /**
      * get the median of the left,center and right. <br />
      * order these and hide the pivot by put it the end of
      * of the array. <br />
      * 
      * @param arr an array of Comparable items. <br />
      * @param left the most-left index of the subarray. <br />
      * @param right the most-right index of the subarray.<br />
      * @return T
      */
      public static <T extends Comparable<? super T>> T median( T[] arr,int left,int right ) {
 
		int center = ( left + right ) / 2;
 
		if ( arr[left].compareTo( arr[center] ) > 0 )
			swapRef( arr,left,center );
		if ( arr[left].compareTo( arr[right] ) > 0 )
			swapRef( arr,right );
		if ( arr[center].compareTo( arr[right] ) > 0 )
			swapRef( arr,center,right );
 
		swapRef( arr,right - 1 );
		return arr[ right - 1 ];
      }
 
     /**
      * internal method to sort the array with quick sort algorithm. <br />
      * 
      * @param arr an array of Comparable Items. <br />
      * @param left the left-most index of the subarray. <br />
      * @param right the right-most index of the subarray. <br />
      */
      private static <T extends Comparable<? super T>> void quickSort( T[] arr,int right ) {
		if ( left + CUTOFF <= right  ) {
			//find the pivot
			T pivot = median( arr,right );
 
			//start partitioning
			int i = left,j = right - 1;
			for ( ; ; ) {
				while ( arr[++i].compareTo( pivot ) < 0 ) ;
				while ( arr[--j].compareTo( pivot ) > 0 ) ;
				if ( i < j )
					swapRef( arr,i,j );
				else
					break;
			}
 
			//swap the pivot reference back to the small collection.
			swapRef( arr,right - 1 );
 
			quickSort( arr,i - 1 );		//sort the small collection.
			quickSort( arr,i + 1,right );		//sort the large collection.
 
		} else {
			//if the total number is less than CUTOFF we use insertion sort instead (cause it much more efficient).
			insertionSort( arr,right );
		}
      }
 
 
      /**
       * method to swap references in an array.<br />
       * 
       * @param arr an array of Objects. <br />
       * @param idx1 the index of the first element. <br />
       * @param idx2 the index of the second element. <br />
       */
      public static <T> void swapRef( T[] arr,int idx1,int idx2 ) {
		T tmp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = tmp;
      }
 
 
      /**
       * method to sort an subarray from start to end
       * 		with insertion sort algorithm. <br />
       * 
       * @param arr an array of Comparable items. <br />
       * @param start the begining position. <br />
       * @param end the end position. <br />
       */
      public static <T extends Comparable<? super T>> void insertionSort( T[] arr,int start,int end ) {
		int i;
		for ( int j = start + 1; j <= end; j++ ) {
			T tmp = arr[j];
			for ( i = j; i > start && tmp.compareTo( arr[i - 1] ) < 0; i-- ) {
				arr[ i ] = arr[ i - 1 ];
			}
			arr[ i ] = tmp;
		}
      }
}