快速排序

LoveArx

Quicksort probably is the most used sorting algorithm than any other, thanks to the relatively simple implementation and yet has great performance on a variety of input datas. That doesn't mean there is no shortcoming though. Quicksort is recursive, not stable, and fragile: which a small implementation mistake can go unnoticed until a spectacular disaster happens. On average quicksort does N log N operations for N number of elements, but on the worst case scenario it takes N^2 operations! Sometime programmers choose shellsort over quicksort due to the possible exploitation of its worst case of N^2 operations, or the effort of making sure correct quicksort implementation just cannot justify the application - especially when the sort mainly processes only small amount of input data. Quicksort however does outperform shellsort up to 10 times more for huge number of elements.

This article will be relying on the applet below. The basic idea for this sort is to first select a pivot, and then partitioning the array so anything smaller than the pivot comes before it and the one larger than the pivot comes after it, and lastly recursively partitioning the partitioned sub-arrays until there is no more sub-array to partition. The applet helps to visualize this process, take a look at it. The yellow bar is the pivot currently selected. At this time just observe how elements are swapped during the partitioning process. Also notice a new sub-array (bounded by blue and red vertical lines) is selected for partitioning whenever the yellow bar itself is swapped.

quicksort

Applet: Basic quicksort animation. Deliberately slowed down to emphasize the exchanges.

There are quite a few ways for selecting the pivot. For simplicity we'll take the last element as the pivot instead. At first the whole array is the sub-array itself so the last element in the array becomes the first pivot. In the applet the pivot is represented by a yellow bar, and the current sub-array is bounded by the blue and red vertical line. To partition the sub-array, starting from the blue vertical line search forward to find an element larger than the pivot and mark this index as left (blue bar). Next starting from the red line search backward to find an element smaller than the pivot and mark the index as right (red bar). Now if left and right has not yet crossed, swap the two element. Keep looking forward and backward starting from the last left and right. When left and right crosses each other swap the pivot with the element currently pointed by left. This completes the partitioning process of a single sub-array. Now the array is already partitioned into two sub-arrays where one of it contains elements less than the pivot and the other one contains elements larger than the pivot. Continue by recursively partitioning on these sub-arrays until there is no more sub-arrays to partition.

Java implementation
Note that this is the very basic of quicksort implementation without any kind of improvement, as such the last element in a sub-array will always be selected as the pivot. The applet above used this method. There are two types of implementation here, the first a "normal" quicksort, and the second similar except without recursion.

1. Basic quicksort.

[C++] 纯文本查看 复制代码

/**
* Quicksort data. Sort starts from here.
* 
* @param data Array to sort. 
*/
public void quicksort(int[] data) {
    // starts by sorting the full array.
    sort(data, 0, data.length-1) ;
}

/**
* Sort a sub-array.
* 
* @param a Array to sort.
* @param l Partition left.
* @param r Partition right.
*/
public void sort(int a[], int l, int r) {
    if (r <= l) return ;

    // start partitioning array using element at r as pivot
    int i = l-1, j = r, pivot = a[r], v ;
    while (true) {
        // scan forward (left to right)
        while (a[++i] < pivot) ;
        // scan backward (right to left)
        while (pivot < a[--j]) if (j == l) break ;
        // stop when left and right crosses
        if (i >= j) break ;
        // no crossing yet so we swap left-i and right-j
        v = a ;
        a = a[j] ;
        a[j] = v ;
    }
    // swap pivot and left-most element
    v = a ;        
    a = a[r] ;
    a[r] = v ;    

    // at this point partitioning is complete

    // recursively sort left partition
    sort(a, l, i-1) ;
    // recursively sort right partition
    sort(a, i+1, r) ;        
}

2. Basic quicksort without recursion.

[C++] 纯文本查看 复制代码

/**
 * Start quicksorting an array.
 * 
 * @param data Array to sort. 
 */    
public void quicksort(int[] data) {
    quicksort(data, 0, data.length-1);
}

/**
 * Start quicksorting a sub-array.
 * 
 * @param a Sub-array to sort.
 * @param l Left index.
 * @param r Right index. 
 */
public void quicksort(int[] a, int l, int r) {
    Stack s = new Stack() ;        
    s.push(l);
    s.push(r);
    int i, j, k, v, pivot ;
    while (!s.isEmpty()) {
        r = (Integer)s.pop(); 
        l = (Integer)s.pop() ;
        if (r <= l) continue ;

        // start partitioning
        i = l-1; 
        j = r; 
        pivot = a[r] ;
        while (true) {
            // scan forward (left to right)
            while (a[++i] < pivot) ;
            // scan backward (right to left)
            while (pivot < a[--j]) if (j == l) break ;
            // stop when left and right crosses
            if (i >= j) break ;
            v = a[i] ;
            a[i] = a[j] ;
            a[j] = v ;
        }
        v = a[i] ;        
        a[i] = a[r] ;
        a[r] = v ;
        // end partitioning

        if (i-l > r-i) {
            s.push(l) ;
            s.push(i-1) ;                
        }
        s.push(i+1) ;
        s.push(r) ;
        if (r-i >= i-l) {
            s.push(l);
            s.push(i-1) ;
        }
    }
}

gjg_detail

经典