快速排序定义
快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码实现
在上图中， l表示最左边的脚标， j表示小于等于v的部分的脚标的最大位置， i表示尚未进行比较的部分的第一个元素位置，然后i不断后移，完成整个数组的比较。在比较过程中， 如果i这个位置的元素>v， 则这个元素归于紫色部分，i直接+1， 移动到下一个位置即可，如果i这个元素小于等于v， 则需要把i这个元素移动到前面橙色部分， 所以把i与 j+1（这个位置为紫色）两个元素交换，然后i移动到i+1的位置,继续进行比较。代码如下：
/**
* 定义好脚标取值范围：
* 对arr[l...r]部分进行快速排序，取值区间前闭后闭
*/
public static void quickSort(int[] arr, int l, int r) {
if(l >= r) {
return;
}
//排序后，位置p左边的数据都小于p,右边的数据都大于p
int p = parttion(arr, l, r);
quickSort(arr, l, p-1);//通过递归继续对左边的数据排序
quickSort(arr, p+1, r);//通过递归继续对右边的数据排序
}
private static int parttion(int[] arr, int l, int r) {
int v = arr[l];//
int j = l;
for(int i=l; i<=r; i++) {
if(arr[i] < v) {
//如果当前数比v小，则把当前数交换到 小于v的集合中
swap(arr, i, j+1);
j++;
}
}
swap(arr, l, j);//把这个中间值 真正的移动到中间位置吗，即在排序完成后， 把v和橙色部分最后一个元素进行交换， 这样左边的都是小于v，右边都大于v
return j;//返回这个中间值的位置
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
快速排序的优化一
高级排序在最后阶段较少数据排序是，都可以使用插入排序进行优化，因为越是高级的排序，实现越是复杂，通常来说在数据较大的效果越是明显，在数据较少时使用插入排序这一种简单排序更加快速。
/**
* 定义好脚标取值范围：
* 对arr[l...r]部分进行快速排序，取值区间前闭后闭
*/
public static void quickSort(int[] arr, int l, int r) {
if(r - l <= 15) {
insertionSort(arr, l, r);
return;
}
//排序后，位置p左边的数据都小于p,右边的数据都大于p
int p = parttion(arr, l, r);
quickSort(arr, l, p-1);//通过递归继续对左边的数据排序
quickSort(arr, p+1, r);//通过递归继续对右边的数据排序
}
// 对arr[l...r]范围的数组进行插入排序
private static void insertionSort(int[] arr, int l, int r){
for( int i = l+1 ; i <= r ; i ++ ) {
int e = arr[i];
int j;
for (j = i; j > l && arr[j-1] > e; j--)
arr[j] = arr[j-1];
arr[j] = e;
}
return;
}
快速排序的优化二
每次选择的最左边的数据作为比较的数，如果每次这个数都刚好是整个数据中的最小数，那么就不能起到将整个数据一分为二的效果，特别是在数据整体趋向于有序时，更有这种可能：
所以，我们每次随机选择一个数，作为用来比较的数，这样就尽量的避免了上述情况， 代码增加了一行，修改如下：
private static int parttion(int[] arr, int l, int r) {
//随机选择一个数，然后交换到最前面，作为比较的数
//这样改的最少，可以直接在原有代码上优化
swap(arr, l, Math.round(r-l) + l);
int v = arr[l];
int j = l;
for(int i=l; i<=r; i++) {
if(arr[i] < v) {
//如果当前数比v小，则把当前数交换到 小于v的集合中
swap(arr, i, j+1);
j++;
}
}
swap(arr, l, j);
return j;//返回这个中间值的位置
}
快速排序的优化三–双路快速排序
上述代码中，都没有考虑一种情况，就是如果数据中有大量重复的数字，那么就这些数字就会集中在在小于等于v 或者 大于等于v的这一端中，从而导致数据没有均匀的分开，有可能退化为上面 优化二所描述的情况。
此时，我们应该尽量把数据都分散开来，尽量均匀的划分为两部分，如下图所示：
此时的代码逻辑调整为：用两个指针i、j分别指向数据的头尾，当前数e小于v时，就存放到前面部分，当数据e大于v时，就存放到后面部分。在代码中只有小于号< 或 大于号 >， 但是实际上，当不满足 <时， 数据是大于等于v的 就移动到了后半部分， 当不满足 > 时， 数据是小于等于v的，就移动到了前半部分， 从而尽量把等于的数据均匀分散到两端。
代码如下：
public static void quickSort2(int[] arr, int l, int r) {
if( r-l <= 15) {
insertionSort(arr,l,r);
return;
}
//排序后，位置p左边的数据都小于p,右边的数据都大于p
int p = partition2(arr, l, r);
quickSort2(arr, l, p-1);//通过递归继续对左边的数据排序
quickSort2(arr, p+1, r);//通过递归继续对右边的数据排序
}
private static int partition2(int[] arr, int l, int r){
swap( arr , l, (int) (Math.random()%(r-l+1)+l) );
int v = arr[l];
// arr[l+1...i) <= v; arr(j...r] >= v
int i = l+1, j = r;
while( true ){
while( i <= r && arr[i] < v )
i ++;
while( j >= l+1 && arr[j] > v )
j --;
if( i > j )
break;
swap( arr , i, j);
i ++;
j --;
}
swap( arr , i, j);
return j;
}
快速排序的优化三–三路快速排序
三路快速排序，如名字一般，就要维护三个索引，分别是小于v的最右边位置索引，大于v的最左边的位置，以及当前指向数据的位置，
- 1、 当 当前位置的数小于v时，就和 等于v的数据集合的第一个位置的数交换，然后 lt++, i++;
- 2、如果当前位置的数大于v，则当前位置 的数和大于v的部分的最小的位置交换，然后gt–, i++;
- 3、如果当前位置的数等于v, 则直接i++即可
代码实现如下：
public static void quickSort3Ways(int[] arr, int l, int r){
if( r - l <= 15 ){
insertionSort(arr,l,r);
return;
}
swap( arr , l, (int) (Math.random()%(r-l+1)+l) );
int v = arr[l];
int lt = l; // arr[l+1...lt] < v
int gt = r + 1; // arr[gt...r] > v
int i = l+1; // arr[lt+1...i) == v
while( i < gt ){
if( arr[i] < v ){
swap( arr, i, lt+1);
i ++;
lt ++;
}
else if( arr[i] > v ){
swap( arr, i , gt-1);
gt --;
}
else{ // arr[i] == v
i ++;
}
}
swap( arr, i, lt );
quickSort3Ways(arr, l, lt-1);
quickSort3Ways(arr, gt, r);
}
附上自动生成测试数组的代码
public static int[] randomArray(int length) {
int[] arr = new int[length];
Random random = new Random();
for(int i=0; i<length; i++) {
arr[i] = random.nextInt(100);
}
//自动生成随机数组，先进行一次原始数据打印
System.out.println(Arrays.toString(arr));
return arr;
}
