目录

快速排序

基本思想

​代码设计

代码实现

时间、空间复杂度

快速排序的优化

三数取中法：

修改的代码

完整代码

快速排序是不稳定的。

基本思想

快速排序是选择一个关键值作为基准值，比基准小的在左边（一般是无序的），比基准大的在右边（一般是无序的），依次递归，达到总体都有序。

递归地对两个序列进行快速排序，直到划分的序列为空或者只有一个元素。

代码设计

1. 定义temp，left，right

        left，right分别为左右边界;

        temp存放基准，一般定义temp=arr[left];

从右边界开始遍历，right--，若arr[right]

从left开始遍历，left++，若arr[left]>temp,arr[right] = arr[left];

直到left == right,则说明第一趟排序完成。排序为 小于temp的所有值 temp 大于temp的所有值；

2. 通过return得到当前left，即temp存放的位置，定义index=left；

用递归实现 partition（arr，left, right）;

判断index的左右两边的元素是否大于2，左边：index-1>left(left …… index-1)，右边index+1

使用partition方法对左右两边进行排序。

代码实现

public class QuickSort {
    public static >int partition(T[] arr,int left,int right){
        T temp = arr[left];
        while (leftleft;i--){
                if(arr[i].compareTo(temp)<0){
                    arr[left] = arr[i];
                    break;
                }
            }
            right = i;
            int j = left;
            for(;j0){
                    arr[right] = arr[j];
                    break;
                }
            }
            left = j;
        }
        arr[left] = temp;
        return left;
    }
    public static> void quick(T[] arr,int left,int right){
        int index = partition(arr,left,right);
        if(index-1>left){
            quick(arr,left,index-1);
        }
        if(index+1> void quickSort(T[] arr){
        quick(arr,0, arr.length-1);
    }
    public static void main(String[] args) {
        Integer arr[] = {2,1,3,5,9,4,6,7,3,2,11,32,21,22,12,5,13};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

时间、空间复杂度

空间复杂度 O(1)

时间复杂度：O(nlog2^n)

最差时间复杂度：O(n^2)

快速排序的优化

        对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。即为，基准的选择是很重要的，选择基准就意味着，分割后的两个子序列的长度。

        最理想的方法是将序列分割为相等长度的子序列，但要找到算法的中间值，计算量太大。一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形，并且减少快排大约14%的比较次数。也可以左中右三个中选取扩大到五个元素中或者更多元素中选取。

三数取中法：

具体思想：对待排序序列中left、mid、right三个位置上数据进行排序，取他们中间的那个数据作为枢轴，并用0下标元素存储枢轴。
即：采用三数取中，并用0下标元素存储枢轴。

修改的代码

    public static> void swap(T[] arr,int index1,int index2){
        T temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    public static > T selectPivotMedianOfThree(T[] arr,int left,int right){
        int mid = left+((right-left)>>1);
        if(arr[mid].compareTo(arr[left])>0){
            swap(arr,mid,left);  // 保证 arr[mid]<=arr[left];
        }
        if(arr[mid].compareTo(arr[right])>0){
            swap(arr,mid,right); // 保证 arr[mid]<=arr[right];
        }
        if(arr[left].compareTo(arr[right])>0){
            swap(arr,left,right); // 保证 arr[left] <= arr[right];
        }
        // 保证 arr[mid]<=arr[left]<=arr[right];
        return arr[left];
    }

获得的返回值，即为第一个temp存放的值 

完整代码

import java.util.Arrays;

public class QuickSort {
    public static> void swap(T[] arr,int index1,int index2){
        T temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    public static > T selectPivotMedianOfThree(T[] arr,int left,int right){
        int mid = left+((right-left)>>1);
        if(arr[mid].compareTo(arr[left])>0){
            swap(arr,mid,left);  // 保证 arr[mid]<=arr[left];
        }
        if(arr[mid].compareTo(arr[right])>0){
            swap(arr,mid,right); // 保证 arr[mid]<=arr[right];
        }
        if(arr[left].compareTo(arr[right])>0){
            swap(arr,left,right); // 保证 arr[left] <= arr[right];
        }
        // 保证 arr[mid]<=arr[left]<=arr[right];
        return arr[left];
    }
    public static >int partition(T[] arr,int left,int right){
        T temp = selectPivotMedianOfThree(arr,left,right);
        while (leftleft;i--){
                if(arr[i].compareTo(temp)<0){
                    arr[left] = arr[i];
                    break;
                }
            }
            right = i;
            int j = left;
            for(;j0){
                    arr[right] = arr[j];
                    break;
                }
            }
            left = j;
        }
        arr[left] = temp;
        return left;
    }
    public static> void quick(T[] arr,int left,int right){
        int index = partition(arr,left,right);
        if(index-1>left){
            quick(arr,left,index-1);
        }
        if(index+1> void quickSort(T[] arr){
        quick(arr,0, arr.length-1);
    }
    public static void main(String[] args) {
        Integer arr[] = {2,1,3,5,9,4,6,91,67,45,76,98};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}