基于快速排序的快速选择

基于快速排序的快速选择

         ——《数据结构与算法分析——C语言描述》

         快速选择有很多方法，这里不做一一介绍。《重谈快速排序》中我们介绍了快速排序的相关实现细节。这里我们介绍一种基于快速排序的快速选择方法。

         其实现原理和快速排序类似。

         给出一个序列，我们不知道该序列是否已经排好序，如果我们想从中选择第k小的数，该怎么做？最简单最直观的方法是对这个序列进行排序，然后依据k选择索引为k-1数即可。由于排序的时间复杂度为O(NlogN)。所有这种选择第k小的数的时间复杂度是O(NlogN)。

         这样会造成一定的浪费，因为我们仅仅是想从中选择第k个小的数，而对序列进行排序导致前k-1个数和后面的n-k个数都是有序的，这种有序对选择第k个小的数没有什么意义。所以，排序造成了一定的浪费。

         利用快速排序原理选择第k小的数，时间复杂度平均情况下可以达到O(N)，最差的时间复杂度为O(N*N)。

         其原理是：每次对序列按照枢纽元进行左右风格，分割后，i指向枢纽元。如果k=i+1，则arr[i]就是序列中第k小的数；如果k<i+1，则第k小的数在左半部分，继续对左半部分进行分割，选择左半部分中第k个小的数；如果k>i+1，则第k小的数在右半部分，继续对右半部分进行分割，选择右半部分中第k-i-1小的数。

         如果我们直接在原序列上进行快速选择，则会打乱原来序列中元素的位置。如果不想打乱元素的位置，可以拷贝临时的一份作为快速选择的序列。

         下面我们对基于快速排序的快速选择进行实现如下：

// 基于快速排序的快速选择
#include <iostream>
using namespace std;

// 交换函数
void swap(int& a, int& b)
{
    int t = a;
    a = b;
    b = t;
}

// 该函数用于选择合适的枢纽元
// 具体做法是：选取三个元素，这三个元素为待排序序列中的第一个、最后一个、中间一个
// 去三个元素的中位数，作为快排的枢纽元
// 三个元素的选取也可以完全随机，但是没必要完全随机
// 该函数有两个功能：1.选择合适的枢纽元；2.将枢纽元交换到right-1位置
int Median3(int arr[], int left, int right)
{
    // 取中间的坐标
    int center = (left + right) / 2;

    // 对三个数进行排序
    if (arr[left] > arr[center])
    {
        swap(arr[left], arr[center]);
    }
    if (arr[left] > arr[right])
    {
        swap(arr[left], arr[right]);
    }
    if (arr[center] > arr[right])
    {
        swap(arr[center], arr[right]);
    }

    // 我们选arr[center]作为枢纽元
    // arr[right]本身会大于等于枢纽元
    // arr[left]本身会小于等于枢纽元
    // 所以，我们不再将枢纽元置坐标置为right，而是置为right-1
    // 在后续操作中，i的初始值设置为left+1，j的初始值设置为right-2

    // 将枢纽元置于序列的后面，但不是最后一个——right，而是right-1
    swap(arr[center], arr[right - 1]);

    // 返回枢纽元
    return arr[right - 1];
}

// 打印序列
void PrintArr(int arr[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << arr[i] << ' ';
    }
    cout << endl;
}

// 插入排序
// 时间复杂度O(N*N)
void InsertionSort(int arr[], int n)
{
    if (n <= 1)
    {
        return;
    }
    for (int i = 1; i < n; ++i)
    {
        int tmp = arr[i];
        int p   = i - 1;
        while (p >= 0 && arr[p] > arr[p + 1])
        {
            arr[p + 1] = arr[p];
            --p;
        }
        arr[p + 1] = tmp;
    }
}

// 用于定义调用快速排序的最低元素个数：Cutoff+1
const int Cutoff = 3;

// 实现基于快速排序的快速查找
void QSelect(int arr[], int k, int left, int right)
{
    int i = 0, j = 0;
    int pivot = 0;

    if (left + Cutoff <= right)
    {
        pivot = Median3(arr, left, right);
        i = left;
        j = right - 1;

        for (;;)
        {
            while (arr[++i] < pivot);
            while (arr[--j] > pivot);

            if (i < j)
            {
                swap(arr[i], arr[j]);
            }
            else
            {
                break;
            }
        }
        swap(arr[i], arr[right - 1]);

        if (k < i + 1)
        {
            QSelect(arr, k, left, i - 1);
        }
        else if (k > i + 1)
        {
            QSelect(arr, k, i + 1, right);
            // QSelect(arr + i + 1, k - i - 1, 0, right - i - 1);
        }
        else // k = i + 1
        {
            // 找到了第k小的数
            ;
        }
    }
    else
    {
        InsertionSort(arr + left, right - left + 1);
    }
}

// 对QSelect封装
int QuickSelect(int arr[], int k, int n)
{
    // 开辟一个新的副本，以免打乱原来的序列
    int* tmp = new int[n];
    memcpy(tmp, arr, sizeof (*tmp) * n);

    QSelect(tmp, k, 0, n - 1);

    cout << "tmp:";
    PrintArr(tmp, n);

    int t = tmp[k - 1]; // 第k小的数，其索引为k-1

    delete [] tmp;

    return t;
}

// 实现基于快速排序的快速查找2
int QSelect2(int arr[], int k, int left, int right)
{
    int i = 0, j = 0;
    int pivot = 0;

    if (left + Cutoff <= right)
    {
        pivot = Median3(arr, left, right);
        i = left;
        j = right - 1;

        for (;;)
        {
            while (arr[++i] < pivot);
            while (arr[--j] > pivot);

            if (i < j)
            {
                swap(arr[i], arr[j]);
            }
            else
            {
                break;
            }
        }
        swap(arr[i], arr[right - 1]);

        if (k < i + 1)
        {
            return QSelect2(arr, k, left, i - 1);
        }
        else if (k > i + 1)
        {
            return QSelect2(arr, k, i + 1, right);
            // QSelect(arr + i + 1, k - i - 1, 0, right - i - 1);
        }
        else // k = i + 1
        {
            // 找到了第k小的数
            return arr[i]; // 索引k-1
        }
    }
    else
    {
        InsertionSort(arr + left, right - left + 1);
        return arr[k - 1]; // 索引k-1
        // return (arr + left)[k - left - 1];
    }
}

// 对QSelect2封装
int QuickSelect2(int arr[], int k, int n)
{
    // 开辟一个新的副本，以免打乱原来的序列
    int* tmp = new int[n];
    memcpy(tmp, arr, sizeof (*tmp) * n);

    int t = QSelect2(tmp, k, 0, n - 1);

    cout << "tmp:";
    PrintArr(tmp, n);

    delete [] tmp;

    return t;
}

int main()
{
    int arr[] = {8, 1, 4, 9, 6, 3, 5, 2, 7, 10};

    PrintArr(arr, sizeof (arr) / sizeof (*arr));

    cout << QuickSelect(arr, 5, sizeof (arr) / sizeof (*arr)) << endl;
    PrintArr(arr, sizeof (arr) / sizeof (*arr));

    cout << QuickSelect2(arr, 5, sizeof (arr) / sizeof (*arr)) << endl;
    PrintArr(arr, sizeof (arr) / sizeof (*arr));

    cout << endl;

    int arr2[] = {9, 9, 9, 9, 9, 9, 9, 9, 9, 9};

    PrintArr(arr2, sizeof (arr2) / sizeof (*arr2));

    cout << QuickSelect(arr2, 8, sizeof (arr2) / sizeof (*arr2)) << endl;
    PrintArr(arr2, sizeof (arr2) / sizeof (*arr2));

    cout << QuickSelect2(arr2, 8, sizeof (arr2) / sizeof (*arr2)) << endl;
    PrintArr(arr2, sizeof (arr2) / sizeof (*arr2));

    return 0;
}

         其他快速选择算法将在后续介绍。