排序算法之快排

####前言
在校期间，曾经也学习过各种排序，依稀还记得当时在 OJ 系统上各种刷题的场景。。。
快排当时的数据结构与算法课程上也学习过，只不过当时已经开始 JAVAEE 课程的学习了，所以对于算法这种东西也就没有大一时候那么痴迷了。如今只记得快排的大致思想了，所以今日抽空重新理清一遍。
####实现
快排的思想如下：
* 将待排序数组拆分成三部分，左边部分比中间数字小（大），右边数字比中间数字大（小）。
* 分而治之，继续将两边的数字按照上面方法拆分，直到不可拆分为止，此时就已经排好序了。

有了以上思想，接下来就该想想如何把小（大）的数放左边，大（小）的数放右边了。
除了上面的问题，还有个问题是，中间数该如何选择？这里很容易出现一个误解，中间数那就是大小排在中间的那个数嘛。这个理解完全错误，数组是待排序的，从何而来的大小排在中间的那个数，这个数只有等到排完序才知道。
所以这个数只能随机选择，所以我们可以直接以数组的第一个数作为这个中间数。

如何将小（大）的数放左边，大（小）的数放右边？
* 从右往左找比中间数小的数
* 从左往右找比中间数大的数
* 交换这个两个数的位置
* 重复以上步骤，直至从左往右找的数组下标大于从右往左找的下标则停止，因为此时数组已经全部遍历完了

最后要做的就是将左右两部分继续当成两个个数组按照上面方法进行处理。代码如下：
```java
public class QuickSort {

private static void sort(int[] arr, int left, int right) {
		if (left >= right)
			return;
		int begin = arr[left];
		int i = left;
		int j = right;
		while (i < j) {
			//从右边开始找到第一个小于begin的位置
			while (arr[j] >= begin && i < j)
				j--;
			//从左边第二个开始找到第一个大于begin的位置
			while (arr[i] <= begin && i < j)
				i++;
			if (i < j) {
				//交换这两个数的位置，即把大于begin的数放右边，小于begin的放左边
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		//最后把begin放在比它大的数和比它小的数的中间
		arr[left] = arr[j];
		arr[j] = begin;
		//分治递归继续重复上面操作
		sort(arr, left, j - 1);
		sort(arr, j + 1, right);
	}

public static void main(String[] args) {
		int[] arr = {2, 5, 1, 9, 6, 8, 3, 7, 4, 2, 5, 11, 20, 3, 1, 2};
		sort(arr, 0, arr.length - 1);
		for (int i = 0; i < arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}
```

排序算法之快排

发表评论：