IntroSort-内省排序

d0j1a_1701 · 2020-10-17 20:37:35 · 个人记录

前置知识

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为“已排序”和“未排序”两部分，每次从“未排序的”元素中选择一个插入到“已排序的”元素中的正确位置。

插入排序在序列已部分有序的情况下效率很高。

插入排序的最优时间复杂度为 O(n) ，最差与平均时间复杂度为 O(n^2) 。

快速排序

快速排序的工作原理是通过 分治 的方式来将一个数组排序。

快速排序分为三个过程：

将数列划分为两部分（要求保证相对大小关系）； 递归到两个子序列中分别进行快速排序； 不用合并，因为此时数列已经完全有序。 和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度，一般是随机选择一个数 x 来当做两个子数列的分界。

之后，维护一前一后两个指针 i 和 j ，依次考虑当前的数是否放在了应该放的位置（前还是后）。如果当前的数没放对，比如说如果后面的指针 j 遇到了一个比 x 小的数，那么可以交换 i 和 j 位置上的数，再把 j 向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。

其实，快速排序没有指定应如何具体实现第一步，不论是选择 x 的过程还是划分的过程，都有不止一种实现方法。

第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。

普通快排的最优与平均时间复杂度为 O(n\log n) 最差情况下为 O(n^2) 。

堆排序

堆排序的工作原理为对所有待排序元素建堆，然后依次取出堆顶元素，就可以得到排好序的序列。

堆排序的时间复杂度为 O(n\log n) 。

注：为了缩短代码长度，本文章内堆排序使用STL优先队列实现。

正文

这是朴素的双路快排：

void quickSort(int l, int r) {
    if(l >= r)    return;
    int i = l, j = r;
    int pivot = arr[l];
    while(i < j) {
        while(i < j && arr[j] >= pivot) j--;
        while(i < j && arr[i] <= pivot) i++;
        if(i < j)
            swap(arr[i], arr[j]);
    }
    swap(arr[l], arr[i]);
    quickSort(l, i - 1);
    quickSort(i + 1, r);
}

在一些极端情况下，普通的快速排序会退化为 O(n^2) 的冒泡排序，这通常会导致用时大幅提升，为了避免这种情况，在实际实现时会做优化。

Step 1:基准点的选择

基准点的选择对快速排序的性能有极大的影响。在上文的代码中，始终选择区间的最左侧数据作为基准点。

基准点若选成区间的最大/最小值会导致退化（遍历区间时pivot始终大于或小于其他所有元素，这会导致第6和7行的循环把区间遍历两遍）；最好的情况应选择区间内元素的中位数（每次恰好将区间内元素分割成大于、小于基准点的两部分，只需遍历一遍），但这通常无法实现，会导致时间常数大幅增高。

一种常见的方法是使用随机基准点：

void quickSort(int l, int r) {
    if(l >= r)    return;
    int i = l, j = r;
    swap(arr[l], arr[rd() % (r - l + 1) + l]);//随机选择基准点
    int pivot = arr[l];
    while(i < j) {
        while(i < j && arr[j] >= pivot) j--;
        while(i < j && arr[i] <= pivot) i++;
        if(i < j)
            swap(arr[i], arr[j]);
    }
    swap(arr[l], arr[i]);
    quickSort(l, i - 1);
    quickSort(i + 1, r);
}

随机选择基准点情况下，几乎不可能每次都选中区间的极值。

另一种方法是从区间最左侧，区间中央，区间最右侧取中位数做基准点（三数取中法），这种方法只需少量比较即可获得（不那么准确的）中位数，在序列已有序时获得良好的效果，STL中采用此种方法。

int getPivot(int l, int r) {
    int ix = l, iy = r - 1, iz = (l + r - 1) >> 1;
    int x = arr[ix], y = arr[iy], z = arr[iz];
    if(x > y) {
        if(x > z) {
            if(y > z) {
                return iy;
            } else {
                return iz;
            }
        } else {
            return ix;
        }
    } else {
        if(x > z) {
            return ix;
        } else {
            if(y > z) {
                return iz;
            } else {
                return iy;
            }
        }
    }
}
void quickSort(int l, int r) {
    if(l >= r)    return;
    int i = l, j = r;
    swap(arr[l], arr[getPivot(l,r)]);//三数取中法
    int pivot = arr[l];
    while(i < j) {
        while(i < j && arr[j] >= pivot) j--;
        while(i < j && arr[i] <= pivot) i++;
        if(i < j)
            swap(arr[i], arr[j]);
    }
    swap(arr[l], arr[i]);
    quickSort(l, i - 1);
    quickSort(i + 1, r);
}

Step 1.5：

经过优化的快排在遇到大量相同数据时还是会超时，所以可以使用三路快速排序，它将区间分割成大于基准点，等于基准点，小于基准点三部分。但是因为我不会写实现难度大，而且在后续优化后效果不明显，本文章不采用此方法。

Step 2：

当区间长度很小（如 r-l \le 16 ）时，再让快排去分割没有意义。如果使用插入排序进行小范围排序，反而能得到更好的效果。

int getPivot(int l, int r) {
    int ix = l, iy = r - 1, iz = (l + r - 1) >> 1;
    int x = arr[ix], y = arr[iy], z = arr[iz];
    if(x > y) {
        if(x > z) {
            if(y > z) {
                return iy;
            } else {
                return iz;
            }
        } else {
            return ix;
        }
    } else {
        if(x > z) {
            return ix;
        } else {
            if(y > z) {
                return iz;
            } else {
                return iy;
            }
        }
    }
}
void insertSort(int l, int r) {
    for(int i = l + 1; i <= r; i++) {
        int j = i;
        while(j > l) {
            if(arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
                j--;
            } else {
                break;
            }
        }
    }
}
void quickSort(int l, int r, int deep) {
    if(l >= r)  return;
    if(r - l <= 16) {
        insertSort(l,r);
        return;
    }
    int i = l, j = r;
    swap(arr[l], arr[getPivot(l, r)]);
    int pivot = arr[l];
    while(i < j) {
        while(i < j && arr[j] >= pivot) j--;
        while(i < j && arr[i] <= pivot) i++;
        if(i < j)
            swap(arr[i], arr[j]);
    }
    swap(arr[l], arr[i]);
    quickSort(l, i - 1, deep + 1);
    quickSort(i + 1, r, deep + 1);
}

Step 3：

在递归深度大于 2\log n 时，如果再使用快速排序分割会导致退化为冒泡排序。可以在递归深度大于 2\log n 时切换为堆排序，这样就得到内省排序。

内省排序（英语：Introsort 或 Introspective sort）是快速排序和 堆排序 的结合，由 David Musser 于 1997 年发明。内省排序其实是对快速排序的一种优化，保证了最差时间复杂度为 n \log n 。

内省排序将快速排序的最大递归深度限制为 2\log n ，超过限制时就转换为堆排序。这样既保留了快速排序内存访问的局部性，又可以防止快速排序在某些情况下性能退化为 n^2 。

2000 年 6 月，SGI C++ STL 的 stl_algo.h 中 sort(）函数的实现采用了内省排序算法。

完整代码（可通过P1177 【模板】快速排序）：

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int n, maxdeep;
int arr[100010];
priority_queue<int, vector<int>, greater<int> > pq;
void insertSort(int l, int r) {
    for(int i = l + 1; i <= r; i++) {
        int j = i;
        while(j > l) {
            if(arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
                j--;
            } else {
                break;
            }
        }
    }
}
int getMaxDeep(int x) {
    int k;
    for(k = 0; x > 1; x >>= 1)  k++;
    return k * 2;
}
int getPivot(int l, int r) {
    int ix = l, iy = r - 1, iz = (l + r - 1) >> 1;
    int x = arr[ix], y = arr[iy], z = arr[iz];
    if(x > y) {
        if(x > z) {
            if(y > z) {
                return iy;
            } else {
                return iz;
            }
        } else {
            return ix;
        }
    } else {
        if(x > z) {
            return ix;
        } else {
            if(y > z) {
                return iz;
            } else {
                return iy;
            }
        }
    }
}
void heapSort(int l, int r) {
    for(int i = l; i <= r; i++) pq.push(arr[i]);
    for(int i = l; i <= r; i++) {
        arr[i] = pq.top();
        pq.pop();
    }
}
void introSortLoop(int l, int r, int deep) {
    if(l >= r)  return;
    if(r - l <= 16) {
        return;//经测试，在排序完成后直接执行一次插入排序更快
    }
    if(deep >= maxdeep) {
        heapSort(l, r);
        return;
    }
    int i = l, j = r;
    swap(arr[l], arr[getPivot(l, r)]);
    int pivot = arr[l];
    while(i < j) {
        while(i < j && arr[j] >= pivot) j--;
        while(i < j && arr[i] <= pivot) i++;
        if(i < j)
            swap(arr[i], arr[j]);
    }
    swap(arr[l], arr[i]);
    introSortLoop(l, i - 1, deep + 1);
    introSortLoop(i + 1, r, deep + 1);
}
void introSort(int l, int r) {
    introSortLoop(l, r - 1, 0);
    insertSort(l, r - 1);//经测试，在排序完成后直接执行一次插入排序更快（STL实现）
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    maxdeep = getMaxDeep(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    introSort(0, n);
    for(int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    return 0;
}

Q/A:

Q:为什么不直接使用归并排序或堆排序等时间复杂度为 O(n \log n) 的排序？

A:快速排序的分治算法在大多数情况下内存访问效率极高，虽然都是 O(n\log n) 但是快排比其他的快。

Q:为什么还是没有STL快？

A:STL做了许多特殊优化，比如插入排序有“带边界保护”和“无边界保护”的两个版本。这导致比较次数更少，在数据范围大时造成显著影响。