java实现快速排序（快排）

快速排序原理

快速排序（Quicksort）我们习惯的把它简称 ‘快排’。快排利用的也是分治思想。

快排思想大概是这样的：如果要排序数组下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。

遍历p到r之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据被分成了三部分，前面 p 到 q-1 之间都是小于 pivot，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。

根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标 q+1 到 r 之间的数据，直到区间缩小为1，将说明所有的数据都有序了。

快速排序实现过程

我们还是用上次那组数据进行过程分析（arr[8, 5, 9, 1, 3, 2, 4]）。
首先我们得找一个 pivot ，这个点随便是数组中的一个点就可以一般习惯的使用数组的第一个元素做为 pivot 即pivot = 8 。然后从数组的两端进行探测，先从右往左找一个小于 8 的数字，再从左往右找一个大于 8 的数字，然后交换他们的位置。这里我们可以使用两个变量 i 和 j 分别指向数组的首位与末位 i=0即arr[i]=8；j=6 即arr[j]=4

i						j
8	5	9	1	3	2	4
pivot

然后从右往左查找小于pivot数字即arr[j] = 4，再从左往右查找大于pivot数字即arr[i]=9。交换得到如下结果：

		i			j
8	5	4	1	3	2	9
pivot

继续做上面的操作，j--,i++,直到找到符合条件的数停下来，但是这一次情况有点特殊你会发现j的位置还是不动i的位置一直再 ++ 直到i和j相遇了，尽管 i++ 这次没有找到符合条件的数可是他已经和j相遇了所以就要停下来就变成了下面的这个样子。

					i,j
8	5	4	1	3	2	9
pivot

现在需要将 pivot 与相遇的点的数字进行交换 如下：

2	5	4	1	3	8	9

到这里一轮的探测就结束了，也就是以 8 作为分界点 将原数组分为三部分即 [2，5，4，1，3]，8，[9],现在我们需要对8左右两边的数组分别做如上的处理，首先我们先处理左边的数据。

i				j
2	5	4	1	3
pivot

这一块我不详细的说明了，方法适合上面一样的，如果你模拟的没错的话得到的结果应该是下面的这个样子：

1	2	4	5	3

这一次探测又将数组分为了三部分即[1],2,[4,5,3]。我们继续将其分为左右两边进行处理，由于左边只有一个元素所以不需要进行任何处理，右边经过探测处理后得到如下的结果：

3	4	5

这次探测将数组同样的也分为了三部分，刚好左右两边都只有一个数据所以都不需要做处理。
然后我们在对[9] 进行探测同样由于只有一个元素所以不用做任何处理。
至此排序到此结束，得到一下的结果：

1	2	3	4	5	8	9

其实快排 就是每次将pivot 进行归位，直到所有的数据都归位后排序就结束了。
下面我用一张手绘图来描述一下整个的算法归位过程：

（字实在是太丑了，下次不手绘了😭😭）

代码实现

public class QuickSort {
  public static void quickSort(int[] arr, int start, int end) {
    if (start > end) return;
    int i, j, tmp, t;
    i = start;
    j = end;
    tmp = arr[i];

    while (i < j) {
      while (arr[j] >= tmp && i < j) j--;
      while (arr[i] <= tmp && i < j) i++;
      if (i < j) {
        t = arr[j];
        arr[j] = arr[i];
        arr[i] = t;
      }
    }
    arr[start] = arr[i];
    arr[i] = tmp;
    quickSort(arr, start, i - 1);
    quickSort(arr, i + 1, end);
  }

  public static void main(String[] args) {
    int[] arr = {8, 5, 9, 1, 3, 2, 4};
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
  }
}