精华内容
下载资源
问答
  • 输入:一最多包含n整数的文件,每数都小于n,其中n=10^7。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。 输出:按升序排列的输入整数的列表。 约束:最多有(大约)1MB的...

    转自:https://blog.csdn.net/hyb612/article/details/84977416

    前言

    输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。

    输出:按升序排列的输入整数的列表。

    约束:最多有(大约)1MB的内存空间可用,有充足的磁盘存储空间可用。运行时间最多几分钟,运行时间为10秒就不需要进一步优化。

    这是《编程珠玑》中很有意思的一个问题。今天给大家分享一下并附上自己的代码实现。

    分析

    这个问题的限制在于,大约只有1MB的内存空间可用,而存储10^7个整数却大约需要4*10^7字节即大约需要40M内存,显然是不够用的。
    一种思路是,既然总的内存不够,我们可以读取40次,例如,第一次读取0至249 999之间的数,并对其进行排序输出,第二次读取250 000 至499 999之间的数,并对其排序输出。以次类推,在进行了多次排序之后就完成了对所有数据的排序,并输出到文件中。

    另外一种思路是,既然有充足的磁盘存储空间可用,那么我们可以借助中间文件。读入一次输入文件,利用中间文件进行归并排序写入输出文件。

    那么能否结合两种思路呢?即只需要读取一次,也不借助中间文件?或者说,如何用大约1MB内存空间,即大约800万个比特位最多表示10^7个互异的数呢?

    位图法

    借助位图法当然是可以的。我们可以用一个比特位来代表一个数。例如,对于整数集合{1,2,5,6,7},可以使用下面的比特位表示:

    0 1 1 0 0 1 1 1 
    

    数值存在的比特位置为1,其他位为0,对应上面的即可。分别在第1,2,5,6,7比特位置1即可。而上面的比特位转换为整数值为103,只需要一个字节便可存储。

    回到我们之前的问题。对于最多10^7个整数,我们大约需要10^7个比特位,即10^7/(8*1024*1024)MB,约1.2M的内存即可存储。

    至此,我们可以梳理出算法大体流程:
    1.对给定大小的数组所有比特位置0
    2.循环读取输入文件的数据,并将对应数值大小的比特位置1
    3.遍历数组各比特位,如果位为1,则输出对应比特位的位置整数

    C语言实现

    C语言实现代码如下:

    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #define CHAR_BIT    8            // char类型占用的bit位数
    4. #define SHIFT        3            //右移的位数
    5. #define MAX_NUM        10000000     
    6. #define BIT_SIZE    10000000*8   //所需比特位总数量
    7. #define MAX_STR     10           //一个整数所需最大字符数
    8. #define INPUT_FILE  "srcNum.txt"
    9. #define OUTPUT_FILE "dstNum.txt"
    10. /*将整数对应的比特位置1*/
    11. int putIntoBitMap(char *bitmap, int num)
    12. {
    13.     int byte = num >> SHIFT;
    14.     char bit = 1 << num % CHAR_BIT;
    15.     bitmap[byte] |= (char) bit;
    16.     return 0;
    17. }
    18. /*判断整数是否在位图中*/
    19. int isInBitMap(char *bitmap, int num)
    20. {
    21.     int byte = num >> SHIFT;
    22.     char bit    = 1 << num % CHAR_BIT;
    23.     if (bitmap[byte] & (char) bit)
    24.         return 1;
    25.     else
    26.         return 0;
    27. }
    28. int main(void)
    29. {
    30.     /*打开源文件*/
    31.     FILE *in = fopen( INPUT_FILE, "r" );
    32.     if(NULL == in)
    33.     {
    34.         printf("open src num failed");
    35.         return -1;
    36.     }
    37.     /*申请位图相关内存,并初始化为0*/
    38.     char string[MAX_STR]    = { 0 };
    39.     char *bitmap = (char*)calloc(MAX_NUM,sizeof(char));
    40.     if(NULL == bitmap)
    41.     {
    42.         fclose(in);
    43.         return -1;
    44.     }
    45.     int num = 0;
    46.     /*循环读取文件中的整数,并将对应位置1*/
    47.     while(fgets(string, MAX_STR, in ) != NULL)
    48.     {
    49.         num = atoi(string);
    50.         putIntoBitMap(bitmap, num);
    51.         //printf("%d\n",num);
    52.     }
    53.     fclose(in);
    54.     /*遍历位图中的比特位,为1,则输出整数到文件中*/
    55.     FILE *out = fopen(OUTPUT_FILE, "w+");
    56.     if(NULL == out)
    57.     {
    58.         printf("open dst num failed");
    59.         free(bitmap);
    60.         bitmap = NULL;
    61.         return -1;
    62.     }
    63.     int i;
    64.     for (i = 0; i < BIT_SIZE; i++)
    65.     {
    66.         if (isInBitMap(bitmap , i))
    67.         {
    68.             fprintf(out, "%d\n", i);
    69.             //printf("%d\n",i);
    70.         }
    71.     }
    72.     fclose(out);
    73.     free(bitmap);
    74.     bitmap = NULL;
    75.     return 0;
    76. }

    srcNum.txt中存放了早已生成好的小于10^7的大量无重复整数,编译运行结果如下:

    1. gcc -o bitmap bitmap.c
    2. time ./bitmap
    3. real    0m1.830s
    4. user    0m1.729s
    5. sys    0m0.100s

    可以看到运行时间为秒级。
    关键点说明:

    • putIntoBitMap和isInBitMap函数是该算法的关键函数
    • putIntoBitMap将整数对应的比特位置1
    • isInBitMap 判断整数所在比特位是否为1
    • 例如对于整数81,它所在的字节数是81/8 = 10,第10字节(从0开始数),所在的比特位为81%8=1,第1个比特位。那么我们只需要将第10字节的第1个比特位置1即可。
    • 如何将第n个比特位置1?先将1左移n位(n小于8),得到一个值,再将这个值与该字节进行相或即可。例如,如果需要将第4个比特位置1,则1左移4位,得到二进制的00010000即16,若原来该字节值为01000000,即64时,只需将64与16逻辑或即可。
    1. 00010000
    2. 01000000   
    3. 01010000  #逻辑或之后的结果

    上面的程序还有很多不足之处,包括未对输入做任何检查,未对输入数量做校验等等。这一切都基于输入数据都是正确的,但这丝毫不影响我们对该算法思想的理解。

    总结

    位图法适用于大规模数据,但数据状态又不是很多的情况。对于上面的程序,几乎是做完读取操作之后,排序就完成了,效率惊人。

    思考

    给定一个最多包含40亿个随机排列的32位整数的文件,如何快速判断给出的一个数是否在其中?

    展开全文
  • 点击蓝色“分钟学算法”关注我哟加“星标”,天天中午 12:15,一起学算法作者 | 守望先生来源 | 编程珠玑前言输入:一最多包含n整数的文件,每数都小于n,...
        

    点击蓝色“五分钟学算法”关注我哟

    加个“星标”,天天中午 12:15,一起学算法

    640

    作者 | 守望先生

    来源 | 编程珠玑


    前言

    输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。

    输出:按升序排列的输入整数的列表。

    约束:最多有(大约)1MB的内存空间可用,有充足的磁盘存储空间可用。运行时间最多几分钟,运行时间为10秒就不需要进一步优化。

    这是《编程珠玑》中很有意思的一个问题。今天给大家分享一下并附上自己的代码实现。

    分析

    这个问题的限制在于,大约只有1MB的内存空间可用,而存储10^7个整数却大约需要4*10^7字节即大约需要40M内存,显然是不够用的。
    一种思路是,既然总的内存不够,我们可以读取40次,例如,第一次读取0至249 999之间的数,并对其进行排序输出,第二次读取250 000 至499 999之间的数,并对其排序输出。以次类推,在进行了多次排序之后就完成了对所有数据的排序,并输出到文件中。

    另外一种思路是,既然有充足的磁盘存储空间可用,那么我们可以借助中间文件。读入一次输入文件,利用中间文件进行归并排序写入输出文件。

    那么能否结合两种思路呢?即只需要读取一次,也不借助中间文件?或者说,如何用大约1MB内存空间,即大约800万个比特位最多表示10^7个互异的数呢?

    位图法

    借助位图法当然是可以的。我们可以用一个比特位来代表一个数。例如,对于整数集合{1,2,5,6,7},可以使用下面的比特位表示:

    0 1 1 0 0 1 1 1 

    数值存在的比特位置为1,其他位为0,对应上面的即可。分别在第1,2,5,6,7比特位置1即可。而上面的比特位转换为整数值为103,只需要一个字节便可存储。

    回到我们之前的问题。对于最多10^7个整数,我们大约需要10^7个比特位,即10^7/(8*1024*1024)MB,约1.2M的内存即可存储。

    至此,我们可以梳理出算法大体流程:
    1.对给定大小的数组所有比特位置0
    2.循环读取输入文件的数据,并将对应数值大小的比特位置1
    3.遍历数组各比特位,如果位为1,则输出对应比特位的位置整数

    C语言实现

    C语言实现代码如下:

    #include<stdio.h>#include<stdlib.h>#define CHAR_BIT    8            // char类型占用的bit位数#define SHIFT        3            //右移的位数#define MAX_NUM        10000000     #define BIT_SIZE    10000000*8   //所需比特位总数量#define MAX_STR     10           //一个整数所需最大字符数#define INPUT_FILE  "srcNum.txt"#define OUTPUT_FILE "dstNum.txt"/*将整数对应的比特位置1*/int putIntoBitMap(char *bitmap, int num){    int byte = num >> SHIFT;    char bit = 1 << num % CHAR_BIT;    bitmap[byte] |= (char) bit;    return 0;}/*判断整数是否在位图中*/int isInBitMap(char *bitmap, int num){    int byte = num >> SHIFT;    char bit    = 1 << num % CHAR_BIT;    if (bitmap[byte] & (char) bit)        return 1;    else        return 0;}int main(void){    /*打开源文件*/    FILE *in = fopen( INPUT_FILE, "r" );    if(NULL == in)    {        printf("open src num failed");        return -1;    }    /*申请位图相关内存,并初始化为0*/    char string[MAX_STR]    = { 0 };    char *bitmap = (char*)calloc(MAX_NUM,sizeof(char));    if(NULL == bitmap)    {        fclose(in);        return -1;    }    int num = 0;    /*循环读取文件中的整数,并将对应位置1*/    while(fgets(string, MAX_STR, in ) != NULL)    {        num = atoi(string);        putIntoBitMap(bitmap, num);        //printf("%d",num);    }    fclose(in);    /*遍历位图中的比特位,为1,则输出整数到文件中*/    FILE *out = fopen(OUTPUT_FILE, "w+");    if(NULL == out)    {        printf("open dst num failed");        free(bitmap);        bitmap = NULL;        return -1;    }    int i;    for (i = 0; i < BIT_SIZE; i++)    {        if (isInBitMap(bitmap , i))        {            fprintf(out, "%d", i);            //printf("%d",i);        }    }    fclose(out);    free(bitmap);    bitmap = NULL;    return 0;}

    srcNum.txt中存放了早已生成好的小于10^7的大量无重复整数,编译运行结果如下:

    gcc -o bitmap bitmap.ctime ./bitmapreal    0m1.830suser    0m1.729ssys    0m0.100s

    可以看到运行时间为秒级。
    关键点说明:

    • putIntoBitMap和isInBitMap函数是该算法的关键函数

    • putIntoBitMap将整数对应的比特位置1

    • isInBitMap 判断整数所在比特位是否为1

    • 例如对于整数81,它所在的字节数是81/8 = 10,第10字节(从0开始数),所在的比特位为81%8=1,第1个比特位。那么我们只需要将第10字节的第1个比特位置1即可。

    • 如何将第n个比特位置1?先将1左移n位(n小于8),得到一个值,再将这个值与该字节进行相或即可。例如,如果需要将第4个比特位置1,则1左移4位,得到二进制的00010000即16,若原来该字节值为01000000,即64时,只需将64与16逻辑或即可。

    0001000001000000   01010000  #逻辑或之后的结果

    上面的程序还有很多不足之处,包括未对输入做任何检查,未对输入数量做校验等等。这一切都基于输入数据都是正确的,但这丝毫不影响我们对该算法思想的理解。

    总结

    位图法适用于大规模数据,但数据状态又不是很多的情况。对于上面的程序,几乎是做完读取操作之后,排序就完成了,效率惊人。

    思考

    给定一个最多包含 40 亿个随机排列的 32 位整数的文件,如何快速判断给出的一个数是否在其中?




    本文相关阅读推荐:


    毕业十年后,我忍不住出了一份程序员的高考试卷

    一道腾讯面试题:厉害了我的杯

    十大经典排序算法动画与解析,看我就够了

    这或许是东半球分析十大排序算法最好的一篇文章

    面试官,我会写二分查找法!对,没有 bug 的那种!

    看《长安十二时辰》可以了解哪些算法知识

    GitHub 标星 3w+,很全面的算法和数据结构知识

    640?wx_fmt=png


    展开全文
  • 但是对于初步接触java编程的人来说应该都没有了解太深,今天介绍一个对基础性的对3个整型数字快速排序的方法。 这里运用的方法就是在java学习初期就可以接触到的一个知识—条件表达式! 例: a&amp;amp;gt;b...

    在Java的程序编写中,经常遇到数字排序的问题,今天介绍一个对基础性的对3个整型数字快速排序的方法。
    这里运用的方法就是在java学习初期就可以接触到的一个知识—条件表达式!
    例:
    a>b?a:b;
    这个式子表达的是这样一个过程:判断 a>b 是否成立,返回boolean值,如果返回值为 true,则式子结果为a,反之为b。这样就可以求取两个数的较大值,反之也可以求取最小值。

    同理,我们也可以求取3个数的最大值和最小值,从而也可以对3个整数或实数进行快速排序。
    这里写图片描述
    郁闷,直接发表老是被吞,改成图片了!

    展开全文
  • 快速排序冒泡排序的一种改进,其基本思想是基于分治法的:在待排序表L[1...n]中任取一元素p作为基准 通过一趟排序将待排序的表L划分为两部分L[1...k-1]和L[k+1...n],使得L[1...k-1]中的所有元素小于p,L[k+1...

    什么是“快速排序”?

    快速排序是对冒泡排序的一种改进,其基本思想是基于分治法的:在待排序表L[1...n]中任取一个元素p作为基准

    通过一趟排序将待排序的表L划分为两部分L[1...k-1]和L[k+1...n],使得L[1...k-1]中的所有元素小于p,L[k+1...n]中的所有元素大于等于p,而p放在了其最终位置L[k]上,这个过程称为一趟快速排序。

    而后递归地分别对两个子表重复上述过程,直至每部分内只有一个元素或空为止,即所有元素放在了其最终位置上。

    具体的程序结构:

    int Partition(ElemType A[],int low,int high){
    
        ElemType pivot=A[low];//当前表的第一个元素设为中枢值
        while(low<high){
            while(low<high&&A[high]>=pivot) --high;
            A[low]=A[high];//比中枢值小则移到左端
            while(low<high&&A[low]<pivot) low++;
            A[high]=A[low];//比中枢值大则移到右端
        }
        A[low]=pivot;
        return low;
    
    }
    
    void QuickSort(ElemType A[],int low,int high){
        if(low<high){
        int pivotpos=Partition(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);
        }
    }

     

    展开全文
  • 快速排序(升序)(分治) int partition( int Arr[], int be, int en) // 选取极端的测例:5 4 3 2 1 排成小到大 { int i,j; int temp; i =be+ 1 ; j= en; while (i) // 注意"而不是" // 当i==j时说明...
  • 已知三升序整数数组Given an integer array and we have to sort ... 给定一个整数数组,我们必须在PHP中按升序和降序进行排序。 Methods to sort an array 数组排序方法 In PHP, there are two methods wh...
  • 题目 给一组整数,按照升序... 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法这两部分数据分别进行快速排序,整个排序过程可以递归进行,以
  • 32位无符号整数进行排序

    千次阅读 2012-12-28 09:07:39
    输入一32位无符号整数每一整数十进制表示的每位数字按照降序各位数字进行排序得到一新数。并调整后的该组正整数按照升序排列后输出。按照以下流程完成题目。 流程: 1. 输入无符号整数个数 2....
  • 怎样 40亿8位正整数进行排序

    千次阅读 2010-10-15 23:57:00
    这里可以借鉴快速排序的思想,将整个数据量进行分解,取8位正整数的中间值128,凡是大于这数的值都放入文件b,小于128的都放入文件a。 然后再按照这种方法一直分解直到任意一边的数量小于1千万为止,然后...
  • N个整数中,找到前M(M)最大的数字
  • 本题思路源自Bitmap算法,实际操作可能有一定的限制或难点,仅用于算法思想学习与参考,如有疑问或建议,欢迎留言...定义一数有2种状态,“不存在这数”,“存在这数”,你只有1G出头的运行内存,给出算法设计...
  • 数组有 N 元素,使用快速排序对进行排序输出(本题还会人工阅卷,请使用快速排序算法进行排序) 输入描述: 输入为两行。 第一行一个整数n(1 ≤ n ≤ 100000),表示一共有n元素 第二行为n数,即每元素,每...
  • 自己写的一delphi正整数快速排序

    千次阅读 2013-11-07 15:14:19
    type  TIntArr= array of word; procedure MyQSort(var arr: TIntArr; low: word; high: word); //word可以改为自己需要的类型 var i, j , x, k : word; begin if low begin i:= low;... j:
  • 给定10个整数的序列,要求其重新排序排序要求: 1.奇数在前,偶数在后; 2.奇数按从大到小排序; 3.偶数按从小到大排序。 【输入】 输入一行,包含10个整数,彼此以一空格分开,每个整数的范围是大于...
  • 请编写程序不超过50000个整数递增排序。 输入格式: 输入第一行一整数n,表示待排序的元素数。第二行为n个整数,表示待排序的元素。n不超过50000。 输出格式: 输出为一行,表示排序结果,每个整数后一空格...
  • 整数排序

    2017-05-28 12:22:46
    使用归并排序,快速排序,堆排序或者任何其他 O(n log n) 的排序算法。 样例 给出 [3, 2, 1, 4, 5], 排序后的结果为 [1, 2, 3, 4, 5]。 解题思路: sort()函数就是O(n log n) 的算法。 ...
  • #include<bits/stdc++.h> using namespace std; void InsertSort(vector<int>&v,int n) { int j; for(int i=2;i<=n;i++) { if(v[i]<v[i-1]) { v[0]=v[i]; v[i]=v[i-1];...
  • 问题描述  输入三数,比较其大小,并从大到小输出。 输入格式  一行三个整数。 输出格式  一行三个整数,从大到小排序。 样例输入 33 88 77 样例输出 88 77 33
  • # 题目:n进行排序(快速排序算法) def fast_sort(x, x_list): i, j, r = -1, 0, x - 1 while True: if j == r: x_list[i + 1], x_list[r] = x_list[r], x_list[i + 1] if r != 1 an...
  • 整数排序

    2017-07-19 09:22:20
    问题: ... 题目1190:大整数排序 ...N长度最长可达到1000的数进行排序。 输入: 输入第一行为一个整数N,(1 接下来的N行每行有一数,数的长度范围为1 每数都是一正数,并且保证不包含
  • 代码如下 C# code using System; using System.Collections.Generic; using System.Linq; ...Console.WriteLine("快速排序结果"); for (int i = 0; i ; i++) { Console.WriteLine(arr[i]); } } } }
  • 有一个整数数组,请你根据快速排序的思路,找出数组中第K大的数。 给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间),请返回第K大的数,保证答案存在。 题目分析 利用快速排序,将数组按照标兵即数组的第...
  • #include<iostream> using namespace std; void fun(int N) { int S=1; for(int i=1;i<N;i++) { S+=1; S*=2; } cout<<S; } int main() { int N; cin>>N; fun(N);...}
  • 1、问题 读取一列整数,然后按升序排列它们,...此函数根据你给的比较条件进行快速排序,通过指针移动实现排序 void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const voi
  • 快速排序

    2018-02-05 17:55:33
    普通的快速排序 数据结构实验之排序八:快速...给定N(N≤10^5)个整数,要求用快速排序对数据进行升序排列,注意不得使用STL。 Input 连续输入多组数据,每组输入数据第一行给出正整数N(≤10^5),随后给出N个整数,数

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 101,384
精华内容 40,553
关键字:

对50个整数进行快速排序