时间复杂度为O(nlogn)的算法

柔情只为你懂 2021-10-01 09:34 372阅读 0赞

# mergeSort #

## 口诀： ##

左拆分，左合并，右拆分，右合并，最后合并左右。

## 归并排序的逻辑 ##

### 归并排序的战略（宏观）逻辑 ###

先将原数组拆分为arr.length个小数组，每个数组长度为1。
    小数组之间合并，进行第一次合并
    第一次合并后，此时大数组分为了arr.length/2个小数组，每个小数组有两个元素，再次合并
    每次合并后，将新的最小数组合并。

拆分的逻辑是递归，需要先推导出递归的公式和退出低轨的条件：

忽略常数项 参数l,r代表数组左右索引，数组允许左右索引想等
    mergeSort(l,r) = merge(mergeSort(l,p),merge_sort(p+1,r))
    退出条件为：
    l>=r

### 归并排序合并的逻辑 ###

本质：最小数组（左右数组）元素之间的比较，构造一个有序数组，完成合并

while循环，左右数组均从个字其实索引位开始比较，并将本次比较的小值放到临时数组中。直到一侧数组中所有元素都放入了临时数组（即一侧数组元素清空）
    判断余下了那测数组，将该测数组遍历并放入临时数组中（此时是一测数组内部循坏，没测数组都是有序的，所以直接遍历赋值即可）
    将新数组遍历赋值给原数组

![18721752-c6cc0f90f07596a7.png][]

image.png

代码实现

//递归拆分，直到拆分到最小数组长度为1
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        int mid = (left+right)/2;
        if (left<right){
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right,temp);
            merge(arr,left,mid,right,temp);
        }
    }
    //合并
    private static void merge(int[] arr, int left,int mid, int right, int[] temp) {
        //左侧数组的索引，赋予初始值为左侧数组的起始索引
        int leftIndex = left;
        //右侧数组的索引，赋予初始值为右侧数组的起始索引
        int rightIndex = mid+1;
        int tIndex = 0;
        //todo 最小数组之间的元素比较并给临时数组赋值   eg:数组中四个元素，左右各两个元素，左面数组和右侧数组均从起始索引遍历，放入临时数组
        while(leftIndex<=mid && rightIndex<=right){
            //起始判定：左侧数组最小值，和右侧数组最小值比较， 左右数组都从各自的起始元素开始比较，放入临时数组，跳出循环的条件为，当一侧数组先比较完，即出现一侧数组清空的情况，跳出循环。
            //注意此处一定要是<=  为了应对值相同的场景，保证其的稳定性
            if (arr[leftIndex]<=arr[rightIndex]){
                temp[tIndex] = arr[leftIndex];
                leftIndex++;
                tIndex++;
            }else {
                temp[tIndex] = arr[rightIndex];
                rightIndex++;
                tIndex++;
            }
        }
        //todo 将剩下的值都放到临时数组中
        //判断哪测数组清空了，将未清空的一侧数组按照其索引位开始遍历，放到临时数组中（没测数组均是有序的）
        while (leftIndex <= mid){
            temp[tIndex] = arr[leftIndex];
            tIndex++;
            leftIndex++;
        }
    
        while (rightIndex<=right){
            temp[tIndex] = arr[rightIndex];
            tIndex++;
            rightIndex++;
        }
        //todo 将临时数组复制给arr  可以直接遍历赋值，因为原数组的这部分元素都在临时数组中
    
        int arrIndex = left;
        tIndex = 0;
        while (arrIndex<=right){
            //   System.out.println(tIndex+"-----------"+arrIndex);
            arr[arrIndex] = temp[tIndex];
            arrIndex++;
            tIndex++;
        }
    }

## 归并思想： ##

将一组数据拆分至最小单元，在将最小单元合并，合并的过程中进行排序，合并直到最小单元长度等于元数据长度。

## 性能分析 ##

### 内存消耗 ###

O(n)  
实际上，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

### 稳定性 ###

是否稳定决定于代码21行  
if (arr\[leftIndex\]<=arr\[rightIndex\])  
如果判断条件是<=那就是稳定的，如果判断条件是<而不是<=就是不稳定的。

### 执行效率 ###

最好，最坏，平均都是O(nlogn)

这里分析时间复杂度，和之前有点不同，因为通过递归实现的，所以这里的时间复杂度即分析递归的时间复杂度。

##### 递归代码时间复杂度推导过程 #####

首先先看一下递归的使用场景  
一个问题 a 可以分解为多个子问题 b、c，那求解问题 a 就可以分解为求解问题 b、c。问题 b、c 解决之后，我们再把 b、c 的结果合并成 a 的结果。

###### 递归代码的时间复杂度： ######

如果我们定义求解问题 a 的时间是 T(a)，求解问题 b、c 的时间分别是 T(b) 和 T( c)，那我们就可以得到这样的递推关系式：  
T(a) = T(b) + T(c) + K  
其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。

###### mergeSort的时间复杂度： ######

我们假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。我们知道，merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：

T(1) = C；   n=1时，只需要常量级的执行时间，所以表示为C。
    T(n) = 2*T(n/2) + n； n>1

2\*T(n/2)为每个子数组排序的时间  
n为合并两个子数组的时间，merge() 函数合并两个有序子数组的时间复杂度是 O(n)  
以上只是一次merge的时间函数，如果在以上的基础上再次拆分：

T(n) = 2*T(n/2) + n
         = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n       //进行两次合并
         = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
         = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
         ......
         = 2^k * T(n/2^k) + k * n
         ......

当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 k=log2n 。我们将 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。  
大O分析，则得出时间复杂度为：

O(nlogn)

归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)，这种排序算法，和原数组是否有序无关。

# 快速排序 #

## 排序逻辑 ##

通过不断递归二分，不断将数组分成两组，左侧组所有元素都比右侧组所有元素小，在和中间值比较的过程中，先到达中间位置的一侧负责控制另一侧的索引，让另一组合中间值比较与交换中间值，也就是另一组和中间值排序。

*  从数列中挑出一个元素，称为 “基准”（pivot）；
 *  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 *  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

## 递归公式 ##

quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)
    
    终止条件：
    p >= r

code

public static void quickSort(int[] arr,int left,int right){
            //todo 首次分组通过中间值，制造两组，左面小于中间值，右面大于中间值，后面每次都在各自组中再次分组，直到中间值等于最小值或者等于最大值。
            int leftIndex = left;
            int rightIndex = right;
            int middleValue = arr[(leftIndex + rightIndex)/2];
            //左少 -1,1,2,0,3,4,6  l1 r3  l2 r2  l3 r1  -1,0,2,1,3,4,6    右少  -1,-2,-3,0,-4,-5,6    -1,1,2,0,-3,4,5  -1,-3,2,0,1,4,5   -1,-3,0,2,1,4,5
            while (leftIndex < rightIndex){
                int temp = 0;
                while (arr[leftIndex] < middleValue){
                    leftIndex++;
                }
                while (arr[rightIndex] > middleValue){
                    rightIndex--;
                }
                if (leftIndex == rightIndex){
                    break;
                }
                temp = arr[leftIndex];
                arr[leftIndex] = arr[rightIndex];
                arr[rightIndex] = temp;
                //每次中轴两侧比较，左右互补越过中轴，左先到，等右，右先到，等左
                if (arr[rightIndex] == middleValue){
                    leftIndex++;
                }
                if (arr[leftIndex] == middleValue){
                    rightIndex--;
                }
            }
            //每次出循环，必然leftIndex = rightIndex
            if (leftIndex == rightIndex){
                leftIndex++;
                rightIndex--;
            }
    
            if (leftIndex<right ){
                quickSort(arr,leftIndex,right);
            }
    
            if (rightIndex>left){
                quickSort(arr,left,rightIndex);
            }
        }

## 性能分析 ##

### 内存消耗 ###

O(1)

### 稳定性 ###

不稳定

### 执行效率 ###

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)

# 总结 #

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是 O(n)。正因为此，它也没有快排应用广泛。  
快速排序算法虽然最坏情况下的时间复杂度是 O(n2)，但是平均情况下时间复杂度都是 O(nlogn)。不仅如此，快速排序算法时间复杂度退化到 O(n2) 的概率非常小，我们可以通过合理地选择 pivot 来避免这种情况。

[18721752-c6cc0f90f07596a7.png]: /images/20210918/fc4aaa7f831c483aa8196ef2fed9d294.png