第二章—排序

1. 初级排序

1.1选择排序

• 算法思想
  找到数组中最小的元素，将其与数组第一个元素交换，再不断的在剩下的元素中进行重复，最后将数组排序。

• 复杂度考虑
  假设数组的元素为N个，从0~N - 1的任意一个元素i都需要进行一次交换和N - 1 - i 次比较，总共就是N次交换和 \(N^2-1\) ​次比较。因此时间复杂度为\(O(n^2)\)。

• 代码实现(C++)

  template <typename T>
  void SelectSort(vector<T> &a)
  {
      int n = a.size();
      for (int i = 0; i < n; i++)
      {
          int min = i;
          for (int j = i + 1; j < n; j++)	//寻找剩余元素中的最小元素
          {
              if (a[j] < a[min])
                  min = j;
          }
          swap(a[i], a[min]);
      }
      return;
  }
  

1.2 插入排序

• 算法思想
  将待排序的数组分为有序部分和无序部分，在开始时，认为第一个元素是有序的，在无序元素中将无序部分的元素插入有序部分的合理位置，当遍历完无序部分时，即完成排序。

• 复杂度考虑
  假设数组有N个元素，平均情况下，对于索引为1~N - 1中的任意元素 i 的要进行 \(\frac{i-1}{2}\) 次比较，因此时间复杂度为\(O(n^2)\)。

• 代码实现(C++)

  template <typename T>
  void InsertSort(vector<T> &a) 
  {
      int n = a.size();
      for (int i = 1; i < n; i++)
      {
          int temp = a[i];
          int j = i - 1;
          while (j >= 0 && a[j] > temp)
          {
              a[j + 1] = a[j];
              j--;
          }
          a[j + 1] = temp;
      }
      return;
  }
  

1.3 希尔排序

• 算法思想:
  希尔排序是一种基于插入排序的快速排序方法。取数组中任意间隔为gap，将待排序的元素分为以gap为长度的子数组，然后对各子数组进行直接插入排序，然后逐渐减小gap的值，不断重复分组和排序，最后当gap = 1时，排序完成。

• 复杂度考虑:
  希尔排序的时间复杂度与gap的选取有关，当gap=1时，退化为直接插入排序，复杂度为\(O(n^2)\)​​​，而取Hibbard增量(1,3,5,7...)时，在最坏情况下时间复杂度为\(O(n^{\frac{3}{2}})\)​​​。

• 稳定性

  对于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，因此，Shell排序是不稳定的。

• 代码实现(C++)

  template <typename T>
  void ShellSort(vector<T> &a)
  {
      int n = a.size();
      int h = n / 2;
      while (h >= 1)
      {
          for (int i = h; i < n; i++)
          {
              for (int j = i; j >= h && a[j] < a[j - h]; j -= h)
                  swap(a[j], a[j - h]);
          }
          h /= 2;
      }
      return;
  }
  

2 归并排序

• 算法思想

  将数组递归地分成两半分别排序，然后将其归并起来。

• 归并操作

  • 直接将两个不同的有序数组归并到第三个数组

    template <typename T>
    void merge(vector<T> &a, int low, int mid, int high)   //归并
    {
        int n = a.size();
        vector<T> aux(n);
        for (int i = low; i <= high; i++) //拷贝数组
            aux[i] = a[i];
    
        int i = low, j = mid + 1;
        for (int k = low; k <= high; k++)
        {
            if (i > mid)
                a[k] = aux[j++];
            else if (j > high)
                a[k] = aux[i++];
            else if (aux[i] < aux[j])
                a[k] = aux[i++];
            else
                a[k] = aux[j++];
        }
    }
    

    图示1:将数组A和数组B归并

    

    for循环内的四个条件判断分别是:

    1. 当A组遍历完毕后直接取B组全部元素
    2. 当B组遍历完毕后直接取A组全部元素
    3. A组当前元素小于B组当前元素时取A组元素
    4. B组当前元素小于A组当前元素时取B组元素

• 自顶向下的归并

  • 通过分治的思想，将整个大数组不断分为多个小数组，对小数组不断的进行归并。实现上采用递归的方式。

    template <typename T>
    void MergeSort(vector<T> &a,int low, int high)   //递归归并
    {
        if(low >= high)	return;
        int mid = low + (high - low)/2;
        MergeSort(a,0,mid);
        MergeSort(a,mid+1,high);
        merge(a,low,mid,high);
    }
    

    图示2:当N=16时归并排序中的子数组

    

• 自顶向上的归并

  • 先归并微型数组，然后再成对归并得到的子数组，不断往复，将整个数组归并在一起。

    template <typename T>
    void MergeSort(vector<T> &a)	//迭代归并
    {
    	int n = a.size();
        vector<T> aux(a);	//拷贝数组
        for(int sz = 1; sz < n; sz+=sz)		//sz为子数组大小
        {
            for(int i = 0; i < n-sz; i+= sz*2)		//i为子数组索引
            {
                merge(a,i,i+sz-1,min(i+2*sz-1,n-1));	//最后一次子数组的大小可能比sz小
    		}	
        }
    }
    

  • 数组下标	0	1	2	3	4	5	6	7
    原数组	3	44	38	5	47	15	10	21
    merge(a,0,0,1)	3	44	38	5	47	15	10	21
    merge(a,2,2,3)	3	44	5	38	47	15	10	21
    merge(a,4,4,5)	3	44	5	38	15	47	10	21
    merge(a,6,6,7)	3	44	5	38	15	47	10	21
    merge(a,0,1,3)	3	5	38	44	15	47	10	21
    merge(a,4,5,7)	3	5	38	44	10	15	21	47
    merge(a,0,3,7)	3	5	10	15	21	38	44	47

• 复杂度考虑

  • 假设数组的元素为N个，我们进行归并排序时不断的将二分，如图示2，可得到最终会形成具有N个结点的完全二叉树，此时完全二叉树的层数\(log_2N+1\)​​​。
    此时所需时间 \(T(N)=N*T(1)+N*log_2N=Nlog_2N\)​​​ ，故时间复杂度为\(O(nlogn)\)​​​。
  • 在归并排序中，我们需要构建一个辅助数组，因此空间复杂度为\(O(n)\)​​​。

• 算法优化

  • 对小规模数组使用插入排序

    • 在递归过程中，由于小数组过多导致递归调用频繁，在小数组上插入排序大部分情况下由于归并排序

  • 测试数组是否有序

    • 根据归并排序的特点，每次归并的两个小数组都是有序的，可以添加一个判断条件(a[mid] <= a[mid+1])。我们可以认为数组是有序的并跳过merge方法，这样改动并不影响排序的递归调用。

  • 不将元素复制到辅助数组

    • 节省将数组元素复制到辅助数组的时间(无法减少空间)，我们可以将数据从输入数组排序到辅助数组或者将数据从辅助数组排序到输入数组

  • 代码实现(C++)

    template <typename T>
    void MergeSort(vector<T> &a, int low, int high)	//改良版归并排序
    {
    	int mid = low + (high - low) / 2;
        if(high - low <= 3)		//小规模数组使用插入排序
        {
            for(int i = low; i <= high; i++)
            {
                for(int j = i; j > low && a[j] < a[j-1]; j--)
                    swap(a[j],a[j-1]);
            }
            return;
        }
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
        if(!a[mid] < a[mid+1])
            merge(a,low,mid,high);
    }
    

3 快速排序

• 算法思想:快速排序也是分治思想的排序算法，将数组分为三段，左段，分割元素，右段。左段的元素都不大于分割元素，右段的元素都不小于分割元素，然后对左段和有段独立排序。

• 复杂度考虑

  • 快速排序需要的递归栈空间为\(O(n)\)，若用栈来模拟递归，则需要的空间可以减少为\(O(logn)\)。

  • 在最坏情况下，数据段左段总为空，此时用时为\(O(n^2)\)​。在最好情况下，左段和右端的元素数目总是大致相同，此时用时\(O(nlogn)\)。平均复杂度为\(O(nlogn)\)。

• 代码实现(C++)

  template <typename T>
  int Partition(vector<T> &a, int low, int high)	//切分
  {
      int i = low, j = high + 1;
      T temp = a[low];	//切分元素
      while (true)
      {
          //扫描左右
          while (a[++i] < temp)
              ;
          while (a[--j] > temp)
              ;
          if (i >= j)		//i，j相遇时终止循环
              break;
          swap(a[i], a[j]);
      }
      swap(a[low],a[j]);
      return j;
  }
  
  template <typename T>
  void QuickSort(vector<T> &a, int low, int high)	//快速排序
  {
      if (low >= high)
          return;
      int j = Partition(a, low, high);
      QuickSort(a, low, j - 1);	//左段排序
      QuickSort(a, j + 1, high);	//右段排序
  }
  

• 算法改进

  • 切换到插入排序
    • 对于小数组，快速排序比插入排序慢；由于采用递归，快速排序也会在小数组中调用自身。
  • 三取样切分
    • 使用子数组的一小部分元素的中位数来切分数组。
  • 熵最优的排序
    • 实际情况下，经常会出现有大量重复元素的数组，而原本的算法仍会对重复的元素进行切分，在这里可以进行改进。可以将数组切分为三个部分，分布对应小于，等于，大于切分元素的数组元素。

• 代码实现(C++)

  template <typename T>
  void QuickSort_inThreeWays(vector<T> &a, int low, int high)		//三路切分的快速排序
  {
      if (low >= high)
          return;
      int lt = low, i = low, gt = high;
      T pivot = a[low];
      while (i <= gt)
      {
          //索引元素与分割元素进行比较，来判断索引所处的部分
          int temp = (a[i] > pivot) ? 1 : ((a[i] == pivot) ? 0 : -1);
          if (temp < 0)
              swap(a[lt++], a[i++]);
          else if (temp > 0)
              swap(a[gt--], a[i]);
          else
              i++;
      }
      QuickSort_inThreeWays(a, low, lt - 1);
      QuickSort_inThreeWays(a, gt + 1, high);
  }
  

4 优先队列

• 我们经常需要处理有序的元素，但又不一定要求他们全都有序，或者要一次性的就将它们排序。很多时候我们只需要处理一些元素中键值最大或者键值最小的元素。
  这种时候合适的数据结构应该支持插入和删除最大(最小)元素。
  这种类型的数据类型叫优先队列。接下来主要使用以堆实现的优先队列。

• 堆的定义

  • 二叉堆能很好的实现优先队列的基本操作，在二叉堆中每一个元素都要大于等于另外两个特定位置的元素，相应的，这些位置的元素又至少要大于等于数组中的另外两个元素。
    将所有元素画成一颗二叉树，就能很容易看出这种结构。
    当二叉树的每一个结点都大于等于它的两个子结点时，又称堆有序。

  • 我们可以用数组来实现二叉堆，则位置k的结点的父结点的位置为\(\lfloor k/2 \rfloor\)，而它的两个子结点的位置分别为\(2k\)和\(2k+1\)。

  • 图示3 一颗堆有序的完全二叉树

    

• 堆的算法

  • 在堆的有序化中，我们会遇到某个结点的优先级上升和某个结点优先级下降两种情况。这个时候我们需要采用自下而上恢复堆的有序化和自上而下恢复堆的有序化。

  • 上浮(自下而上的堆有序化)

    • 代码实现(C++)

      template <typename T>
      void swim(vector<T> &a, int k)	//上浮
      {
          while( k > 1 && a[k/2] < a[k])	//不断寻找父结点
          {
              swap(a[k/2],a[k]);
              k /= 2;
          }
      }
      

  • 下沉(自上而下的堆有序化)

    • 代码实现(C++)

      template <typename T>
      void sink(vector<T> &a, int k)	//下沉
          {
              int n = a.size();
              while (2 * k <= n)
              {
                  int j = 2 * k;
                  if (j < n && a[j] < a[j + 1])	j++;
                  if (a[k] > a[j])	break;
                  swap(a[k], a[j]);
                  k = j;
              }
          }
      

  • 优先队列的代码实现(C++)

    template <typename T>
    class Proiority_Queue
    {
    private:
        vector<T> pq;
        int N = 0;
    
    public:
        Proiority_Queue(int n)
        {
            pq.assign(n + 1, NULL);	//开辟数组空间
        }
        bool isEmpty() { return N == 0; }
        int Size() { return N; }
    
        void insert(T value)
        {
            pq[++N] = value;	//在子结点插入新结点
            swim(N);	//寻找
        }
    
        T delMax()	
        {
            T max = pq[1];
            swap(pq[1], pq[N--]);
            pq[N + 1].~T();
            sink(1);
            return max;
        }
    
        void swim(int k)	//上浮
        {
            while (k > 1 && pq[k / 2] < pq[k])
            {
                swap(pq[k / 2], pq[k]);
                k /= 2;
            }
        }
    
        void sink(int k)	//下沉
        {
            int n = pq.size();
            while (2 * k <= n)
            {
                int j = 2 * k;
                if (j < n && pq[j] < pq[j + 1])
                    j++;
                if (pq[k] >= pq[j])
                    break;
                swap(pq[k], pq[j]);
                k = j;
            }
        }
    };
    

  • 复杂度考虑

    • 堆的插入
      以最大堆为例，进行插入操作的策略是从一个叶子结点到根节点的一趟起泡过程，需要的操作时间是\(O(height) = O(logn)\)​
    • 堆的删除
      以最大堆为例，进行删除操作就是删除根节点的元素，需要遍历从根节点到叶子结点的一条路径，要的操作时间是\(O(height) = O(logn)\)

• 堆排序

  • 堆的构造

    • 对于N个给定的元素，我们理所当然的会从左到右遍历数组，然后用swim()保证插入的元素已经是一颗堆有序的的完全二叉树。这样已经能在\(nlogn\)成正比的时间完成堆的构造了。

      但我们有一种更为高效的方法，可以从右往左用sink()函数构造子堆，这样在开始时我们只需要扫描数组一半的元素(我们可以跳过大小为1的子堆)，最后在位置1上调用sink()方法，扫描结束。

  • 代码实现C(++)

    template <typename T>
    void HeapSort(vector<T> &a)
    {
        int n = a.size();
        for (int i = n / 2; i >= 1; i--)
        {
            sink(a, i);
            while (n > 1)
            {
                swap(a[1], a[n--]);
                sink(a, 1);
            }
        }
    }
    

  • 复杂度考虑

    • 在堆排序的函数中，如果堆的大小为N，那么for循环的每次迭代需要\(O(logn)\)级别的时间，迭代次数为\(N/2\)，因此堆排序的时间复杂度为\(O(nlogn)\)。
      但实际上我们进行更加严密的分析，while循环的每一次迭代时间为\(O(height_i)\)，\(height_i\)是位置\(i\)为根结点的子树的高度。而完全二叉树的高度为\(h=\lceil log_2{N+1} \rceil\)。在树的第j层，最多有\(2^{j-1}\)个结点，因此最多有\(2^{j-1}\)个结点具有相同的高度\(h_j=h-j+1\)​。于是最大堆的初始化时间为：
      \[O(\sum_{j=1}^{h-1}2^{j-1} (h-j+1)) = O(\sum_{k=2}^{h}k 2^{h-k}) = O(2^h \sum_{k=2}^{h}k 2^{-k}) = O(2^h) =O(n) \]
      对\(O(2^h \sum_{k=2}^{h}k 2^{-k}) =O(2^h)\)的证明：
      \[令\sum_{k=2}^{h}k 2^{-k} = S_n \\ S_n = 2/2^2+3/2^3+\cdots+h2^h\\ 2S_n = 2/2+3/2^2+4/2^3+\cdots+h/2^{h-1}\\ 2S_n-S_n =S_n=1+1/2^2+1/2^3+\cdots+1/2^{h-1}-h/2^h\\ 故2^h*Sn\sim2^h \]
      故堆排序的真正的时间复杂度为\(O(n)\)

5 其他排序算法

• 冒泡排序

  • 算法思想

    • 简单的排序算法，重复走过待排序的数组，一次比较两个元素，如果顺序错误就交换他们，重复进行这个过程直到不需要交换。

  • 代码描述(C++)

    template <typename T>
    void BubbleSort(vector<T> &a)
    {
    	int temp = 0;
        for(int i = a.size()-1; i > 0; i--)
        {
    		for(int j = 0; j < i; j++)
            {
    			if(a[j] > a[j+1])
                    swap(a[j],a[j+1]);
            }
        }
    }
    

• 计数排序

  • 算法思想

    • 找出待排序的数组中最大和最小的元素，统计数组中每个值为i的元素出现的次数，存入数组C的第i项。对所有的计数累加，将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

  • 代码描述(C++)

    void CountingSort(vector<int> nums)
    {
        int minn = INT_MAX, maxn = INT_MIN;
        for(int num : nums)		//寻找最大最小值
        {   
            minn = min(minn,num);	
            maxn = max(maxn,num);
        }
        vector<int> cnt(maxn - minn + 1);	//建立新数组
        for(int num : nums)		//统计每个元素出现次数
        {
            cnt[num-minn]++;
        }
        int cur = 0;
        for(int i = 0; i < cnt.size(); i++)		//根据出现次数把cnt数组放回旧数组
        {
            while(cnt[i]>0)
            {
                nums[cur++] = i + minn;
                cnt[i]--;
            }
        }
    }
    

• 桶排序

  • 算法思想
    • 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
      1. 在额外空间充足的情况下，尽量增大桶的数量
      2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

• 基数排序

  • 算法思想
    • 原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

6 排序算法的选择

• 排序算法的性能特点

  算法	是否稳定	时间复杂度	空间复杂度
  冒泡排序	稳定	\(O(n^2)\)	\(O(1)\)
  选择排序	否	\(O(n^2)\)	\(O(1)\)
  插入排序	是	\(O(n^2)\)	\(O(1)\)
  希尔排序	否	\(O(nlogn)\)	\(O(1)\)
  快速排序	否	\(O(nlogn)\)	\(O(nlogn)\)
  归并排序	是	\(O(nlogn)\)	\(O(n)\)
  堆排序	否	\(O(nlogn)\)	\(O(1)\)
  计数排序	是	\(O(n+k)\)	\(O(n+k)\)
  桶排序	是	\(O(n+k)\)	\(O(n+k)\)
  基数排序	是	\(O(n*k)\)	\(O(n+k)\)