经典排序算法小结

比较弱的排序算法

选择排序 (Selection Sort)

思想:扫描一次数组,我们就能得到最小值,把这个最小值取出,再扫描剩下的元素,就能得到第二小的值,以此类推。

设数组是A[0...n-1]

  • 扫描A[0...n-1],选出最小的,与A[0]交换,A[0]已经有序;
  • 扫描A[1...n-1],选出最小的,与A[1]交换,A[0...1]已经有序;
  • 扫描A[2...n-1],选出最小的,与A[2]交换,A[0...2]已经有序;
  • 扫描A[n-2...n-1],选出最小的,与A[n-2]交换,A[0...n-2]已经有序;
  • 整个数组已经有序

Notes: 一共扫描了n-1次,每一次扫描的范围都会减少一,总比较次数为n*(n-1)/2;最多做n-1次交换(选择排序的交换次数最少)。

  • 时间复杂度:$O(n^2)$
  • 为数不多的优点:原地排序
  • 实际场景下几乎不使用

参考代码(C++):

template<typename T>
void SelectionSort(vector<T>& A) {
    int n = A.size();
    // 扫描n-1次
    for (int i = 0; i < n - 1; ++i) {
        int pos_min = i;  // 最小值的位置
        for (int j = i; j < n; ++j) {
            if (A[j] < A[pos_min]) {
                pos_min = j;
            }
        }
        std::swap(A[i], A[pos_min]);
    }
}

冒泡排序 (Bubble Sort)

思想:我有强迫症,看到这里有一对数字不是有序的,我就交换它们!又发现了一对,再交换…终于没有不是有序的数对了~

设数组是A[0...n-1]

  • 考察A[0]A[1]A[1]A[2]A[n-2]A[n-1],如果不是有序就交换,这一轮考察结束后,最大的已经被交换(冒泡)到A[n-1]
  • 考察A[0]A[1]A[1]A[2]A[n-3]A[n-2],如果不是有序就交换,这一轮考察结束后,第2大的已经被交换(冒泡)到A[n-2]
  • 考察A[0]A[1],如果不是有序就交换,这一轮考察结束后,第n-1大的已经被交换(冒泡)到A[1]
  • 整个数组已经有序

Notes: 一共考察了n-1轮,每一轮考察的范围都会减少1,总比较次数为n*(n-1)/2;最多做n*(n-1)/2次交换(交换次数太多了)。

  • 时间复杂度:$O(n^2)$
  • 也属于排序的入门级算法

参考代码(C++):

template<typename T>
void BubbleSort(vector<T>& A) {
    int n = A.size();
    // 考察n-1轮
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n-1-i; ++j) {  // 这一轮要考察的部分
            if (A[j] > A[j+1]) {  // 每次考察相邻的一对
                std::swap(A[j], A[j+1]);
            }
        }
    }
}

下面开始,是实用的排序算法。

插入排序 (Insertion Sort)

插排的原理就类似于抓扑克牌,每次摸一张牌,然后把它插入之前已经有序的牌中。

插入排序的具体做法如下:

  1. 从第2个元素开始(第1个元素已经有序),在已经有序的序列中从右往左走,如果当前位置元素大于待插入元素,就将其往右挪一位,直到走到数组头部或者走到第一个小于等于待插入元素的位置,将待插入元素挪到到该位置之后;
  2. 取出下一个元素(未排序的序列),重复上面的步骤,直到整个序列处理完。

insertion sort example

  • 插排的性能总体而言是比较好的,尤其在数组近似有序的时候,因为每个元素平均移动的次数将比较少。
  • 虽然最坏时间复杂度是$O(n^2)$(数组完全逆序),但是最佳时间复杂度是$O(n)$(数组完全有序)。
  • STL中,sort内部的算法中在排序的后期使用了插排。

参考代码(C++):

template<typename T>
void InsertionSort(vector<T>& A) {
    int n = A.size();
    for (int i = 1; i < n; ++i) {
        T temp = std::move(A[i]);
        int j;
        for (j = i; j > 0 && temp < A[j-1]; --j) {
            A[j] = std::move(A[j-1]);
        }
        A[j] = std::move(temp);
    }
}

堆排序 (Heap Sort)

基本思想:建堆,之后利用堆的性质不断取出最大/最小值,同时维护堆性。

  • 高效实用的排序算法
  • 建堆的平摊时间复杂度是O(n),取出最值O(1),维护堆性O(logn),因此堆排序的时间复杂度是$O(n \log n)$,且无须额外空间
template<typename T>
void HeapSort(vector<T>& A) {
    int n = A.size();
    
    /**
     * 第一步:将数组堆化(这里是建最大堆)
     * 从第一个非叶子节点开始执行SiftDown操作
     * begin_idx: 第一个非叶子节点的位置
     * 如果堆顶从0开始,那么一个节点j的父节点是(j-1)/2
     */
    int begin_idx = n / 2 - 1;  // (n-1 - 1) / 2 = n/2 - 1
    for (int i = begin_idx; i >= 0; --i) {
        SiftDown(A, i, n);
    }
    
    /**
     * 第二步:对堆化数据排序
     */
    for (int i = n - 1; i > 0; --i) {
        std::swap(A[0], A[i]);  // 等价于:取出堆顶,与最后一个节点交换
        SiftDown(A, 0, i);  // 维持堆性,这时堆的size = i
    }
}

SiftDown是非常关键的操作:

template<typename T>
void SiftDown(vector<T>& A, int i, int n) {
    /**
     * 对位置i处的节点做SiftDown(最大堆)
     * n: 当前堆的有效size
     */
    T tmp = std::move(A[i]);
    int child;
    
    for (; 2*i+1 < n; i = child) {  // 循环条件是左孩子存在
        int lchild = 2*i + 1, rchild = lchild + 1;
        child = lchild;
        if (rchild < n && A[rchild] > A[lchild]) {  // 选择左右孩子中较大的
            child = rchild;
        }
        if (tmp < A[child]) {
            A[i] = std::move(A[child]);
        } else break;
    }
    A[i] = std::move(tmp);
}

归并排序 (Merge Sort)

基本思想:Divide & Conquer

  • 把数组一分为二,分为长度大致相等的左、右两个子数组
  • 分别对左、右子数组进行排序
  • 左右子数组有序后,合并它们
  • 处理左、右子数组时,递归地进行

merge sort example

归并排序的递归方程: \(T(n) = 2 T\left(\frac{n}{2}\right) + O(n)\) $T(n)$表示对整个数组进行排序的时间,$2T\left(\frac{n}{2}\right)$表示对两个子数组进行排序的时间,而$O(n)$表示合并两个子数组的时间复杂度。求解这个递归方程,得到$T(n) = O(n\log{n})$。

关于时间复杂度,也可以这么简单地理解:划分原问题为更小规模子问题的复杂度是$O(\log{n})$(其实是个递归树,而且这里是二叉树),合并已排好序的数组的复杂度是$O(n)$,因而是$O(n\log{n})$。

参考程序(C++):

首先是排序入口:

template<typename T>
void MergeSort(vector<T>& A, int start, int end) {
    if (start >= end) return;
    int mid = start + (end - start) / 2;
    MergeSort(A, start, mid);
    MergeSort(A, mid+1, end);
    Merge(A, start, mid, end);
}

然后是合并排序数组的操作:

template<typename T>
void Merge(vector<T>& A, int start, int mid, int end) {
    vector<T> helper(end-start+1);  // 临时开辟辅助数组(在外部预先申请好空间可以提高效率)
    int p = start, q = mid+1, k = 0;
    while (p <= mid && q <= end) {
        if (A[p] < A[q]) helper[k++] = A[p++];
        else helper[k++] = A[q++];
    }
    while (p <= mid) helper[k++] = A[p++];
    while (q <= end) helper[k++] = A[q++];
    std::copy(helper.begin(), helper.end(), A.begin()+start);  // 拷贝回原数组(大数据比快排慢的主要原因)
}

快速排序 (Quick Sort)

我喜欢把快排称为「划分排序」(Partition Sort),因为这是其工作原理所在。至于为什么叫「快排」,顾名思义,因为快嘛——它是目前在实际应用中表现最好的算法之一(虽然平均意义上的时间复杂度依然是$O(n \log n)$)。

快排和归并排序可以说是一对「姐妹算法」,体现了正向思维和逆向思维的联系。快排的基本思想是先让数组整体有序,再对局部进行递归操作。而归并排序是先局部有序,然后通过合并有序的局部来构造有序的整体。

总体步骤:

  1. 如果数组只有1个元素,不做任何操作,返回
  2. 选取一个主元(pivot),对原数组进行划分(partition)。通常的做法是以pivot为分界点将数组分为两部分,使得左边的元素都小于pivot,右边的元素都不小于pivot。
  3. 分别对左、右两部分进行排序

可以在HackerRank练习,那里的教程写得比较详细。先练习Partition的实现,再练习整个排序的递归实现。后面还有复杂度的讲解。基本上认真做一遍,就能很好地理解快排了~

关于快排的复杂度分析,这里就不搬运了,CLRS上有详细的推导。

通常Partition的实现是「就地」(in-place)进行的,因为这样可以避免额外的空间开销,从而提高效率。Partition的写法不止一种,往往Pivot的选取不同,Partition的方式也不同。这里给出一种被称为Lomuto Partitioning的划分方法,它选取子数组的最后一个元素作为Pivot,然后用一个变量fstLarger记录第一个比Pivot大的元素位置,它初始化为第一个元素的下标。当往右遍历子数组时,如果遇到了比Pivot小的元素,就将该元素与fstLarger处的元素交换,之后fstLarger往右移一位。还是看图比较直观:

Partition

template<typename T>
int Partition(vector<T>& A, int low, int high) {
    int pivot = A[high];
    int fstLargerPos = low;
    
    for (int i = low; i < high; ++i) {
        if (A[i] < pivot) {
            swap(A[i], A[fstLargerPos]);
            fstLargerPos++;
        }
    }
    std::swap(A[high], A[fstLargerPos]);
    return fstLargerPos;
}

最后返回Pivot所在的位置,Pivot直到整个排序结束都不会改变了,它已经处于「正确」的位置上。这个返回值也是划分的依据,它将决定左、右子数组的长度。于是,快排主体的递归写法如下(还是很简洁的~):

template<typename T>
void QuickSort(vector<T>& A, int low, int high) {
    if (low >= high) return;
    int mid = Partition(A, low, high);
    QuickSort(A, low, mid-1);
    QuickSort(A, mid+1, high);
}
-----EOF-----

Categories: 算法 Tags: 排序 Divide & Conquer