【数据结构与算法】快排、归并 O(nlogn) 基于比较

墨蓝 2022-11-25 10:05 113阅读 0赞

冒泡、插入、选择 O(n^2) 基于比较  
**快排、归并 O(nlogn) 基于比较**  
计数、基数、桶 O(n) 不基于比较

## 一、分治思想 ##

#### 1.分治思想：分治，顾明思意，就是分而治之，将一个大问题分解成小的子问题来解决，小的子问题解决了，大问题也就解决了。 ####

#### 2.分治与递归的区别：分治算法一般都用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。 ####

## 二、归并排序 ##

### 1.算法原理 ###

先把数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两部分合并到一起，这样整个数组就有序了。这就是归并排序的核心思想。如何用递归实现归并排序呢？写递归代码的技巧就是分写得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。递推公式怎么写？如下  
递推公式：merge\_sort(p…r) = merge(merge\_sort(p…q), merge\_sort(q+1…r))  
终止条件：p >= r 不用再继续分解  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

### 2.代码实现 ###

public class MergeSort { 
    
      // 归并排序算法, a是数组，n表示数组大小
      public static void mergeSort(int[] a, int n) { 
        mergeSortInternally(a, 0, n-1);
      }
    
      // 递归调用函数
      private static void mergeSortInternally(int[] a, int p, int r) { 
        // 递归终止条件
        if (p >= r) return;
    
        // 取p到r之间的中间位置q,防止（p+r）的和超过int类型最大值
        int q = p + (r - p)/2;
        // 分治递归
        mergeSortInternally(a, p, q);
        mergeSortInternally(a, q+1, r);
    
        // 将A[p...q]和A[q+1...r]合并为A[p...r]
        merge(a, p, q, r);
      }
    
      private static void merge(int[] a, int p, int q, int r) { 
        int i = p;
        int j = q+1;
        int k = 0; // 初始化变量i, j, k
        int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
        while (i<=q && j<=r) { 
          if (a[i] <= a[j]) { 
            tmp[k++] = a[i++]; // i++等于i:=i+1
          } else { 
            tmp[k++] = a[j++];
          }
        }
    
        // 判断哪个子数组中有剩余的数据
        int start = i;
        int end = q;
        if (j <= r) { 
          start = j;
          end = r;
        }
    
        // 将剩余的数据拷贝到临时数组tmp
        while (start <= end) { 
          tmp[k++] = a[start++];
        }
    
        // 将tmp中的数组拷贝回a[p...r]
        for (i = 0; i <= r-p; ++i) { 
          a[p+i] = tmp[i];
        }
      }
    
      /** * 合并(哨兵) * * @param arr * @param p * @param q * @param r */
      private static void mergeBySentry(int[] arr, int p, int q, int r) { 
        int[] leftArr = new int[q - p + 2];
        int[] rightArr = new int[r - q + 1];
    
        for (int i = 0; i <= q - p; i++) { 
          leftArr[i] = arr[p + i];
        }
        // 第一个数组添加哨兵（最大值）
        leftArr[q - p + 1] = Integer.MAX_VALUE;
    
        for (int i = 0; i < r - q; i++) { 
          rightArr[i] = arr[q + 1 + i];
        }
        // 第二个数组添加哨兵（最大值）
        rightArr[r-q] = Integer.MAX_VALUE;
    
        int i = 0;
        int j = 0;
        int k = p;
        while (k <= r) { 
          // 当左边数组到达哨兵值时，i不再增加，直到右边数组读取完剩余值，同理右边数组也一样
          if (leftArr[i] <= rightArr[j]) { 
            arr[k++] = leftArr[i++];
          } else { 
            arr[k++] = rightArr[j++];
          }
        }
      }
    }

### 3.性能分析 ###

#### 1）算法稳定性： ####

归并排序稳不稳定关键要看merge()函数，也就是两个子数组合并成一个有序数组的那部分代码。在合并的过程中，如果 A\[p…q\] 和 A\[q+1…r\] 之间有值相同的元素，那我们就可以像伪代码中那样，先把 A\[p…q\] 中的元素放入tmp数组，这样 就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一种稳定排序算法。

#### 2）时间复杂度：分析归并排序的时间复杂度就是分析递归代码的时间复杂度 ####

如何分析递归代码的时间复杂度？  
递归的适用场景是一个问题a可以分解为多个子问题b、c，那求解问题a就可以分解为求解问题b、c。问题b、c解决之后，我们再把b、c的结果合并成a的结果。若定义求解问题a的时间是T(a)，则求解问题b、c的时间分别是T(b)和T©，那就可以得到这样的递推公式：T(a) = T(b) + T© + K，其中K等于将两个子问题b、c的结果合并成问题a的结果所消耗的时间。这里有一个重要的结论：不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。套用这个公式，那么归并排序的时间复杂度就可以表示为：

T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
    T(n) = 2*T(n/2) + n； n>1，其中n就是merge()函数合并两个子数组的的时间复杂度O(n)。
    
    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) = 2kT(n/2k)+kn。当 T(n/2k)=T(1) 时，也就是 n/2k=1，我们得到 k=log2n 。我们将 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。  
3）空间复杂度：归并排序算法不是原地排序算法，空间复杂度是O(n)  
为什么？因为归并排序的合并函数，在合并两个数组为一个有序数组时，需要借助额外的存储空间。为什么空间复杂度是O(n)而不是O(nlogn)呢？如果我们按照分析递归的时间复杂度的方法，通过递推公式来求解，那整个归并过程需要的空间复杂度就是O(nlogn)，但这种分析思路是有问题的！因为，在实际上，递归代码的空间复杂度并不是像时间复杂度那样累加，而是这样的过程，即在每次合并过程中都需要申请额外的内存空间，但是合并完成后，临时开辟的内存空间就被释放掉了，在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时空间再大也不会超过n个数据的大小，所以空间复杂度是O(n)。

## 三、快速排序 ##

### 1.算法原理 ###

快排的思想是这样的：如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。然后遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将povit放到中间。经过这一步之后，数组p到r之间的数据就分成了3部分，前面p到q-1之间都是小于povit的，中间是povit，后面的q+1到r之间是大于povit的。根据分治、递归的处理思想，我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。  
递推公式：quick\_sort(p…r) = quick\_sort(p…q-1) + quick\_sort(q+1, r)  
终止条件：p >= r  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

### 2.代码实现 ###

/** * 快速排序 * * @param arr */
        public static void quickSort(int[] arr, int left, int right) { 
            if (left >= right) { 
                return;
            }
            int q = partition2(arr, left, right);
            quickSort(arr, left, q - 1);
            quickSort(arr, q + 1, right);
        }
    
        private static int partition(int[] arr, int left, int right) { 
            int pivot = arr[right];
            int i = left;
            for (int j = left; j < right; j++) { 
                if (arr[j] < pivot) { 
                    if (i == j) { 
                        ++i;
                    } else { 
                        int tmp = arr[i];
                        arr[i++] = arr[j];
                        arr[j] = tmp;
                    }
                }
            }
            int tmp = arr[i];
            arr[i] = arr[right];
            arr[right] = tmp;
            return i;
        }
    
        private static int partition2(int[] arr, int left, int right) { 
            // 三数取中法 , 随机数在这里写
            int middle = (left + right) / 2;
            int pivot = arr[middle];
            // 交换到最右边
            int val = arr[right];
            arr[right] = pivot;
            arr[middle] = val;
            int i = left;
            for (int j = left; j < right; j++) { 
                if (arr[j] < pivot) { 
                    if (i == j) { 
                        ++i;
                    } else { 
                        int tmp = arr[i];
                        arr[i++] = arr[j];
                        arr[j] = tmp;
                    }
                }
            }
            int tmp = arr[i];
            arr[i] = arr[right];
            arr[right] = tmp;
            return i;
        }
    
        /** * 三向切分快速排序 * * @param arr * @param left * @param right * @return */
        private static void quickSort3(int[] arr, int left, int right) { 
            if (left >= right) { 
                return;
            }
            int l = left;
            int k = left + 1;
            int r = right;
            int pivot = arr[l];
    
            while (k <= r) { 
                if (arr[k] < pivot) { 
                    int tmp = arr[l];
                    arr[l] = arr[k];
                    arr[k] = tmp;
                    l++;
                    k++;
                } else if (arr[k] == pivot) { 
                    k++;
                } else { 
                    if (arr[r] > pivot) { 
                        r--;
                    } else if (arr[r] == pivot) { 
                        int tmp = arr[k];
                        arr[k] = arr[r];
                        arr[r] = tmp;
                        k++;
                        r--;
                    } else { 
                        int tmp = arr[l];
                        arr[l] = arr[r];
                        arr[r] = arr[k];
                        arr[k] = tmp;
                        l++;
                        k++;
                        r--;
                    }
                }
            }
    
            quickSort(arr, left, l - 1);
            quickSort(arr, r + 1, right);
        }
    
        /** * 双轴快速排序 * * @param arr * @param left * @param right */
        private static void quickSort4(int[] arr, int left, int right) { 
            if (left >= right) { 
                return;
            }
            int l = left;
            int k = left + 1;
            int r = right;
            // 判断pivot1 与 pivot2 大小
            if (arr[l] > arr[r]) { 
                int tmp = arr[l];
                arr[l] = arr[r];
                arr[r] = tmp;
            }
            int pivot1 = arr[l];
            int pivot2 = arr[r];
    
            while (k < r) { 
                if (arr[k] < pivot1) { 
                    l++;
                    if (l != k) { 
                        int tmp = arr[l];
                        arr[l] = arr[k];
                        arr[k] = tmp;
                    }
                    k++;
                } else if (arr[k] >= pivot1 && arr[k] <= pivot2) { 
                    k++;
                } else { 
                    --r;
                    if (arr[r] > pivot2) { 
                    } else if (arr[r] >= pivot1 && arr[r] <= pivot2) { 
                        int tmp = arr[k];
                        arr[k] = arr[r];
                        arr[r] = tmp;
                        k++;
                    } else { 
                        l++;
                        int tmp = arr[l];
                        arr[l] = arr[r];
                        arr[r] = arr[k];
                        arr[k] = tmp;
                        k++;
                    }
                }
            }
    
            // 交换pivot1 和 pivot2
            arr[left] = arr[l];
            arr[l] = pivot1;
            arr[right] = arr[r];
            arr[r] = pivot2;
    
            quickSort(arr, left, l - 1);
            quickSort(arr, l + 1, r - 1);
            quickSort(arr, r + 1, right);
        }

### 3.性能分析 ###

#### 1）算法稳定性： ####

因为分区过程中涉及交换操作，如果数组中有两个8，其中一个是pivot，经过分区处理后，后面的8就有可能放到了另一个8的前面，先后顺序就颠倒了，所以快速排序是不稳定的排序算法。比如数组\[1,2,3,9,8,11,8\]，取后面的8作为pivot，那么分区后就会将后面的8与9进行交换。

##### 2）时间复杂度：最好、最坏、平均情况 #####

快排也是用递归实现的，所以时间复杂度也可以用递推公式表示。  
如果每次分区操作都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并的相同。  
T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。  
T(n) = 2\*T(n/2) + n； n>1  
所以，快排的时间复杂度也是O(nlogn)。  
如果数组中的元素原来已经有序了，比如1，3，5，6，8，若每次选择最后一个元素作为pivot，那每次分区得到的两个区间都是不均等的，需要进行大约n次的分区，才能完成整个快排过程，而每次分区我们平均要扫描大约n/2个元素，这种情况下，快排的时间复杂度就是O(n^2)。  
前面两种情况，一个是分区及其均衡，一个是分区极不均衡，它们分别对应了快排的最好情况时间复杂度和最坏情况时间复杂度。那快排的平均时间复杂度是多少呢？T(n)大部分情况下是O(nlogn)，只有在极端情况下才是退化到O(n^2)，而且我们也有很多方法将这个概率降低。

##### 3）空间复杂度：快排是一种原地排序算法，空间复杂度是O(1) #####

## 四、归并排序与快速排序的区别 ##

归并和快排用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢？

#### 1.归并排序，是先递归调用，再进行合并，合并的时候进行数据的交换。所以它是自下而上的排序方式。何为自下而上？就是先解决子问题，再解决父问题。 ####

#### 2.快速排序，是先分区，在递归调用，分区的时候进行数据的交换。所以它是自上而下的排序方式。何为自上而下？就是先解决父问题，再解决子问题。 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]

[笔记整理来源： 王争 数据结构与算法之美][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20221124/d471590cf9e0486993e179d300d4b26e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20221124/8bbadfbc2fe34bcabc620144d5044555.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20221124/9cf45cf500fd4dc1af31c8e5650c8215.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20221124/e32b64a798c64653800925e11967bd2f.png
[Link 1]: https://s1.ax1x.com/2020/08/03/aUh2TS.png