《数据结构与算法分析：C语言描述》复习——第六章“排序”——快速排序

2014.06.17 05:15

简介：

　　快速排序是实际应用最广的基于内存的不稳定的比较排序。拥有O(n * log(n))的平均复杂度和O(n^2)的最坏复杂度。采用的思路是分治法，递归实现。

描述：

　　快速排序的基本思路，是从数组中选取一个值pivot作为参照，使得比pivot小的都在它左边，比pivot大的都在它右边。pivot的英文意思是支点，从这个你应该能猜到——左右的元素最好数目接近。如果偏向很多，效果就不好了。如此递归排序两个小段，就可以完成整个数组的排序了。思路很简单，实现起来却不是那么简单。讲解快速排序的原理也许得废很多话，不如逐行仔细阅读代码，体会每一步执行的过程。我认为这其中最难理解的，莫过于++和--之处。由于实现快速排序的难度，光是“写个快排看看”就算是一道面试题了。

　　由于我曾经在面试时被直接要求写出快速排序，当时的我完全无力招架（那时可以说基本不会写代码，而且还自我感觉良好）。所以现在一提到快速排序我就非常小心，几乎是按照教材上的代码实现的。在这段不算长的代码中随便改掉一点，都容易造成各种错误。实际上我在别人的不少技术博客中的确找到了错误，有些运行结果明显不对，但代码长得和正确版本几乎一模一样。这应该就是那种很不直观，但代码简洁的神级之算法吧。

实现：

// My implementation for quick sort.
#include <iostream>
#include <vector>
using namespace std;

const int CUT_OFF = 4;

static void swap(int &x, int &y)
{
    int tmp;
    
    tmp = x;
    x = y;
    y = tmp;
}

static int medianThree(vector<int> &v, int left, int right)
{
    int center = (left + right) / 2;
    
    if (v[left] > v[right]) {
        swap(v[left], v[right]);
    }
    if (v[left] > v[center]) {
        swap(v[left], v[center]);
    }
    if (v[center] > v[right]) {
        swap(v[center], v[right]);
    }
    swap(v[center], v[right - 1]);
    
    return v[right - 1];
}

static void quickSortRecursive(vector<int> &v, int left, int right)
{
    if (right - left + 1 >= CUT_OFF) {
        int i, j;
        int pivot = medianThree(v, left, right);
        
        i = left;
        j = right - 1;
        while (true) {
            while (v[++i] < pivot) {}
            while (v[--j] > pivot) {}
            if (i < j) {
                swap(v[i], v[j]);
            } else {
                break;
            }
        }
        swap(v[i], v[right - 1]);
        quickSortRecursive(v, left, i - 1);
        quickSortRecursive(v, i + 1, right);
    } else {
        int i, j;
        int tmp;
        
        for (i = left + 1; i <= right; ++i) {
            tmp = v[i];
            for (j = i; j > left && v[j - 1] > tmp; --j) {
                v[j] = v[j - 1];
            }
            v[j] = tmp;
        }
    }
}

void quickSort(vector<int> &v)
{
    int n = (int)v.size();
    quickSortRecursive(v, 0, n - 1);
}

int main()
{
    vector<int> v;
    int n, i;
    
    while (cin >> n && n > 0) {
        v.resize(n);
        for (i = 0; i < n; ++i) {
            cin >> v[i];
        }
        quickSort(v);
        for (i = 0; i < n; ++i) {
            cout << v[i] << ' ';
        }
        cout << endl;
    }
    
    return 0;
}