快速排序：

普通快排：

选取待排序数组的首或尾元素作为枢轴（就是base，我们选出来的比较的数），大于base的放右边，小于base的放左边。

public void quickSort(int[] nums, int low, int high) {if (low >= high) return;int base = nums[low];//基准元素int lIndex = low, rIndex = high;//lIndex是需要交换的最左元素下标，rIndex是最右元素下标while (lIndex < rIndex) {while(lIndex < rIndex && nums[rIndex] >= base) rIndex--;while(lIndex < rIndex && nums[lIndex] <= base) lIndex++;if(lIndex < rIndex) {swap(nums, lIndex, rIndex);}}//经过以上处理得到的lIndex就是base应该放置的下标swap(nums, lIndex, low);quickSort(nums, low, lIndex - 1);//分别对base的左右两侧快排quickSort(nums, lIndex + 1, high);
}
private static void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;
}

很显然对于普通的快排来说只能处理大于base和小于base的情况，对于等于base的情况我们是做的模糊处理（哪边先碰到算哪边的），所以在待排序数组中元素重复度比较高的情况下会退化为O(n^2)。如：4，4，4，4，4，1

我们每次只能一个元素一个元素的拆开，而不是理想情况一半一半的拆，为了处理以上情况有了双路快排。

双路快排：

void doubleQuicklySort(int[] nums, int low, int high) {if(low >= high) return;//index1是左往右（除base外）第一个大于等于base的数的下标//index2是右往左第一个小于等于base的数的下标int base = nums[low], index1 = low + 1, index2 = high;while(true) {while(index1 < index2 && nums[index2] > base) index2--;while(index1 < index2 && nums[index1] < base) index1++;if(index1 >= index2) break;swap(nums, index1, index2);//交换完后我们认为符合左右两边的规律性，所以下一次开始的时候需要从两个下标的后一位开始index1++;index2--;}/*因为上面while中的交换是为了让nums[low](第一个>=base的)和nums[index2](第一个<=base的互换)来保证左右两边的规律性，但是如果在上面第一个while中对于index2的更新因为不满足(index1 < index2)的条件而退出，不是因为不满足(nums[index2] > base)，所以就有可能导致index2指向的数仍然是>=base的所以就没必要调换  eg:3 4 4 5 6可以用这个例子理解*/if(nums[index2] < base)swap(nums, low, index2);doubleQuicklySort(nums, low, index2-1);doubleQuicklySort(nums, index2, high); 
}