算法设计策略-分治法

排序问题

问题描述

排序是将一个元素序列调整为按指定关键字值的递增（或递减）次序排列的有序序列。

分治法求解

分治法求解排序问题思想：按某种方式将序列分成两个或多个子序列，分别进行排序，再将已排序的子序列合并成一个有序序列。

合并排序和快速排序是两种典型的符合分治策略的排序算法。

合并排序

合并排序（merge sort）的基本运算就是将两个或多个有序序列合并成一个有序序列。

两路合并排序算法

//merge 函数
template<class T>
  void SortableList<T>::Merge(int left, int mid, int right)
  {
    T* temp = new T[right-left+1];
    int i = left, j = mid+1, k = 0;
    while((i<=mid)&&(j<=right)){
      if(l[i]<=l[j]){
        temp[k++]=l[i++];
      } else{
        temp[k++]=l[j++];
      }
    }
    while(i<=mid){
      temp[k++]=l[i++];
    }
    while(j<=right){
      temp[k++]=l[j++];
    }
    for(i = 0, k = left; k<=right;){
      l[k++]=temp[i++];
    }
  }

函数Merge将两个长度之和为n的有序序列合并成一个有序序列，在执行过程中，最多进行n-1次关键字值之间的比较，时间复杂度为 $O (n)$ 。

分治法求解

使用分治法的两路合并算法可以描述为：将待排序的元素序列一分为二，得到两个长度基本相等的子序列，然后对两个子序列分别排序，如果子序列较长，还可以继续细分，直到子序列的长度不超过1为止；当分解所得的子序列已排列有序时，将两个有序子序列合并成一个有序子序列，实现将子问题的解组合成原问题的解。

//两路合并排序
template<class T>
  void SortableList<T>::MergeSort()
  {
    MergeSort(0,n-1);
  }
template<class T>
  void SortableList<T>::MergeSort(int left, int right)
  {
    //若序列的长度超过1，则划分为两个序列
    if(left<right){
      //将待排序的序列一分为二
      int mid = (left+right)/2;
      //对左子列排序
      MergeSort(left, mid);
      //对右子列排序
      MergeSort(mid+1, right);
      //将两个有序子序列合并成一个有序序列
      Merge(left, mid, right);
    }
  }

合并排序递归算法的时间复杂度为 $O (n \log n)$ ，空间复杂度为 $O (n)$ 。

C语言实验

#include <stdio.h>
#include <stdlib.h>
//Merge函数
void Merge(int l[], int left, int mid, int right)
{
  int *temp = (int *)malloc(sizeof(int)*(right-left+1));
  int i = left, j = mid+1, k = 0;
  while((i<=mid)&&(j<=right)){
      if(l[i]<=l[j])
        temp[k++] = l[i++];
      else
        temp[k++] = l[j++];
    }
  while(i<=mid){
      temp[k++] = l[i++];
    }
  while(j<=right){
      temp[k++] = l[j++];
    }
  for(i = 0, k = left; k<=right;){
      l[k++] = temp[i++];
    }
}

//合并归并排序
void MergeSort(int l[], int left, int right)
{
  //如果序列的长度超过1
  if(left<right){
      int mid = (left+right)/2;
      MergeSort(l, left, mid);
      MergeSort(l, mid+1, right);
      Merge(l, left, mid, right);
    }
}
int main()
{
  int l[5] = {1,3,2,4,3};
  MergeSort(l, 0, 4);
  for(int i = 0; i<5; i++)
    printf("l[%d] = %d
", i, l[i]);
  return 0;
}

实验结果

l[0] = 1
l[1] = 2
l[2] = 3
l[3] = 3
l[4] = 4

快速排序

快速排序（quick sort）又称为分划交换排序。

快速排序采用一种特殊的分划操作堆排序问题进行分解，其分解方法是：在待排序的序列 $(K_{0}, K_{1}, \dots, K_{n - 1})$ 中选择一个元素作为分划元素，也称主元（pivot）。经过一趟的划分处理将原序列中的元素重新排列，使得以主元为轴心，将序列分成左右两个子序列。主元左侧子序列中所有元素都不大于主元，主元右侧子序列所有元素都不小于主元。通常将这一趟过程，称为一趟分划（partition）。

通过分划操作，原序列的排序问题被分解成了两个性质相同、相互独立的子问题，分别对两个子序列进行排序。当子序列为空序列或只有一个元素的序列时，无须进行任何处理，它们自然是有序的。

分划操作

分划操作是快速排序的核心操作。最简单的做法是选择每个序列的第一个元素为主元。

//分划函数
template<class T>
  int SortableList<T>::Partition(int left, int right)
  {
    //前置条件：left<=right；主元为第一个元素l[left] 。
    int i = left, j = right+1;
    do{
      do{
        i++;
      }while(l[i]<l[left]);// 从l[left+1]开始比较
                        //i右移，直到遇到一个不小于主元的元素停止
      do{
        j--;
      }while(l[j]>l[left]);//  从l[right]开始比较
                            // j左移，直到遇到一个不大于主元的元素停止
      if(i<j)
        //交换两个元素l[i]和l[j]
        Swap(i,j);      
    }while(i<j);//只要i仍小于j
    Swap(left,j);//最后将主元l[left]与l[j] 交换，结束一趟分划操作
    return j;//返回当前主元的位置
  }//

算法要求在待排序序列的尾部设置一个大值 $\infty$ 作为哨兵，是为了防止指针i在右移过程中移出序列。

快速排序算法

//快速排序算法
template<class T>
  int SortableList<T>::QuickSort(int left, int right)
  {
    //当序列长度大于1时，进行分割
    if(left<right){
      //对[left,right]范围内的序列进行分划
      int j =Partition(left, right);
      //对左子序列实施快速排序
      QuickSort(left, j-1);
      //对右子序列实施快速排序
      QuickSort(j+1, right);
    }
  }

C语言实验

#include <stdio.h>
//分划函数Partition
int Partition(int l[], int left, int right)
{
    int i=left, j=right+1, tmp=0;
    do{
        do{
            i++;
        }while(l[i]<l[left] && i<=right);
        do{
            j--;
        }while(l[j]>l[left] && j>=left);
    if(i<j){
        tmp = l[i];
        l[i]=l[j];
        l[j]=tmp;
    }
    }while(i<j);
    tmp = l[left];
    l[left]=l[j];
    l[j]=tmp;
    for(int i = 0; i<=8; i++)
        printf("%d ", l[i]);
    printf("
");
    return j;
}

//快速排序QuickSort
void QuickSort(int l[], int left, int right)
{
    if(left<right){
        int j = Partition(l, left, right);
        QuickSort(l, left, j-1);
        QuickSort(l, j+1, right);
    }
}

int main()
{
    int l[9] = {72,26,57,88,42,80,72,48,60};
    QuickSort(l, 0, 8);
    for(int i = 0; i<=8; i++)
        printf("l[%d] = %d
", i, l[i]);
    return 0;
}

实验结果：

72 26 57 60 42 48 72 80 88
48 26 57 60 42 72 72 80 88
42 26 48 60 57 72 72 80 88
26 42 48 60 57 72 72 80 88
26 42 48 57 60 72 72 80 88
26 42 48 57 60 72 72 80 88
l[0] = 26
l[1] = 42
l[2] = 48
l[3] = 57
l[4] = 60
l[5] = 72
l[6] = 72
l[7] = 80
l[8] = 88

Press any key to continue.

如果每次划分操作后，左右两个子序列的长度基本相等，则快速排序的效率最高，其最好的时间复杂度为 $O (n \log n)$ ；反之，如果每次划分所产生的两个子序列其中由一个为空，则快速排序效率最低，其最坏情况时间复杂度为 $O (n^{2})$ ，辅助空间： $O (n)$ 或 $O (\log n)$ 。

快速排序的平均情况时间复杂度为 $O (n \log n) $ 。

快速排序算法的改进

改进主元的选择方法。可以采用如下三种方式：
- 取 $K_{(l e f t + r i g h t) / 2}$ 作为主元
- 取left~right间的随机整数j，以 $K_{j}$ 作为主元
- 取 $K_{l e f t}$ 、 $K_{(l e f t + r i g h t) / 2}$ 和 $K_{r i g h t}$ 三者的中间值为主元
在快速排序中，子序列会变得越来越小。当子序列长度小到一定值（如小于10）时，可以不继续划分，而使用直接插入法进行排序。
递归算法的效率常常不如相应的迭代算法。为了提高快速排序速度，可以设计非递归的快速排序算法。

合并排序和快速排序的比较

合并排序的问题分解过程十分简单，只需将序列一分为二；而快速排序的问题分解方法相对较困难，需要调用Partition函数将一个序列划分为子序列。

从子问题的解得到原问题的解的过程对于快速排序来说异常简单，一旦左右两个子序列都已分别排序，整个序列自然成为有序序列，几乎无须额外的工作；但对于合并排序，则需要调用Merge函数来实现。

排序算法的时间下界

排序算法	最好情况	平均情况	最坏情况
直接插入排序	$O (n)$	$O (n^{2})$	$O (n^{2})$
简单选择排序	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$
冒泡排序	$O (n)$	$O (n^{2})$	$O (n^{2})$
快速排序	$O (n \log n)$	$O (n \log n)$	$O (n^{2})$
两路合并排序	$O (n \log n)$	$O (n \log n)$	$O (n \log n)$
堆排序	$O (n \log n)$	$O (n \log n)$	$O (n \log n)$

定理：任何一个通过关键字值比较对n个元素进行排序的算法，在最坏的情况下，至少需要做 $(n / 4) \log n$ 次比较。