package com.wang.sort;
/**
* 快速排序
* 思路：为每一个基数通过分治思想找到合理位置
*
* @author wxe
* @since 0.0.1
*/
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
int i, j, temp, t;
if (low > high) {
return;
}
i = low;
j = high;
// temp就是基准位
temp = arr[low];
System.out.println("我是基准："+temp);
while (i < j) {
// 先看右边，依次往左递减
while (temp <= arr[j] && i < j) {
j--;
}
// 再看左边，依次往右递增
while (temp >= arr[i] && i < j) {
i++;
}
// 如果满足条件则交换
if (i < j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
// 最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
// 递归调用左半数组
quickSort(arr, low, j - 1);
// 递归调用右半数组
quickSort(arr, j + 1, high);
}
public static void main(String[] args) {
int[] arr = {6,1,2,7,9,3,4,5,10,8};
System.out.println("开始");
quickSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+",");
}
}
}
我们来分析一下基本的思路：
-
第一次交换：以6为基准，首先j向前移动，直到遇见比这个基准6小的第一个数为止，然后i向后移动，直到遇见比这个基准数6大的第一个数为止。如图所示：
基准数为6.png
现在我们知道j指向数字5，i指向数字7，我们将这两个数字进行交换，如图所示：
基准数为6.png
第一次交换结束了，首先仍然是j向前移动，直到遇见比这个基准6小的第一个数为止，然后i向后移动，直到遇见比这个基准数6大的第一个数为止。如图所示：
基准数为6.png
现在我们知道j指向数字4，i指向数字9，将两个数字进行交换，如图所示：
图片.png
第二次交换结束了，首先仍然是j向前移动，直到遇见比这个基准6小的第一个数为止，然后i向后移动，直到遇见比这个基准数6大的第一个数为止。如图所示：
基准数为6.png
当j向前移动遇到3停止了，i向后移动也遇到3了，说明i,j相遇了，没有必要再走下去了，这个时候，该是给基数找到了一个新的位置。将基准数与该数进行交换，该数成为新的基准数，而原来的基准数也找到了合适的位置，如图所示：
基准数为6.png
到此为止，第一个基准数找到了合适的位置，此时，我们就需要根据原来的基准数6将数分为两类了，基准数6的数字都是比6小，而基准数6右边的数都是比6大。此时我们需要再以这个基准数为分解将数据分为两部分，并分别对这两部分进行以上步骤的基准数分类。现在我们知道，基准数6分类后的两类数分别为：左边为3,1,2,5,4.右边为9,7,10,8。 -
接下来我们将通过以上步骤对左边数据为基准数找位置。
基准数为3.png
左边数据第一次交换：以3位基准数，首先仍然是j向前移动，直到遇见比这个基准3小的第一个数为止，然后i向后移动，直到遇见比这个基准数3大的第一个数为止。如图所示：
图片.png
当j遇到数字2时停止，然后i开始移动遇到2发现i,j又相遇了，没有必要再走下去了。这个时候，相当于说明给基准数3找到了合适的位置了。进行交换如图所示：
基准数为3.png
到此为止第二个基准数找到了合适的位置。此时，我们根据基准数3将数据分为两类，左边为2,1，右边为5,4。记下来对这两部分进行以上步骤的基准数分类。
-
接下来我们将通过以上步骤对左边数据为基准数找位置。
基准数为2.png
左边数据进行交换：以2位基准数，首先仍然是j向前移动，直到遇见比这个基准2小的第一个数为止，然后i向后移动，直到遇见比这个基准数2大的第一个数为止。
图片.png
现在只剩下两个数，如果j向前移动，没有比2小的数了，只有1，所以j保持不动，i向后移动，在数字1处相遇，此时就为基数2找到了合适的位置，同时也找到了新的基数1.两者进行交换，如图所示：
基准数为2.png -
现在新的基准数为1，只剩下一个数，没有必要再进行任何处理了。如图所示：
基准数为1.png -
接下来我们看看之前3右边数的分类。新的基数为5如图所示：
基准数为5.png -
现在又找到了新的基准数4，只有一个数字了，没有必要进行任何处理了。
基准数为4.png
到此为止，我们把最开始基准数为6左边分类所有的数字的基准数都找到了合适的位置.
-
现在来处理基准数6右边的分类数字，如图所示：
基准数为9.png
第一次交换：j向前移动找到第一个小于基准数9的位置即停止，i向前移动，找到第一个大于基准数9的位置即停止，如图所示：
图片.png
j找到8的时候停止，i指向数字10的时候停止，进行交换，如图所示：
基准数为9.png
第一次交换结束了，j继续向前走，找到8比技术9小，i继续向后走，正好在数字8出相遇，没有必要再走下去了，说明已经为基准数9找到了合适的位置，同时也找打了新的基准数8，两者进行交换，如图所示：
基准数为9.png
现在原来的基准数又把数据分为两部分了，左边为8,7。右边为10。 -
我们先来为左边的数据进行基准数8找合适位置。
基准数为8.png
j找到的第一个小于基准数8的位置，然后接着i向后移动寻找第一个大于基准数8的位置，正好在数字7相遇，没有必要再走下去，说明为基准数8找到了合适位置，也找打了新的基准数7.两者进行交换，如图所示：
基准数为8.png
到此为止，我们原来的基准数8将数据分类好了。 -
左边只剩下7，也就是新的基准数，只有一个数字，不需要进行任何处理了。如图所示：
基准数为7.png - 再来看看基准数9右边的数据，只剩下数字10也是。如图所示：
基准数为10.png
只剩下一个数字，也是新的基准数10，不需要任何处理了。
到此为止，我们通过快速排序的方法将数字排好序了，如图所示：
图片.png
由上分析可知：我们的基准数分别为：6,3,2,1,5,4,9,8,7,10
因此快速排序的最差时间复杂度是O((n²)，它的平均时间复杂度为O(nlogn)
