求数组中第k小的数

    根据快速排序算法，可快速找到数组中第k小的数

 

#include <iostream>
using namespace std;

int partition(int arr[], int l, int r)
{
    int i = l - 1;
    int j = r;
    int v = arr[r];
    int tmp;

    for (; ;)
    {
        while (arr[++i] < v)
            ;
        while (v < arr[--j])
            if (j == l)
                break;
        if (i >= j)
            break;
        
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    tmp = arr[i];
    arr[i] = arr[r];
    arr[r] = tmp;
    return i;
}

void quicksort(int arr[], int l, int r)
{
    int i;
    if (r <= l)
        return;
    i = partition(arr, l, r);
    quicksort(arr, l, i-1);
    quicksort(arr, i+1, r);
}

void select(int arr[], int l, int r, int k)
{
    int i;
    if (r <= l)
        return;
    i = partition(arr, l, r);
    if (i > k)
        select(arr, l, i-1, k);
    else if (i < k)
        select(arr, i+1, r, k);
    else
        printf("%d th number is %d\n", k, arr[k]);
}

int main()
{
    int arr[15] = {10, 21, 2, 1, 3, 45, 2, 932, 32, 27, 86, 65, 576, 434, 76753};
    int arr2[15] = {10, 21, 2, 1, 3, 45, 2, 932, 32, 27, 86, 65, 576, 434, 76753};
    int i;
    
    cout << "Original array" << endl;
    for (i = 0; i < 15; i++)
        cout << arr[i] << " ";
    cout << endl << endl;

    
    quicksort(arr, 0, 14);

    cout << "Sorted array" << endl;
    for (i = 0; i < 15; i++)
        cout << arr[i] << " ";
    cout << endl;

    select(arr2, 0, 14, 13);
    return 0;
}