【数据结构】——排序算法——2.2、快速排序
一、先上维基的图：
图二、快速排序实例
| 分类 | 排序算法 |
|---|---|
| 数据结构 | 不定 |
| 最差时间复杂度 | |
| 最优时间复杂度 | |
| 平均时间复杂度 | |
| 最差空间复杂度 | 根据实现的方式不同而不同 |
二、描述
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。举个例子，军训时第一次集合，大家一时间混乱了，不知道怎么排，这时候教官随便抓了个人，说以该同学为基准，高的站左边，矮的站右边。此时，基本就把队伍分为高低两大阵营。那么，在每个小区间内，又进行同样的操作，迭代到每个区间内只有一个人，那么操作便结束了！
步骤为：
- 从数列中挑出一个元素，称为"基准"（pivot），
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
三、Java程序
非wiki版：
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]);
}
}
wiki版：
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;
}
}
}
