快速排序

简洁版：

	public static void sort(int arr[], int i, int j) {
		if (i  >= j)return;
		int front = i, rear = j;
		int tmp = arr[i];

		while (i < j) {
			while (arr[j] > tmp && i < j) {
				j--;
			}
			if (i < j) {
				arr[i] = arr[j];
				i++;
			}

			while (arr[i] < tmp && i < j) {
				i++;
			}
			if (i < j) {
				arr[j] = arr[i];
				j--;
			}
		}

		arr[i] = tmp;
		sort(arr, front, i);
		sort(arr, i + 1, rear);
	}

我想讲一下大体的思路，因为我知道现在我记得，但以后时间隔久了就忘了。所以及时写下思路。

首先说快排的总体思想。任意选一个值作为“标兵”，找到一个位置，把这个“标兵”放下后，“标兵”左边都比它小，“右边”的元素都比标兵大。
这个就是快排最基础的子问题就是这个。
整个快排就是把问题集不断切分，用上面这个一样的过程去跑。

其次，我们具体说说这单次过程，就是这个最基础的子问题是怎么来做的。
1.选标兵，可以任意选，但我们一般方便都选第一个。
2.就是调整位置的过程了。
标兵存在tmp，
round 1：
从最后开始找，找到第一个比标兵小的（该数据点位置j），存到标兵原来的位置上(i)。
再从标兵原位置往前一格(i+1)，找到第一个比标兵大的，存到j位置上。

round 2：
从j-1开始找，。。。。(j)，。。。。(i)
....

....如此循环 这样最终i j变为相等的值了。这样才算第一轮的排序完成了。是按照第一个点作为标兵排好序了。

后面就是把大的问题切分成不断的子问题，递归做。
一开始的起始用front=i, rear=j,保存
最后递归用 sort(arr, front, i), sort(arr, i+1, rear)来做。

------
//if (i + 1 >= j)return; 错
//if (i == j)return; 错
谈一下这个递归的停止条件为什么是 i >= j

首先i>j 肯定要停下来，i==j也要停下来，这个都很好理解。
但是用 i==j是不是就够了呢？不行。因为中间的交换会导致i++，i加了不少，
那么最后的sort(arr, i+1, rear),这里i+1 可能会比rear=j大很多。虽然一开始i是小于j的，但是由于中间i++加了好多位，最后悔导致i+1还大于rear=j，所以要加上 i>=j, 而不是i==j

i+1 >= j 这个是不对的。例子，如arr={5,2}，如果你有+1就停下来，那肯定没排好序。



有问题的写法：

	public static void sort(int arr[], int i, int j) {
		if (i + 1 >= j)return;
		int front = i, rear = j;
		int tmp = arr[i];

		while (i < j) {
			while (arr[j] > tmp && i < j) {
				j--;
			}
			//if (i < j) {
				arr[i] = arr[j];
				i++;
			//}

			while (arr[i] < tmp && i < j) {
				i++;
			}
			//if (i < j) {
				arr[j] = arr[i];
				j--;
			//}
		}

		arr[i] = tmp;
		sort(arr, front, i);
		sort(arr, i + 1, rear);
	}

你可能会觉得一开始有while(i < j)的限制，另外每次对j--，即往前移，还有对i++，即往前移，都有while (arr[j] > tmp && i < j)和while (arr[i] < tmp && i < j)，其中包括了i < j的限制了，再在赋值的地方添加一个i < j的条件判断，貌似有点画蛇添足。

其实不是。去掉那个i < j的条件判断会出错。
出错的原因在于，有可能一个东西在上面那个arr[i] = arr[j]; 赋完值，后面这个i++，把i的值修改了。如果下面那个赋值语句arr[j] = arr[i]; j--; 外面没有包一层 if(i < j),那么这里就出错了。




完整版：

package sort;

public class QuickSort {
	public static void main(String[] args) {
		int[] arr = { 49, 38, 65, 97, 76, 13, 27 };
		int i = 0, j = arr.length - 1;
		sort(arr, i, j);

	}

	public static void sort(int arr[], int i, int j) {
		if (i + 1 >= j)
			return;
		int front = i, rear = j;
		int tmp = arr[i];

		while (i < j) {
			printArray(arr, i, j);
			while (arr[j] > tmp && i < j) {
				j--;
			}
			if (i < j) {
				arr[i] = arr[j];
				i++;
			}

			printArray(arr, i, j);
			while (arr[i] < tmp && i < j) {
				i++;
			}
			if (i < j) {
				arr[j] = arr[i];
				j--;
			}
		}

		arr[i] = tmp;

		printArray(arr, i, j);
		sort(arr, front, i);
		sort(arr, i + 1, rear);
	}

	public static void printArray(int[] arr, int i, int j) {
		for (int k = 0; k < arr.length; k++) {
			System.out.print(arr[k] + ",");
		}
		System.out.print("i:" + i + ", j:" + j);
		System.out.println();
	}
}

为什么快排能做到nlog(n)的时间效率,就是因为它可以比较平衡的切分问题，变为子问题。
应该还记得那个计算时间的方式吧，就是一颗颗子树画下去，求和。
所以才会出现log（n）对数。

如果不能均衡切分子问题，那么你就想象那棵树就会退化成线性的了。
那么为什么不能均衡切分呢，因为大或小的数字始终在“标兵”数字的一边。

更具体的说，我们是取第一个值做“标兵”，并且从小到到大排。
那么最低效的情形就是，整个序列已经自小到大有序了。

这个时候就是n平方的时间复杂度了。





百度百科（快排）：
http://baike.baidu.com/view/19016.htm