• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            The Way of C++

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              55 Posts :: 0 Stories :: 19 Comments :: 0 Trackbacks

            公告

            The first time i use this blog, i will write something that i learn which i think is worth write down.

            常用鏈接

            留言簿(3)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            利用快速排序的分組思路,假設對當前主元值t,已將數組分成三個部分,a[0,m-1]部分都小于t,a[m]等于t,a[m+1,n-1]大于等于t,此時比較m+1與k,若m+1<k,可知第k個元素在右半部分,所以將分組區間的左下標改為m+1,同理,若m+1>k,則將分組區間的右下標改為m-1,若是m+1==k,則表示找到了第k個元素,返回a[m]。可知這個算法的時間復雜度為O(cn),其中c為某個很小的常數。實現時,依賴于分組的方法,有單向分級與雙向分組,用隨機生成的百萬個數據進行測試,結果單向分組的時間為雙向分組的兩倍。
            代碼如下:
            #include<stdio.h>
            #include<time.h>
            #define MAX 1000001
            int n,k;
            int h[MAX];
            int search1()
            {
                    int l,r,i,m,t,temp;
                    for(l=0,r=n-1;;)
                    {
                            t=h[l];
                            m=l;
                            for(i=l+1;i<=r;++i)
                                    if(h[i]<t)
                                    {
                                            temp=h[i];
                                            h[i]=h[++m];
                                            h[m]=temp;
                                    }
                            h[l]=h[m];
                            h[m]=t;
                            if(m+1<k) l=m+1;
                            else if(m+1>k) r=m-1;
                            else break;
                    }
                    return h[m];
            }

            int search()
            {
                    int l,r,i,j,t,temp;
                    for(l=0,r=n-1;;)
                    {
                            t=h[l];
                            i=l,j=r+1;
                            while(1)
                            {
                                    do{
                                            i++;
                                    }while(i<=r&&h[i]<t);
                                    do{
                                            j--;
                                    }while(j>=l+1&&h[j]>=t);
                                    if(i>j)
                                            break;
                                    else
                                    {
                                            temp=h[i];
                                            h[i]=h[j];
                                            h[j]=temp;
                                    }
                            }
                            h[l]=h[j];
                            h[j]=t;
                            if(j+1<k)
                                    l=j+1;
                            else if(j+1>k)
                                    r=j-1;
                            else break;
                    }
                    return h[j];
            }

            int main()
            {
                    scanf("%d%d",&n,&k);
                    int i,j;
                    for(i=0;i<n;++i)
                            scanf("%d",&h[i]);
                    time_t start,end;
                    start=clock();
                    printf("%d\n",search());
                    end=clock();
                    printf("%f\n",((end-start)*1.0)/CLOCKS_PER_SEC);

                    return 0;
            }

            posted on 2010-03-17 16:25 koson 閱讀(313) 評論(0)  編輯 收藏 引用 所屬分類: ACM
            久久精品国产99久久无毒不卡| 久久精品无码一区二区WWW| 久久久无码精品亚洲日韩蜜臀浪潮 | 日韩久久久久中文字幕人妻| 久久久99精品一区二区| 97精品伊人久久大香线蕉| 亚洲欧美久久久久9999| 亚洲第一极品精品无码久久 | 老男人久久青草av高清| 久久人妻少妇嫩草AV蜜桃| 色综合久久综合中文综合网| 色8久久人人97超碰香蕉987| 精品久久久久久久无码| 久久精品亚洲欧美日韩久久| 精品综合久久久久久97| 久久精品国产免费一区| 久久久中文字幕日本| 精品久久久久中文字幕日本 | 久久AV高潮AV无码AV| 久久亚洲精品国产精品| 久久久久亚洲精品无码网址| 久久AV高清无码| 久久久噜噜噜久久中文字幕色伊伊| 国产巨作麻豆欧美亚洲综合久久| 久久偷看各类wc女厕嘘嘘| 日韩中文久久| 久久精品中文騷妇女内射| 一本色道久久综合| 久久精品综合一区二区三区| 久久精品国产亚洲AV无码麻豆| 久久精品国产99国产精品导航 | 国产精品久久午夜夜伦鲁鲁| 久久久久国产一级毛片高清版| 国产一级持黄大片99久久| 伊人久久大香线蕉av不卡| 一个色综合久久| 久久精品桃花综合| 性做久久久久久免费观看| 好属妞这里只有精品久久| 国产精品一久久香蕉国产线看观看| 久久久久亚洲精品日久生情|