【数据结构】【排序】求第k大的数——用谢尔排序实现

【问题描述】
求n个数中第k大的数

【输入形式】
第一行n k，第二行为n个数，都以空格分开

【输出形式】
第k大的数

【样例输入】

103
182111261229334328

【样例输出】

28

【样例说明】

【评分标准】
时间复杂度大于等于O(k*n)的方法得一半分，时间复杂度小于等于O(n*log₂k)得满分。

提示：

1. 分析各种排序或查找算法的优缺点，分析解决具体问题的时间复杂度，进而找出更高效的算法。

2. n与k的值不同，不同算法的效率也会有影响，如n=10,k=9时，可以找第2小的数。

========================= 谢尔（ShellSort）排序的介绍 ===================

1） MoreWindows的csdn blog

http://blog.csdn.net/morewindows/article/details/6668714

2) 《数据结构教程（第二版）》 北航出版社_唐发根 P333

====== 代码============================================

#include <stdio.h>
#include <stdlib.h>

int main()
{

    int n,k;
    int i;
    int a[1024] = {0};

    scanf("%d%d",&n,&k);

    for( i = 0; i < n; i++ )
        scanf("%d",&a[i]);

    ShellSort(a,n);

    printf("%d",a[n-k+1]);

    return 0;
}

void ShellSort (int a[],int n) {

    int i,j;
    int flag;
    int gap = n;
    int temp;

    while ( gap > 1 ) {

        gap = gap / 2;

        do {

            flag = 0;

            for ( i = 1; i <= n -gap; i++ ) {

                j = i + gap;
                if( a[i] > a[j] ) {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    flag = 1;
                }

            }

        } while ( flag != 0);

    }

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!