划分是快速排序的根本机制，主要是把数组分为两组：小于关键字的数据项在一组，大于关键字的数据项在一组。
/** * 划分数据 * * @param left 左边数据 * @param right 右边数据 * @param pivot 参照值 * @return */ public static int partitionIt(int left, int right, int pivot, int[] arr) { // 左边指针 // 左边数据-1，为了后面执行++leftPrt操作时，数据能正确+1 int leftPrt = left - 1; // 右边指针 // 右边数据-1，为了后面执行--rightPrt操作时，数据能正确-1 int rightPrt = right + 1; while (true) { // 左边数据比参照值的小，不做后续操作，循环 while (leftPrt < right && arr[++leftPrt] < pivot); // 右边数据比参照值的大，不做后续操作，循环 while (rightPrt > left && arr[--rightPrt] > pivot); if (leftPrt >= rightPrt) { break; } else { // 交左右两边的数据 swap(leftPrt, rightPrt, arr); } } return leftPrt; } /** * 数据交换 * * @param index1 入参1 * @param index2 入参2 * @param arr 比较数组 */ public static void swap(int index1, int index2, int[] arr) { int temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; }
算法中，我们可以这样理解：leftPrt是左边指针，rightPrt是右边指针，他们在数组下方移动（可以想象成两个人面对面行走）。
当leftPrt遇到比pivot（参照值）大时，跳出循环，此时leftPrt记录的是：大于pivot的数值所在的位置，即arr[leftPrt] > pivot；
当rightPrt遇到比pivot（参照值)小时，跳出循环，此时rightPrt记录的是：小于pivot的数值所在的位置，即arr[rightPrt] < pivot；
这时，找到的arr[leftPrt] ，arr[rightPrt] 都不在正确位置上，需要交换。
具体示例：
/** * 测试函数 * @param args */ public static void main(String[] args) { int[] arr = { 90, 100, 20, 60, 80, 110, 120, 40, 10, 30, 50, 70 }; partitionIt(0, arr.length - 1, 55, arr); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } }
代码执行过程中数组数据项：
可以看到leftPrt和rightPrt都在相互靠拢着移动，当leftPrt >= rightPrt时，循环结束。
划分的效率：运行时间为O(N)。