《编程珠玑》学习之快速找到第K个大小的元素

给定一串无序的数字，如何找到从0开始算第K大的元素？听到这样一个问题你会有哪些思路？
这本是一道《编程珠玑》的练习题目，出自快速排序那一章，看到这你就应该把解这道题目和快速排序的做法联系在一起了。算法是这样的，在这串数字里找出个pivot，用来分割这串数字，经过O(n)时间复杂度之后，达到pivot左边的数字都小于（或等于）pivot，pivot右边都大于pivot。举例来说，给定int inputArray[] = {57, 354, 12, 3, 0, 99, 120, 2}; 使用57作为pivot，经过一次处理，得到
12，3，0，2，57，354，99，120。看到这里你会有一个问题，如果没有选57，而选0或者354作为pivot，那经过一次处理岂不是...? 对，我们要选出一个比较中等大小的数字作为pivot，可以考虑挑选一串数字中位置的第一个，最后一个和中间一个中第二大的数字来做pivot，即inputArray[left]，inputArray[(left+right)/2]和inputArray[right]中的第二大的数做pivot。
选好了pivot，我们就可以开始下一步的工作了。选出pivot，看pivot是排第几个，如果正好是第K个，那就欧了，已经找到，算法结束；如果pivot是第j个，而j>k,那就是说第k个元素在pivot的左边，然后递归处理左侧的数据；如果j

#include "stdafx.h"
#include "iostream"
#include <string>

using namespace std;

static int swapCount = 0;

void myswap(int& x1, int& x2)
{
    int temp = x2;
    x2 = x1;
    x1 = temp;
    swapCount++;
}

void insertSort(int* arr, int left, int right)
{
    if (arr == 0)
    {
        string* NullPtrInput = new string("NULL POINTER in insertSort!");
        throw NullPtrInput;
    }
    if (left >= right)
    {
        string* invalidInput = new string("left is larger than right in insertSort!");
        throw invalidInput;
    }

    for (int i = 0; i <= right - left; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (arr[j+left] > arr[j-1+left])
                break;
            else
                myswap(arr[j-1+left], arr[j+left]);
        }
    }
}

int qsort_k(int* arr, int left, int right, int k)
{
    if (!arr)
    {
        string* NullPtrInput = new string("NULL POINTER in qsort");
        throw NullPtrInput;
    }
    if (left >= right)
        return -1;

    // find a middle number as the pivot
    int mid = (left + right) / 2;
    int tempArr[3] = {arr[left], arr[mid], arr[right]};
    insertSort(tempArr, 0, 2);

    if (tempArr[1] == arr[mid]) // find mid, place it in the left of the array
    {
        myswap(arr[left], arr[mid]);
    }
    else if (tempArr[1] == arr[right])
    {
        myswap(arr[left], arr[right]);
    }

    int swapnode = left+1;
    bool hasNotFoundBiggerThanPivot = true;
    for (int i = left + 1; i <= right; i++)
    {
        if (arr[left] > arr[i])
        {
            if (hasNotFoundBiggerThanPivot)
            {
                swapnode++;
                continue;
            }
            myswap(arr[swapnode++], arr[i]);
        }
        else
        {
            if (hasNotFoundBiggerThanPivot)
            {
                hasNotFoundBiggerThanPivot = false;
                continue;
            }
        }
    }

    int pivot = swapnode-1;
    myswap(arr[left], arr[pivot]);

    if (pivot == k)
        return arr[pivot];
    else if (pivot > k)
        return qsort_k(arr, left, pivot-1, k);
    else
        return qsort_k(arr, pivot+1, right, k);
}

int _tmain(int argc, _TCHAR* argv[])
{

    int arrayForSort[] = {545, 1, 57, 102, 60, 69, 274, 64, 32, 97, 10, 23, 78,
                          21, 104, 265, 592, 312, 0, 122, 13, 56, 57, 993, 102,
                          745, 43743, 3, 4556, 112, 367, 784, 52356, 5378, 987,
                          66, 98, 421, 369, 787, 23, 98, 666, 671, 38, 2500, 9};

    cout << "input array:" << endl;
    for (int i = 0; i < sizeof(arrayForSort)/sizeof(int); i++)
        cout << arrayForSort[i] << " ";
    cout << endl;

    int indexForSearch = 16; // start from zero
    if (indexForSearch >= sizeof(arrayForSort)/sizeof(int))
    {
        cout << "indexForSearch out of bound, start from 0" << endl;
        system("pause");
        return 0;
    }
    int myfinding = qsort_k(arrayForSort, 0, sizeof(arrayForSort)/sizeof(int) - 1, indexForSearch);
    cout << "The " << indexForSearch << "th (0 based) number is " << myfinding << endl;
    cout << "swap count is " << swapCount << endl;
    system("pause");
    return 0;
}

line 55：找pivot的时候，用一个插入排序来排3个数字，然后选出第二大的数。运行程序，有如下打印
input array:
545 1 57 102 60 69 274 64 32 97 10 23 78 21 104 265 592 312 0 122 13 56 57 993
02 745 43743 3 4556 112 367 784 52356 5378 987 66 98 421 369 787 23 98 666 671
8 2500 9
The 16th (0 based) number is 66
swap count is 67
可以看到，算法经过了67次交换，找到了第16大的元素是66。算法中递归的部分比较常规，而比较tricky的地方是如何经过O(n)把pivot的左边和右边分开，代码66到90行做了这个事，代码是我自己写的，当然不如大师写的那么简洁，不过工作起来效果是一样的。