前言

这一章我们学习了排序这一基本算法。本笔记主要做了以下工作:

  • 总结了排序的各种问题
  • 总结并实现了8种排序算法:
    • 插入排序
    • 希尔排序
    • 冒泡排序
    • 快速排序
    • 选择排序
    • 堆排序
    • 归并排序
    • 基数排序
  • 这一章的笔记不同于前面两章。前面两章的笔记所含数据结构和算法的实现代码如无特殊标注,均是我自己实现并测试的。而本章的很多代码都是我从资料中引用的。这是因为某些算法实现起来很简单,或实现价值不大。当然,引用者我们也会标出。

关于排序的基本问题

在计算机科学与数学中,一个排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。

排序算法有以下基本问题:

  • 稳定性。如果一个排序算法是稳定的,当有两个相等键值的纪录$R$和$S$,且在原本的列表中$R$出现在$S$之前,在排序过的列表中$R$也将会是在$S$之前。
  • 内排序与外排序。是否需要使用外存储器
  • 空间复杂度。
  • 时间复杂度。

其实这里教师忽视了一个问题,那就是排序算法是否对现代计算机体系结构友好,或者说的露骨一点,是否会频繁地cache不命中、TLB不命中、页表不命中。当然,作为算法本身来说,这倒是无所谓。但是,既然说到了内排序与外排序这种实现上的问题,那这个问题也应该谈及。

插入排序

插入排序明明是最简单的排序之一,网上有些人却讲的令人云里雾里,不知所云。特别是所谓的“监视哨”,更是让这个简单的算法变得很复杂了。不客气地说,教师的讲述也是不清楚的。

这个算法的基本思想就是一个结构归纳:

如果一个长度为$n$的序列自$0$号至$m - 1$号元素都是有序的,那么只要将$m$号元素插入$0$号至$m - 1$号元素的正确位置,那么这个序列就是从$0$号至$m$号有序的。

有了这个思想,我们定义一个基本操作A(n),就是将一个从$0$到$n - 1$有序的序列变为一个从$0$到$n$有序的序列。那么,只要自$1$至$n - 1$使用这个操作,这个序列就被排好序了。

我们还要搞定最后一个问题,那就是如何将$m$号元素插入到“正确”位置呢?答案也很简单,那就是设置一个条件$P$,如果$P(list[i], list[m])$满足条件,那就结束,否则将$i$号元素后移,继续和$i - 1$号元素比较。这样有些抽象,为了真正说明白,还是需要代码:

/* 此段代码来自维基百科--插入排序词条 */
void insertion_sort(int arr[],int len){
    for(int i=1;i<len;i++){
        int key=arr[i];
        int j=i-1;
        while((j>=0) && (key<arr[j])){
          arr[j+1]=arr[j];
          j--;
        }
        arr[j+1]=key;
    }
}

显然,这段代码是升序排序的代码,它很简单。作为实现来说,不足之处是没有正确利用模板,只能实现对整数序列排序。

关于“监视哨”

一个比较麻烦的问题是所谓的“监视哨”,其实说它“比较麻烦”也是因为有些人讲的实在太混乱。

我们重点关注以下刚才探讨的代码的这一句话:

while((j>=0) && (key<arr[j])){

什么时候会触发$j >= 0$这一条件呢?那就是$j == -1$的时候,也就是说从$0$到$i - 1$都不满足条件,要把这个元素插在开头。

这样我们会发现,这做法是为了一次失败准备的,但我们却要在成功的时候(绝大部分)来作这次比较。

所以自然地,我们会想到要不要优化一下,想办法消除掉这次比较。

那有些人就想到,把0号位置放入一个一定会满足退出条件的元素不就好了!这就是所谓的“监视哨”(sentinel)

至于放什么、怎么放之类的无聊问题这里就不谈了。但是我们必须指出,现代CPU具有流水线、多发射、乱序执行的特性,这种优化是不是真的可以优化时效,我们是有疑问的。

算法分析

插入排序的

  • 最好时间复杂度为:$O(n)$
  • 最坏时间复杂度为:$O(n^2)$
  • 平均时间复杂度为:$O(n^2)$
  • 是否稳定:稳定
  • 辅助空间:$O(1)$

希尔排序

插入排序有两个比较快的情况:

  1. 序列基本有序
  2. 序列很短

希尔排序就是利用这两个情况来使插入排序变为一个比较快速的排序。

维基百科上对希尔排序的解释及其直观,我们这里来复读一下:

考虑一个序列[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],我们一开始把它分为5个列表: 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10

然后分别对这5列排序(这每一列的排序是插入排序): 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45

连接到一起得到[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ],然后再把它分为三个列表: 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45

然后再对这三个列表排序: 10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94

这时基本有序了,我们把它连接到一起,再进行直接插入排序就好了。

我们看到,这个排序过程有一个“分成n个列表”的动作,这个$n$的不同取值,叫做步长序列。

步长序列怎么取呢?这取法是很多的,算法的发明者采用的是$\frac{n}{2}, \frac{n}{4}, …, 1$这个序列。

我们来实现一下这个“分列 -> 排序”的过程:

void MyShellSort(std::vector<int>& vec) {
	for (int step = vec.size() / 2; step > 0; step /= 2) {
		for (int i = step; i < vec.size(); ++i) {
			int j = i - step;
			int temp = vec[i];

			while (j - step >= 0 && vec[j] > temp)
			{
				vec[j + step] = vec[j];
				j -= step;
			}
			vec[j + step] = temp;
		}
	}
}

如果对比一下这份代码和插入排序的代码,我们会发现插入排序就是希尔排序$step == 1$时的情况。

然后我们也会看到,如果step比较大,那么待排序元素数量不大,会进入第一个插入排序较快情况;如果step比较小,那么序列基本有序,进入第二个插入排序较快情况。可见希尔排序的速度应该是比较好的。

算法分析

希尔排序的

  • 最好时间复杂度为:$O(n)$
  • 最坏时间复杂度为:不知道
  • 平均时间复杂度为:不知道
  • 是否稳定:不稳定(这个比较复杂,其实也有稳定的实现)
  • 辅助空间:$O(1)$

冒泡排序

冒泡排序的基本思想是每一次都把未排序序列中最大/最小的元素交换到未排序序列的头部。

这个算法我们很熟悉,实现起来很简单:

void MyBubbleSort(std::vector<int>& vec){
  for(auto i = 0; i < vec.size();++i){
    for(auto j = i + 1; j < vec.size();++j){
      if(vec[i] < vec[j]){
        std::swap(vec[i], vec[j]);
      }
    }
  }
}

但是这样一来即使序列是有序的,我们仍然会是$O(n^2)$的时间复杂度,所以要优化一下:

void MyBobbleSort(std::vector<int>& vec) {
	bool hit = false;
	for (auto i = 0; i < vec.size(); ++i) {
		for (auto j = i + 1; j < vec.size(); ++j) {
			if (vec[i] > vec[j]) {
				std::swap(vec[i], vec[j]);
				hit = true;
			}
		}
		if (hit == false) {
			break;
		}
		hit = false;
	}
}

这样一来,如果序列有序,就是$O(n)$复杂度了。

算法分析

冒泡排序的

  • 最好时间复杂度为:$O(n)$
  • 最坏时间复杂度为:$O(n^2)$
  • 平均时间复杂度为:$O(n^2)$
  • 是否稳定:稳定
  • 辅助空间:$O(1)$

快速排序

这个算法据说是排序随机序列最快的算法。

这是一个很简单的算法 这是一个很简单的算法 这是一个很简单的算法

这个算法一共有三步:

  1. 找到一个位置\(i\)。
  2. 分割序列,使得\(i\)位置左子序列中的元素都比\(i\)小,右子序列中的元素都比\(i\)大
  3. 递归处理左子序列和右子序列中的元素。
  4. 把它们合在一起。

就按照这个描述,我们用ruby实现一下:

class Array
  def qsort
    return if self.length <= 1 
    # 默认找到的为置为0
    left, right = self[1...-1].partition { |i| i <= self[0] }
    left.qsort
    right.qsort
    self = left + self[0] + right
  end
end

为了防止有人不懂ruby,我们再用C++实现一遍:

std::vector qsort(std::vector vec){
	if(vec.size() <= 1){
		return vec
	}
	auto this_ele = vector[0];
	std::vector left;
	std::vector right;
	for(auto i = 1; i < vec.size(); ++i){
		if(vec[i] <= this_ele){
			left.push_back(vec[i]);
		}
		else{
			right.push_back(vec[i]);
		}
	}
	left = qsort(left);
	right = qsort(right);
	std::vector ret(left);
	ret.push_back(this_ele);
	for(auto i in right){
		ret.push_back(i);
	}
	return ret;
}

这个实现就是对算法的直接实现,但是它的效率是很堪忧的,为什么呢?

我们这样写,实际上每次都要新开辟额外的空间,而且这空间还不小,大概是\(O(n)\)的数量级。

如果用c/c++去写,本事就是要追求性能的,自然不可以这样。

所以我们需要一种叫做“原位排序”的技术。而原位排序的关键是原位分割,也即是说在原数组上实现分割。

为了实现原位分割,人们想了各种奇奇怪怪的方法,这里展示两种

一种是比较难以理解的:

template <class TYPE_ITERATION>
TYPE_ITERATION partition(TYPE_ITERATION begin, TYPE_ITERATION end) {
	auto mid = *(end - 1);
	TYPE_ITERATION str = begin;
	for (auto i = begin; i < end - 1; ++i) {
		if (*i < mid) {
			iter_swap(i, str++);
		}
	}
	iter_swap(str, end - 1);
	return str;
}

一种是稍微好理解一点的:

T mid = arr[end];
int left = start, right = end - 1;
while (left < right) { //在整个范围内搜寻比枢纽小或大的元素,然后将左侧元素与右侧元素交换
  while (arr[left] < mid && left < right) //试图在左侧找到一个比枢纽更大的元素
    left++;
  while (arr[right] >= mid && left < right) //试图在右侧找到一个比枢纽更小的元素
    right--;
  std::swap(arr[left], arr[right]); //交换元素
}
if (arr[left] >= arr[end])
  std::swap(arr[left], arr[end]);
else
  left++; 
//arr[left]就是最后被选出的元素

不过,有了这个partition函数,下面的操作就很简单了:

template <class TYPE_ITERATION>
VALUE Mysort(TYPE_ITERATION begin, TYPE_ITERATION end) {
	if (begin + 1 >= end) {
		return;
	}
	TYPE_ITERATION mid = ::partition(begin, end);
	::Mysort(begin, mid);
	::Mysort(mid + 1, end);
}

算法分析

快速排序的

  • 最好时间复杂度为:\(O(nlog(n))\)
  • 最坏时间复杂度为:\(O(n^2)\)
    • 这里需要解释一下,如果每次选的元素都是最大的/最小的,那很不幸,分割就会变成 arr[0…n - 2]   arr[n - 1],这样一来就成了O(n^2)复杂度了。
  • 平均时间复杂度为:\(O(nlog(n))\)
  • 是否稳定:不稳定
  • 辅助空间:\(O(log(n))\)
    • 这里指的是递归用到的栈空间

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

实现如下:

/* 来自维基百科 */
template<typename T> 
void selection_sort(std::vector<T>& arr) {
	for (int i = 0; i < arr.size() - 1; i++) {
		int min = i;
		for (int j = i + 1; j < arr.size(); j++)
			if (arr[j] < arr[min])
				min = j;
		std::swap(arr[i], arr[min]);
	}
}

算法分析

选择排序的

  • 最好时间复杂度为:$O(n)$
  • 最坏时间复杂度为:$O(n^2)$
  • 平均时间复杂度为:$O(n^2)$
  • 是否稳定:不稳定
  • 辅助空间:$O(1)$

堆排序

堆我们在上一章已经学习过了,我们知道它可以在对数时间内完成取出最大值/最小值并调整的动作。

那么,如果我们从一个堆中取出$n$次,岂不就得到了一个排好序的序列?

这时的时间复杂度为$O(log(n))$,然后还需要把一开始的无序序列变为堆,也需要$O(log(n))$,总体来看,堆排序可以稳定地达到$O(log(n))$的复杂度。

由于上次已经用ruby实现过堆了,我们这次直接实现一个堆排序就极为简单:

module BinaryHeapable
  def heap_sort
    self.convert_to_heap
    arr = []
    while self.length != 0
      arr << self.remove_from_heap
    end
    self = arr
  end
end

但这样和快速排序一样,会耗费额外的空间。我们也最好要实现原位排序。

如何实现呢?我们这样去做: 每次排序时,顺序执行这三个步骤:

  1. 把堆顶元素和堆尾元素交换
  2. 堆的长度减一
  3. 调整,使得新的堆满足堆序。

c++实现如下:

/* 代码来自维基百科 */
#include <iostream>
#include <algorithm>
using namespace std;

void max_heapify(int arr[], int start, int end) {
    // 建立父節點指標和子節點指標
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { // 若子節點指標在範圍內才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小,選擇最大的
            son++;
        if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢,直接跳出函數
            return;
        else { // 否則交換父子內容再繼續子節點和孫節點比較
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
    // 初始化,i從最後一個父節點開始調整
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先將第一個元素和已经排好的元素前一位做交換,再從新調整(刚调整的元素之前的元素),直到排序完畢
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

算法分析

堆排序的

  • 最好时间复杂度为:$O(nlog(n))$
  • 最坏时间复杂度为:$O(nlog(n))$
  • 平均时间复杂度为:$O(nlog(n))$
  • 是否稳定:不稳定
  • 辅助空间:$O(1)$
  • 堆排序缓存不友好,容易造成缓存不命中,所以一般不使用

归并排序

归并排序是很经典的分治算法,一共分为三步:

  1. 分,分成两个子序列。
  2. 治,递归处理两个子序列。这一步完成后,两个子序列即为有序。
  3. 合,合并这两个子序列,使得它们有序。

c++实现如下:

void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

算法分析

归并排序的

  • 最好时间复杂度为:$O(nlog(n))$
  • 最坏时间复杂度为:$O(nlog(n))$
  • 平均时间复杂度为:$O(nlog(n))$
  • 是否稳定:稳定
  • 辅助空间:$O(n)$

基数排序

基数排序是很优雅的排序,它的基本过程是:

  1. 将所有数字补成相同长度,如果长度不够则补0
  2. 从最低位开始,在第$i$位进行以下过程
    1. 扫描整个序列,将第$i$位为$k$的数放到编号为$k$的桶中
    2. 按$0$到$9$的顺序把桶中的元素依次放回序列中
    3. 如果$i$大于$n$,结束

这样以后,整个序列就排好序了。可以看到,时间复杂度为$O(kn)$,其中$k$是最大位数。还要花费$O(n)$的额外空间。

实现如下:

/* 这段代码来自维基百科 */
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

算法分析

归并排序的

  • 最好时间复杂度为:$O(kn)$
  • 最坏时间复杂度为:$O(kn)$
  • 平均时间复杂度为:$O(kn)$
  • 是否稳定:稳定
  • 辅助空间:$O(n)$