与归并排序一样,快速排序也使用了分治思想。下面是对一个典型的子数组A[p..r] 进行快速排序的三步分治过程:

分解:数组A[p..r]被划分为两个(可能为空)子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每一个元素都小于等于A[q],而A[q]也小于等于A[q+1..r]中的每个元素。其中,计算下标q也是划分过程的一部分。

解决:通过递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]进行排序。

合并:因为子数组都是原址排序的,所以不需要合并操作:数组A[p..r]已经有序。

算法的关键部分在于分解过程，它实现了对数组A[p..r]的重排。它的基本思想是先从数列中取出一个元素作为基准元素。以基准元素为标准，将问题分解为两个子序列，使小于或等于基准元素的子序列在左侧，使大于基准元素的子序列在右侧。

那么怎么选择基准元素呢？一般来说，基准元素选取有以下几种方法：

取第一个元素。

取最后一个元素。

取中间位置元素。

取第一个、最后一个、中间位置元素三者之中位数。

取第一个和最后一个之间位置的随机数 $k (low \le k \le high)$，选 R[k] 做基准元素。

我们不妨选取第一个元素做基准(记为 pivot)，以说明快速排序的执行过程。我们可以从左向右扫描，找大于 pivot 的数 R[i]，此时从右向左扫描，找小于等于 pivot 的数 R[j] ，然后，让 R[i] 和 R[j] 交换，一直交替进行，直到 i 和 j 碰头为止，这时将基准元素与 R[i] 交换即可。

我发现王晓东的《计算机算法设计分析》快速排序代码有问题。

  while(a[++i] < x);

这句会导致越界，如果大于 i 的小标的元素都比 x 小。

最后下面两句调换也有问题。

  a[p]=a[j];
  a[j] = x;

因为必有$j \le i$, 如果$j < i$ 说明 j 位于左边区域了，必定有 $a[j] \le x$, 可以和 x 交换. 如果$j = i$，说明在临界点，此时有可能$a[j] > x$ , 不能和 j 调换，应该和 j-1 调换。

我使用 java 编写, 经过测试证实了确实有问题.我进行了修改，测试通过。

import java.util.Comparator;
import java.util.List;
import java.util.ListIterator;

/**
 * 容器工具
 * @author yinfeng
 *
 */
public class CollectionsUtil {
	
	/**
	 * 快速排序 
	 * @param list
	 */
    @SuppressWarnings({ "unchecked", "rawtypes" })
	public static  void quickSort(List list) {
        Object[] a = list.toArray();
        quickSortArray(a, (Comparator) null);
        
        ListIterator i = list.listIterator();
        for (Object e : a) {
            i.next();
            i.set((T) e);
        }
    }    
    
    /**
     * 快速排序
     * @param list
     * @param c
     */
	@SuppressWarnings({ "unchecked", "rawtypes" })
	public static  void quickSort(List list, Comparator c) {
		Object[] a = list.toArray();
        quickSortArray(a, (Comparator)c);
        
        ListIterator i = list.listIterator();
        for (Object e : a) {
            i.next();
            i.set((T) e);
        }
    }
    
    public static  void quickSortArray(T[] a, Comparator c) {
        if (c == null) {
        	quickSort2(a, 0, a.length - 1);
        } else {
        	quickSort2(a, 0, a.length - 1, c);
        }
    }

	private static  void quickSort2(T[] a, int p, int r) {
		if(p < r) {
			int q = partition(a, p, r); 
			quickSort2(a, p, q-1); // 对左半段排序
			quickSort2(a, q+1, r); // 对右半段排序
		}
	}
	
	private static  void quickSort2(T[] a, int p, int r, Comparator c) {
		if(p < r) {
			int q = partition(a, p, r, c); 
			quickSort2(a, p, q-1, c); // 对左半段排序
			quickSort2(a, q+1, r, c); // 对右半段排序
		}
	}
	
	/**
	 * 对 partition_wrong 方法进行修改后的版本
	 * @param a
	 * @param p
	 * @param r
	 * @return
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	private static  int partition(T[] a, int p, int r) {
		int i = p, j = r; // j 直接为r值, 不需要调整为 r+1
		
		// x = a[p] 作为划分的基准.
		T x= a[p];
		// 将 < x 的元素交换到左边区域
		// 将 > x 的元素交换到右边区别
		while(true) {
			// 一定要把 i < j 放在第一个条件. 采用 ++i 可以跳过第一个 p 索引,
			// 并且重要的是当 a[++i] >= x 时，要和 j 交换的是增加后 i 索引,
			// 如果修改成 a[i++], 当 a[i++] >=x 时和 j 交换的变成了 i+1 索引, 不匹配.
			// 不使用 <= 0 的原因是认为列表中相等的元素少, 避免每次都需要多一次相等判断.
			while(i < j && ((Comparable)a[++i]).compareTo(x) < 0);
			// 不能把 j 递减放到比较条件中, 比如 a[--j] 是错的，会跳过 r索引.
			// a[j--] 也是错的, 因为当发现 a[j] <= x 时, 要和 i 交换的是 j 而不是
			// j-1.
			// 总结：循环条件中采取后缀的--,++ 会导致条件判断时使用的索引和跳出循环之后
			// 的索引不匹配.
			while(i < j && ((Comparable)a[j]).compareTo(x) > 0) {
				j = j - 1;
			}
			
			if(i >= j)
				break;
			
			swap(a, i, j);
		}
		
		if(((Comparable)a[j]).compareTo(x) < 0) {
			a[p] = a[j];
			a[j] = x;
		}else {
			// 要和 j-1 调换，注意基准要调整为 j-1, 刚开始我就只和 j-1 进行了调换
			// 但是忘记把基准设置为 j-1, 导致返回的是 j.
			j = j-1;
			a[p] = a[j];
			a[j] = x;
		}

		return j;
	}
	
	private static  int partition(T[] a, int p, int r,  Comparator c) {
		int i = p, j = r; // j 直接为r值, 不需要调整为 r+1
		
		// x = a[p] 作为划分的基准.
		T x= a[p];
		// 将 < x 的元素交换到左边区域
		// 将 > x 的元素交换到右边区别
		while(true) {
			while(i < j && c.compare(a[++i], x) < 0);
			while(i < j && c.compare(a[j], x) > 0) {
				j = j - 1;
			}
			
			if(i >= j)
				break;
			
			swap(a, i, j);
		}
		
		if(c.compare(a[j], x) < 0) {
			a[p] = a[j];
			a[j] = x;
		}else {
			j = j-1;
			a[p] = a[j];
			a[j] = x;
		}

		return j;
	}

	/**
	 * 这个是错误的划分，来自王晓东第2版《计算机算法设计与分析》, 我
	 * 直接看出了问题，这里只是测试验证下我的想法.
	 * @param a
	 * @param p
	 * @param r
	 * @return
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	private static  int partition_wrong(T[] a, int p, int r) {
		int i = p, j = r+1;
		
		// x = a[p] 作为划分的基准.
		T x= a[p];
		// 将 < x 的元素交换到左边区域
		// 将 > x 的元素交换到右边区别
		while(true) {
			// yinfeng: 这句会导致越界，如果大于 i 的小标的元素都比 x 小。
			while(((Comparable)a[++i]).compareTo(x) < 0);
			while(((Comparable)a[--j]).compareTo(x) > 0);
			if( i >= j)
				break;
			
			swap(a, i, j);
		}
		/**
		 * 下面两句调换也有问题。因为必有$j \le i$, 如果$j < i$ 说明 j 位于左边区域了，
		 * 必定有 $a[j] \le x$,  可以和 x 交换. 如果$j = i$，说明在临界点，
		 * 此时有可能$a[j] > x$ , 不能和 j 调换，应该和 j-1 调换。
		 */
		a[p] = a[j];
		a[j] = x;
		
		return j;
	}
	
    private static void swap(Object[] x, int a, int b) {
        Object t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

    /**
     * 判断 list 是否排序好的
     * @param list
     * @param asc true: list按升序排序好的; false: list 按降序排序好的.
     * @return
     */
	public static   boolean checkSorted(List list, boolean asc) {
		int end = list.size() - 1;
		boolean success = true;
		if(asc) {
			for(int i = 0; i < end; i++) {
				if(list.get(i).compareTo(list.get(i+1)) > 0) {
					success = false;
					break;
				}
			}
		}else {
			for(int i = 0; i < end; i++) {
				if(list.get(i).compareTo(list.get(i+1)) < 0) {
					success = false;
					break;
				}
			}
		}

		return success;
	}
}

测试代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.ExpectedException;

public class CollectionUtilTest {
	@Rule
	public ExpectedException expected = ExpectedException.none();
	
	
	@Test
	public void quickSortTest1() {
		List  list = Arrays.asList(
				new ArrayList(),
				Arrays.asList(3),
				 Arrays.asList(3, 2),
				 Arrays.asList(2, 3),
				 Arrays.asList(5, 4, 3, 2, 1),
				 Arrays.asList(1, 2, 3, 4, 5),
				 Arrays.asList(1, 4, 3, 7, 2, 5),
				 Arrays.asList(1, 2, 4, 3, 7, 2, 4, 5)
				);
		
	
		for(List o : list) {
			CollectionsUtil.quickSort(o);
			System.out.println(Arrays.toString(o.toArray(new Integer[] {})));
			assert CollectionsUtil.checkSorted(o, true);
		}		
	}
	
	@Test
	public void quickSortTest2() {
		List  list = Arrays.asList(
				new ArrayList(),
				Arrays.asList(3),
				 Arrays.asList(3, 2),
				 Arrays.asList(2, 3),
				 Arrays.asList(5, 4, 3, 2, 1),
				 Arrays.asList(1, 2, 3, 4, 5),
				 Arrays.asList(1, 4, 3, 7, 2, 5),
				 Arrays.asList(1, 2, 4, 3, 7, 2, 4, 5)
				);
		
	
		for(List o : list) {
			CollectionsUtil.quickSort(o, new Comparator() {
				@Override
				public int compare(Integer o1, Integer o2) {
					// o1 不能为空, 见下面sortNullTest 测试
					return o1.compareTo(o2);
				}
			});
			System.out.println(Arrays.toString(o.toArray(new Integer[] {})));
			assert CollectionsUtil.checkSorted(o, true);
		}		
	}
	
	@Test
	public void sortNullTest() {
		List list = Arrays.asList(1, 3, null, 2);
		// 断言排序会抛出空指针异常, 标准的 Collections.sort 也不支持 
		// 空指针排序.
		
		System.out.println("quickSort 空指针异常测试");
		expected.expect(NullPointerException.class);
		CollectionsUtil.quickSort(list);
	}
}