算法分析（二） - 归并排序 & 快速排序

╰+哭是因爲堅強的太久メ 2023-06-18 15:54 46阅读 0赞

归并排序、快速排序都是基于**比较**的排序算法。本文将详细分析这两种排序。

先说结论

<table style="width:700px;"> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th>基于比较</th> 
   <th>原地排序</th> 
   <th>稳定性</th> 
   <th> <p>时间复杂度</p> <p>最好</p> </th> 
   <th> <p>时间复杂度</p> <p>最坏</p> </th> 
   <th> <p>时间复杂度</p> <p>平均</p> </th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>归并排序</td> 
   <td>✔</td> 
   <td>✘</td> 
   <td>✔</td> 
   <td>nlog(n)</td> 
   <td>nlog(n)</td> 
   <td>nlog(n)</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>✔</td> 
   <td>✔</td> 
   <td>✘</td> 
   <td>nlog(n)</td> 
   <td><img alt="n^{2}" src="https://private.codecogs.com/gif.latex?n%5E%7B2%7D"></td> 
   <td>nlog(n)</td> 
  </tr> 
 </tbody> 
</table>

## 1 归并排序 ##

归并排序先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一 起，这样整个数组就都有序了。

代码如下：

void Merge(vector<int>& num, int begin, int end)
    {
        int mid = begin + (end - begin) / 2;
        int i = begin, j = mid+1;
        vector<int> result;
        while (i <= mid && j <= end)
        {
            if (num[i] <= num[j])
            {
                result.push_back(num[i]);
                i++;
            }
            else
            {
                result.push_back(num[j]);
                j++;
            }
        }
    
        while (i <= mid)
        {
            result.push_back(num[i]);
            i++;
        }
    
        while (j <= end)
        {
            result.push_back(num[j]);
            j++;
        }
    
        for (int i = 0; i < result.size(); i++)
        {
            num[begin + i] = result[i];
        }
        result.clear();
    }
    
    void MergeSort(vector<int>& num, int begin, int end)
    {
        if (num.size()  == 0 ||begin >= end)
            return;
    
        int mid = begin + (end - begin) / 2;
        MergeSort(num, begin, mid);
        MergeSort(num, mid + 1, end);
        Merge(num, begin, end);
    }

### 1.1 归并排序不是原地排序算法。 ###

归并排序在合并两个有序数组为一个有序数组时，需要借助额外的存储空间O(n)。这是它致命的弱点，也是它没有快速排序应用广泛的原因。

### 1.2 归并排序是稳定的排序算法。 ###

归并排序稳不稳定关键要看merge()函数，也就是两个有序子数组合并成一个有序数组的那部分代码。有相同的元素时，始终把前一个子数组的元素放入结果数组中，就能保证元素的先后顺序。因此归并排序是一个稳定的排序算法。

### 1.3 归并排序的时间复杂度分析。 ###

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

## 2 快速排序 ##

如果要排序数组中下标从p到r之间的一组数据，选择p到r之间的任意一个数据作为pivot（分区点）。 遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1。此时所有的数据都有序了。

代码如下：

int AdjustArray(vector<int>& num, int left, int right) //返回调整后基准数的位置
    {
        int i = left, j = right;
        int pivot = num[left]; //s[l]即s[i]就是第一个坑
        while (i < j)
        {
            // 从右向左找小于x的数来填s[i]
            while (i < j && num[j] >= pivot)
                j--;
            if (i < j)
            {
                num[i] = num[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑
                i++;
            }
    
            // 从左向右找大于或等于x的数来填s[j]
            while (i < j && num[i] < pivot)
                i++;
            if (i < j)
            {
                num[j] = num[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑
                j--;
            }
        }
        //退出时，i等于j。将x填到这个坑中。
        num[i] = pivot;
        return i;
    }
    
    void QuickSort(vector<int>& num, int begin, int end)
    {
        if (begin < end)
        {
            int i = AdjustArray(num, begin, end);//先成挖坑填数法调整s[]
            QuickSort(num, begin, i - 1); // 递归调用 
            QuickSort(num, i + 1, end);
        }
    }

### 2.1 快速排序是原地排序算法。 ###

快速排序不需要额外的空间，所以它的空间复杂度为O(1)，是一个原地排序算法。

### 2.2 快速排序不是稳定的排序算法。 ###

有相同的元素时，排序过程中会发生交换。快速排序不是稳定的排序算法。

### 2.3 快速排序的时间复杂度分析。 ###

如果数组中的数据原来已经是有序的了，比如1，3，5，6，8。如果我们每次选择最后一个元素作为pivot，那每次分区得到的两个区间 都是不均等的。我们需要进行大约n次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约n/2个元素，这种情况下，快排的时间复杂度就 从O(nlogn)退化成了O(![n^\{2\}][n_2])。

在最好和平均情况下，快排的时间复杂度是O(nlogn)。

[n_2]: https://private.codecogs.com/gif.latex?n%5E%7B2%7D