快速排序（实现+总结）

快速排序是一种应用非常广泛的算法，它流行的原因首先就是快，在时间复杂度为O(NlogN)的几种算法中，它的效率较高，此外它的实现简单并且能够原地排序（不实用辅助数组），与归并一样，快速排序也使用了分治的思想，因此貌似很多公司面试都喜欢考这个。

基本思想

1、先从数列中取出一个数作为切分元素。
2、对数组进行切分，比切分元素小的数放在左边，比它大的放在右边。
3、对左右区间重复第二步（递归地），直到区间只有一个数。

如图：

算法的关键部分是切分的过程，如下，它实现了对数组的原址重排。
切分开始前，我们将数组打乱后，选取第一个元素 4 为切分元素，此时两个指针 i、j 分别指向位置待切分元素的两端。

首先，我们将 i 向右移动直到发现一个大于 4 的值 6，再将 j 向左移直到发现一个 小于 4 的值 0，并将它们两个交换。

继续将 i 右移，j 左移，并将 9 和 1 交换，可以看到 i 走过的区域都是小于 4 的，同样 j 走过的区域都是大与 4 的。

继续移动 i 和 j ，并将 5 和 3 交换。

继续移动i 和 j，此时 i 已经和 j 相遇过了，交换 j 和 切分元素 4。

得到切分后的数组。

快速排序的切分方法的内循环用递增的索引将数组元素和一个定值比较，这种简洁性也是快速排序的一个优点，很难得排序算法中有这么小的内循环。归并排序和希尔排序一般都比快速排序慢，因为它们还要再内循环中移动数据

上个动图来直观感受一下排序的过程

代码实现

mport java.util.Random;

public class QuickSort {
   

	public static void main(String[] args) {
   
		Random ra = new Random
1
2
3
4
5
6
7