Chinaunix首页 | 论坛 | 博客
  • 博客访问: 387882
  • 博文数量: 214
  • 博客积分: 770
  • 博客等级: 军士长
  • 技术积分: 1969
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-08 01:22
文章分类

全部博文(214)

文章存档

2013年(110)

2012年(104)

我的朋友

分类:

2012-11-07 12:26:45

原文地址:求数组中第k小的数 作者:scutan

    根据快速排序算法,可快速找到数组中第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;
}

阅读(176) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~