算法基础课题解合集

快速排序算法起源:
1960 年代，英国国家物理实验室 (National Physical Laboratory) 开始了一项新的计划：将俄文自动翻译成英文。正好霍尔有这个经历，他与俄国的机器翻译专家相识，还在“机器翻译” (Machine Translation) 上发表过论文。
于是他在那里得到了一份工作。
在那个年代，俄文到英文的词汇列表是以字母顺序存储在一条长长的磁带上的。因此，当有一段俄文句子需要翻译时，第一步是把这个句子的词按照同样的顺序排列。这样机器就可以在磁带上只走一遍就可以找到所有的翻译。

霍尔意识到，他必须找出一种能在计算机上实现的排序的算法来。
他想到的第一个算法是后人称作“冒泡排序(bubblesort)”的算法。虽然他没有声明这个算法是他发明的，但他显然是独自得到这个算法的。

他很快放弃了这个算法，因为它的速度比较慢。用计算复杂度理论(Computational complexity theory)来说，它平均需要O(n^2)次运算。

快速排序(Quicksort)是霍尔想到的第二个算法。这个算法的计算复杂度是O(nlogn)次运算。当n特别大的时候，显然步骤要少很多。

快排步骤

1. 确定一个分界值 $x$（这里设为中点，左端点会超时）。

2. 将所有小于等于 $x$ 的集中到数组左边，所有大于等于 $x$ 的集中到数组右边。

3. 然后递归处理左边和右边，直到区间里只剩下一个数（此时肯定有序）。

模拟

见下面的动画演示。

时间复杂度

平均时间 $O(nlogn)$，最坏时间 $O(n^2)$。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, q[N];

void quicksort(int l, int r) {
    //如果只有一个点就一定有序
    if (l == r) return;
    int x = q[l + r >> 1];//选取分界点
    /*
        如果把上面这行改成
        int x = q[l];
        则有可能唤醒O(n^2)的复杂度，然后超时
    */
    //由于使用的是do...while，所以要先-1与+1
    int i = l - 1, j = r + 1;
    while (i < j) {
        //找第一个大于等于x的数
        do i ++; while (q[i] < x);
        //找第一个小于等于x的数
        do j --; while (q[j] > x);
        //交换它们
        if (i < j)
            swap(q[i], q[j]);
    }
    //递归处理左边和右边
    quicksort(l, j);
    quicksort(j + 1, r);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> q[i];
    quicksort(0, n - 1);
    for (int i = 0; i < n; i ++)
        cout << q[i] << " ";
    return 0;
}