快速排序——java递归实现

package com.bjsxt.test;

import org.junit.Test;

/**
 * 递归实现快速排序算法
 * @author jsqiu
 *
 */
public class FastSort {

	@Test
	public void quick_sortTest() {
		int[] a = new int[] { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85 };
		quick_sort(a, 0, a.length-1);
	}

	void quick_sort(int s[], int begin, int end) {
		if (begin < end) {
			// Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
			int i = begin, j = end, x = s[begin];
			while (i < j) {
				while (i < j && s[j] >= x)
					// 从右向左找第一个小于x的数
					j--;
				// 很多人认为既然前面判断了i<j,这里就不用再判断一遍了，其实这个判断很重要。
				// 例如此时进while时i=4,j=5，前面while的判断把j减1了，如果不加这个判断
				// s[i++] = s[j]会把i加1，最终变成i=6,j=5，后面就乱套了,不信你可以试试。
				if (i < j) 
					s[i++] = s[j];

				while (i < j && s[i] < x)
					// 从左向右找第一个大于等于x的数
					i++;
				if (i < j)
					s[j--] = s[i];
			}
			s[i] = x;
			for (int index = 0; index < s.length; index++) {
				System.out.print(s[index] + " ");
			}
			System.out.println();
			quick_sort(s, begin, i - 1); // 递归调用
			quick_sort(s, i + 1, end);
		} else {
			return; // 这句加不加都没关系，方便理解加了这个else
		}
	}

}