精华内容
下载资源
问答
  • 使用BitSet对1000万个Int整数进行排序

    千次阅读 2017-09-12 21:48:39
    //因为BitSet中可以存true/false,而且是按位存储,所以在数据量很大的...// 下面是我使用Bitset和Arrays工具类进行排序的测试类 public class BitSetSort { public static void main(String[] args) { // Stri
    //因为BitSet中可以存true/false,而且是按位存储,所以在数据量很大的时候,合理的使用BitSet可以节省很大的内存空间,
    //提高程序的运算效率。
    
    // 下面是我使用Bitset和Arrays工具类进行排序的测试类
    
    public class BitSetSort {
    
    	public static void main(String[] args) {
    //		String sortNums = sortNums(generateNumber(10000000));
    		sortNums1(generateNumber(10000000));
    //		System.out.println(sortNums);
    	}
    	
    	// 初始化一千万整数
    	private static int[] generateNumber(int size){
    		long start = System.currentTimeMillis();
    		System.out.println("开始生成数据");
    		int[] nums = new int[size];
    		for(int i=0;i<size;i++){
    			nums[i] = RandomUtils.nextInt(0, size);
    		}
    		System.out.println("生成数据完成,耗时:"+(System.currentTimeMillis()-start)+"毫秒");
    		return nums;
    	}
    	
    
            // 使用BitSet进行排序
    	private static String sortNums(int[] nums){
    		long start = System.currentTimeMillis();
    		System.out.println("开始排序");
    		int len = nums.length;
    		StringBuilder sb = new StringBuilder();
    		BitSet bitSet = new BitSet(len);
    		bitSet.set(0, len, false);
    		for(int i=0;i<len;i++){
    			bitSet.set(nums[i], true);
    		}
    		for(int i=0;i<len;i++){
    			if(bitSet.get(i)){
    				sb.append(i).append(",");
    			}
    		}
    		System.out.println("排序完成,耗时:"+(System.currentTimeMillis()-start)+"毫秒");
    		return sb.toString();
    	}
    	
    
            // 使用Arrays工具类进行排序
    	private static int[] sortNums1(int[] nums){
    		long start = System.currentTimeMillis();
    		System.out.println("开始排序");
    		Arrays.sort(nums);
    		System.out.println("排序完成,耗时:"+(System.currentTimeMillis()-start)+"毫秒");
    		return nums;
    	}
    	
    }


    结果:

    1、使用BitSet排序

    开始生成数据
    生成数据完成,耗时:172毫秒
    开始排序
    排序完成,耗时:429毫秒


    2、使用Arrays工具类排序

    开始生成数据
    生成数据完成,耗时:172毫秒
    开始排序
    排序完成,耗时:1078毫秒




    展开全文
  • bitmap与桶方式对1000万数据进行排序

    千次阅读 2013-07-16 11:08:30
    1. 100数据的产生,随机数方式 #include #include #include #include #include using namespace std; const int size = 10000000; int num[size]; int main() { int n; FILE *fp = fopen("data.txt", "w");

    1.  100万数据的产生,随机数方式

    #include <iostream>
    #include <time.h>
    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    using namespace std;
    const int size = 10000000;
    int num[size];
    int main()
    {
        int n;
        FILE *fp = fopen("data.txt", "w");
        assert(fp);
        for (n = 1; n <= size; n++)
        
        //之前此处写成了n=0;n<size。导致下面有一段小程序的测试数据出现了0,特此订正。
        num[n] = n;
        srand((unsigned)time(NULL));
        int i, j;
        for (n = 0; n < size; n++)
        {
            i = (rand() * RAND_MAX + rand()) % 10000000;
            j = (rand() * RAND_MAX + rand()) % 10000000;
            swap(num[i], num[j]);
        }
        for (n = 0; n < size; n++)
        fprintf(fp, "%d ", num[n]);
        fclose(fp);
    
        return 0;
    }


    使用bit_set 进行排序

    //位图方式解决海量数据排序,数据不能有重复
    
    //使用 C++ stl的 bitset
    #include <iostream>
    #include <bitset>
    #include <assert.h>
    #include <time.h>
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;
    const int max_each_scan = 5000000;
    int main()
    {
        clock_t begin = clock();
        bitset<max_each_scan> bit_map;
        bit_map.reset();
        // open the file with the unsorted data
        FILE *fp_unsort_file = fopen("data.txt", "r");
        assert(fp_unsort_file);
        int num;
        
        // the first time scan to sort the data between 0 - 4999999
        while (fscanf(fp_unsort_file, "%d ", &num) != EOF)
        {
            if (num < max_each_scan)
            //有这个数字,将bit_map的对应的位设置为1
            bit_map.set(num, 1);
        }
        FILE *fp_sort_file = fopen("sort.txt", "w");
        assert(fp_sort_file);
        int i;
        // write the sorted data into file
        for (i = 0; i < max_each_scan; i++)
        {
            if (bit_map[i] == 1)
            fprintf(fp_sort_file, "%d ", i);
        }
        
        // the second time scan to sort the data between 5000000 - 9999999
        int result = fseek(fp_unsort_file, 0, SEEK_SET);
        if (result)
        cout << "fseek failed!" << endl;
        else
        {
            bit_map.reset();
        while (fscanf(fp_unsort_file, "%d ", &num) != EOF)
        {
            if (num >= max_each_scan && num < 10000000)
            {
                num -= max_each_scan;
                bit_map.set(num, 1);
            }
        }
        for (i = 0; i < max_each_scan; i++)
        {
            if (bit_map[i] == 1)
            fprintf(fp_sort_file, "%d ", i + max_each_scan);
        }
        }
        clock_t end = clock();
    
        cout<<"用位图的方法,耗时:"<<endl;
        cout << (end - begin) / CLK_TCK << "s" << endl;
        fclose(fp_sort_file);
        fclose(fp_unsort_file);
        return 0;
    }

    位图排序的实现

    #include <iostream>
    #include <memory.h>
    #define BYTESIZE 8
    using namespace std;
    void setBit(char *p,int posi)
    {
        for(int i = 0;i < (posi/BYTESIZE);i ++)
        {
            p ++;
        }
        *p = *p|(0x01 << (posi%BYTESIZE));//将该Bit位赋值1
        return;
    }
    int main()
    {
        int num[] = {3,2,5,7,12,24,9,8,6};
        const int BufferLen = 2;
        char *pBuffer = new char[BufferLen];
        memset(pBuffer,0,BufferLen);
    
        for(int i = 0;i < 9;i ++)
           setBit(pBuffer,num[i]);
    
        //输出排序结果
        for(int i = 0;i < BufferLen;i ++)//每次处理一个字节
        {
            for(int j = 0;j < BYTESIZE;j ++)
            {
                if( (*pBuffer&(0x01<<j)) == (0x01<<j))
                cout << i * BYTESIZE + j << " ";
            }
            pBuffer ++;
        }
        return 0;
    }


    归并排序方式实现

    //copyright@ 纯净的天空 && yansha
    //5、July,updated,2010.05.28。
    #include <iostream>
    #include <ctime>
    #include <fstream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    //#include "ExternSort.h"
    using namespace std;
    //使用多路归并进行外排序的类
    //ExternSort.h
    /** 大数据量的排序
    * 多路归并排序
    * 以千万级整数从小到大排序为例
    * 一个比较简单的例子,没有建立内存缓冲区*/
    #ifndef EXTERN_SORT_H
    #define EXTERN_SORT_H
    #include <cassert>
    class ExternSort
    {
        public:void sort()
        {
            time_t start = time(NULL);
        //将文件内容分块在内存中排序,并分别写入临时文件
        int file_count = memory_sort();
        //归并临时文件内容到输出文件
        merge_sort(file_count);
        time_t end = time(NULL);
        printf("total time:%f/n", (end - start) * 1000.0/ CLOCKS_PER_SEC);
        }
    
        //input_file:输入文件名
        //out_file:输出文件名
        //count: 每次在内存中排序的整数个数
        ExternSort(const char *input_file, const char * out_file, int count)
        {
            m_count = count;
            m_in_file = new char[strlen(input_file) + 1];
            strcpy(m_in_file, input_file);
            m_out_file = new char[strlen(out_file) + 1];
            strcpy(m_out_file, out_file);
        }
        virtual ~ExternSort()
        {
            delete [] m_in_file;
        delete [] m_out_file;
        }
        private:int m_count;
        //数组长度
        char *m_in_file;
          //输入文件的路径
          char *m_out_file;
          //输出文件的路径
          protected:int read_data(FILE* f, int a[], int n)
          {
              int i = 0;
              while(i < n && (fscanf(f, "%d", &a[i]) != EOF))
              i++;
              printf("read:%d integer/n", i);
              return i;
              }
        void write_data(FILE* f, int a[], int n)
        {
            for(int i = 0; i < n; ++i)
            fprintf(f, "%d ", a[i]);
        }
        char* temp_filename(int index)
        {
            char *tempfile = new char[100];
            sprintf(tempfile, "temp%d.txt", index);
            return tempfile;
        }
        static int cmp_int(const void *a, const void *b)
        {
            return *(int*)a - *(int*)b;
        }
        int memory_sort()
        {
            FILE* fin = fopen(m_in_file, "rt");
            int n = 0, file_count = 0;
            int *array = new int[m_count];
            //每读入m_count个整数就在内存中做一次排序,并写入临时文件
            while(( n = read_data(fin, array, m_count)) > 0)
            {
                qsort(array, n, sizeof(int), cmp_int);
                 //这里,调用了库函数阿,在第四节的c实现里,不再调用qsort。
                 char *fileName = temp_filename(file_count++);
                 FILE *tempFile = fopen(fileName, "w");
                 free(fileName);
                 write_data(tempFile, array, n);
                 fclose(tempFile);
            }
            delete [] array;
            fclose(fin);
            return file_count;
        }
        void merge_sort(int file_count)
        {
            if(file_count <= 0)
            return;
            //归并临时文件
            FILE *fout = fopen(m_out_file, "wt");
            FILE* *farray = new FILE*[file_count];
            int i;
            for(i = 0; i < file_count; ++i)
            {
                char* fileName = temp_filename(i);
                farray[i] = fopen(fileName, "rt");
                free(fileName);
            }
            int *data = new int[file_count];
            //存储每个文件当前的一个数字
            bool *hasNext = new bool[file_count];
            //标记文件是否读完
            memset(data, 0, sizeof(int) * file_count);
            memset(hasNext, 1, sizeof(bool) * file_count);
            for(i = 0; i < file_count; ++i)
            {
                if(fscanf(farray[i], "%d", &data[i]) == EOF)
                //读每个文件的第一个数到data数组
                hasNext[i] = false;
            }
            while(true)
            {
                //求data中可用的最小的数字,并记录对应文件的索引
                int min = data[0];
                int j = 0;
                while (j < file_count && !hasNext[j])
                j++;
                if (j >= file_count)
                //没有可取的数字,终止归并
                break;
                for(i = j + 1; i < file_count; ++i)
                {
                    if(hasNext[i] && min > data[i])
                    {
                        min = data[i];j = i;
                    }
                }
                if(fscanf(farray[j], "%d", &data[j]) == EOF)
                //读取文件的下一个元素
                hasNext[j] = false;
                fprintf(fout, "%d ", min);
            }
            delete [] hasNext;
            delete [] data;
            for(i = 0; i < file_count; ++i)
            {
                fclose(farray[i]);
            }
            delete [] farray;
            fclose(fout);
            }
            };
    #endif
    //测试主函数文件
    /** 大文件排序*
    数据不能一次性全部装入内存*
     排序文件里有多个整数,
     整数之间用空格隔开*/
    const unsigned int count = 10000000;
    // 文件里数据的行数
    const unsigned int number_to_sort = 1000000;
    //在内存中一次排序的数量
    const char *unsort_file = "data.txt";
    //原始未排序的文件名
    const char *sort_file = "sort_data.txt";
    //已排序的文件名
    void init_data(unsigned int num);
    //随机生成数据文件
    int main(int argc, char* *argv)
    {
        srand(time(NULL));
        init_data(count);
        ExternSort extSort(unsort_file, sort_file, number_to_sort);
        extSort.sort();
    
        return 0;
    }
    void init_data(unsigned int num)
    {
        FILE* f = fopen(unsort_file, "wt");
        for(int i = 0; i < num; ++i)
        fprintf(f, "%d ", rand());
        fclose(f);
    }



    桶排序方式实现

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <iostream>
    #include <ctime>
    #define LOW 18           //桶大小
    #define FILE_NUM 39       //桶对应的文件数
    
    #define MEM_SIZE 256*1024
    using namespace::std;
    
    int memory[MEM_SIZE];     //1M
    
    
    //对ifp中的数据进行排序,结果输出到ofp中 ,i是正在处理的桶的编号
    void sort(FILE*ifp, FILE *ofp, int i)
    {
        memset(memory,0,1024*1024);
    
        int d;
        int high=i<<LOW;             //保存数据的高位
    
        if(fscanf(ifp, "%d", &d)==1)
        {
            ++memory[d&0x3ffff]; //计数,只是用低18位
            high=d&0xfffc0000;   //保存高位
    
        }
    
        while(fscanf(ifp, "%d", &d)==1)
        {
    
            ++memory[d&0x3ffff]; //计数,不考虑高五位
        }
    
        for (int i=0; i<MEM_SIZE; ++i)
        {
            int num=memory[i];
            while(num--)
            {
                fprintf(ofp,"%d ",i|high);       //输出结果
            }
    
    
        }
    
    
    }
    
    int main()
    {
       FILE *fp_tmp[FILE_NUM];
       FILE *fp_data;
    
       if(NULL==(fp_data=fopen("data.txt","r"))) //打开测试数据
              exit(0);
       int d;
       int i;
    
       time_t start = time(NULL);    //开始计时
    
       for (i=0; i<FILE_NUM; ++i)      //创建桶对应的FILE_NUM个文件
       {
           char buf[64]="tmp_";
           char buf_int[4];
           itoa(i, buf_int, 10);
           strcat(buf,buf_int);
           strcat(buf,".txt");
    
           if((fp_tmp[i]=fopen(buf,"w+"))==NULL)
               exit(0);
    
       }
    
       while(fscanf(fp_data,"%d",&d)==1)     //读入数据存放到各个桶中
       {
           int i = d >> LOW;  //不管这个数多大,右移18位啊,都变成0了
    
            fprintf(fp_tmp[d >> LOW], "%d ",d&0x3ffff);
       }
        for (i=0; i<FILE_NUM; ++i)         //初始化文件指针
       {
            rewind(fp_tmp[i]);
    
        }
    
       FILE * out_fp;
       if(NULL==(out_fp=fopen("out.txt","w")))        //out.txt用于保存排序后的数据
            exit(0);
    
       for (i=0; i<FILE_NUM; ++i)
       {
    
            sort(fp_tmp[i],out_fp,i);        //分别对每个桶进行排序
    
        }
    
    
    
        for (i=0; i<FILE_NUM; ++i)      //关闭文件
       {
            fclose(fp_tmp[i]);
    
        }
        time_t end = time(NULL);         //停止计时
    
        printf("total time:%f/n", (end - start) * 1000.0/ CLOCKS_PER_SEC);
    
       return 0;
    }


    展开全文
  • 最多1000万个正整数的文件,每个数7位正整数,没有任何重复,不与其他关联  输出: 升序排列的输出文件 约束:1MB的内存空间,最短的运行时间 1000万数据需要使用800万位(1MB)来表示,只使用一次读入读出文件。...

    注:此问题来自《编程珠玑》第一章

    问题描述:

    最多1000万个正整数的文件,每个数7位正整数,没有任何重复,不与其他数关联

     输出:

    升序排列的输出文件

    约束:1MB的内存空间,最短的运行时间

    1000万数据需要使用800万位(1MB)来表示,只使用一次读入读出文件。可考虑使用位图来解决。

    分3步:

    初始化:所有位置0;

    for(i=0;i<n;i++)

       bit[i]=0;

    从文件读入数据,每读入一个数据,相应位置1,

    while()

    {

    fin>>num;

    bit[num=1;

    }

    检查每一位,该位为1,则输出对应整数。

    for(i=0;i<n;i++)

    {

    if(bit[i])

    fout>>i;

    }

    展开全文
  • 冒泡排序(时间复杂度N2,空间复杂度1) 依次比较数组相邻两元素,将最大或最小元素放到后面,慢慢“浮”到数列的最后。 选择排序(时间复杂度N2,空间...将数组分为有序和无序两部分,默认组左变第一元素是...
    1. 冒泡排序(时间复杂度N2,空间复杂度1)
      依次比较数组相邻两个元素,将最大或最小元素放到后面,慢慢“浮”到数列的最后。
    2. 选择排序(时间复杂度N2,空间复杂度1)
      首先找到数组最小元素,将它和数组的第一个元素交换位置。再次,在剩下的元素中找到最小的元素,将它与数组第二个元素交换,如此往复。
    3. 插入排序(时间复杂度介于N和N2之间,空间复杂度1)
    4. 将数组分为有序和无序两个部分,默认数组左变第一个元素是有序的,依次遍历数组第二个元素到最后,与数组左变有序序列比较。如果小于左变有序序列则交换位置。
    5. 希尔排序(时间复杂度NlogN,空间复杂度1)
      分组+插入排序。插入排序只能交换相邻的元素,元素只能一点一点从数组的一端移动到另一端。希尔排序的思想是使数组中任意间隔为gap的数组都是有序的。经验公式:gap=gap/3+1,如果有12个元素,那么同一组元素相邻元素间隔4,下一次分组间隔2,最后一次间隔1。
    6. 归并排序(时间复杂度NlogN,空间复杂度N(递归临时变量))
      将两个有序数组归并到第三个数组中,递归在发生在处理数组之后。
    7. 快速排序(时间复杂度NlogN,空间复杂度lgN))
      与归并一样,都是利用分治的排序算法。将数组分成两个子数组,将两部分独立排序,递归发生在处理数组之前。不需要额外的内存空间存储一个临时数组。
    8. 堆排序(时间复杂度NlogN,空间复杂度1)
      利用堆(一种特殊的完全二叉树)而设计的一种排序算法。如果是正序排序,先构建一个最大堆,交换a[1]和a[n],此时a[n]就是数组中最大元素。n–,a[1]向下调整保持最大堆特性,进行下一次交换。
    9. 桶排序(时间复杂度lg(M+N),空间复杂度N)
      构建一个临时数组book,长度为要排序数组的最大值。遍历一次数组a,记录a[i]的值的次数:book[a[i]]++j.最后遍历一遍数组book,将i值和出现的数次写到数组a中。

    这里是引用

    #include<iostream>
    #include<time.h>
    #include <sys/timeb.h>
    using namespace std;
    //效率测试
    #define NUMBER 1000000
    long long getSystemTime()
    {
    	struct timeb t;
    	ftime(&t);
    	return 1000 * t.time + t.millitm;
    }
    
    
     void bucketSort(int *a,int *book, int len)
    {
    	 for (int i = 0; i < len; i++)
    	 {
    		 int tem = a[i];
    		 book[tem]++;
    	 }
    	 int k = 0;
    	 for (int i = 0; i < NUMBER; i++)
    	 {
    		 int ncount = book[i];
    		 for (int j = 0; j < ncount; j++)
    		 {
    			 a[k++] = i;
    		 }
    	 }
    }
    
     //-----------------三向切分的快速排序 ---------------------
    void quick3WaySort(int *a, int left, int right)
    {
    	if (left > right) return;
    	int lt = left;
    	int i = left + 1;
    	int gt = right;
    	int tem = a[left];
    	while (i <= gt)
    	{
    		if (a[i] < tem)  //小于切分元素的放在lt左边,lt和i整体右移
    		{
    			//exchange(a, lt++, i++);
    			int tmp = a[i];
    			a[i] = a[lt];
    			a[lt] = tmp;
    			lt++; i++;
    		}
    		else if (a[i] > tem)//大于切分元素的放在gt右边,因此gt左移
    		{
    			//exchange(a, i, gt--);
    			int tmp = a[i];
    			a[i] = a[gt];
    			a[gt] = tmp;
    			gt--;
    		}
    		else
    			i++;
    	}
    	quick3WaySort(a,left,lt-1);
    	quick3WaySort(a, gt+1, right);
    }
    
    
    #if 0
    void quickSort(int *a, int left, int right)
    {
    	if (left > right) return;
    	int i = left;
    	int j = right;
    	int tem = a[left];
    	while (i != j) 
    	{
    		while (a[j]>tem && i<j)
    			j--;
    		while (a[i] <= tem &&i<j)
    			i++;
    		if (i < j)
    		{
    			int t = a[j];
    			a[j] = a[i];
    			a[i] = t;
    		}
    	}
    
    	a[left] = a[i];
    	a[i] = tem;
    
    	quickSort(a, left, i - 1);
    	quickSort(a, i+1, right);
    	return;
    }
    #endif
    //---------------堆排序--------------------
    void shiftDown(int *a,int len,int i)
    {
    	int index, flag = 0;
    	//----结点有左孩子-----
    	while (i * 2 <= len && flag == 0)
    	{
    		if (a[i] < a[i * 2])
    			index = i * 2;
    		else
    			index = i;
    		//----结点有左孩子-----
    		if (i * 2 + 1 <= len)
    		{
    			if (a[index] < a[i * 2 + 1])
    				index = i * 2 + 1;
    		}
    		if (index != i)
    		{
    			//---交换i节点与子节点,更新编号为下一次向下调整准备
    			int tem = a[i];
    			a[i] = a[index];
    			a[index] = tem;
    			i = index;  
    		}
    		else
    		{
    			flag = 1;
    		}
    	}
    }
    
    
    void heapSort(int *a, int len)
    {
    	//-------------建最大堆----------------
    	for (int i = len / 2; i >= 1; i--)
    	{
    		shiftDown(a,len,i);
    	}
    	//--------------排序-------------------
    	while (len>1)
    	{
    		int tem = a[len];
    		a[len] = a[1];
    		a[1] = tem;
    		len--;
    		shiftDown(a,len,1);
    	}
    }
    
    
    //-------------------归并排序-------------------------
    void merge(int *a, int first, int mid, int last, int *temp)
    {
    	int i = first;      // 第1个有序序列的开始下标
    	int j = mid + 1;    // 第2个有序序列的开始下标
    	int len = 0;
    	// 合并两个有序序列
    	while (i <= mid && j <= last)
    	{
    		if (a[i] < a[j])
    		{
    			// 找二者中比较小的数
    			temp[len] = a[i];
    			i++;
    		}
    		else
    		{
    			temp[len] = a[j];
    			j++;
    		}
    		len++;
    	}
    	while (i <= mid)
    	{
    		temp[len] = a[i];
    		i++;
    		len++;
    	}
    	while (j <= last)
    	{
    		temp[len] = a[j];
    		j++;
    		len++;
    	}
    	// 找到原来的第一个有序序列的开始位置覆盖无序序列
    	for (int k = 0; k < len; k++)
    	{
    		a[first+k] = temp[k];
    	}
    }
    
    void mergeSort(int *a, int first, int last, int *temp)
    {
    	if (first == last)
    		return;
    	int mid =  first+ (last - first) / 2; //防止first+last溢出
    	mergeSort(a, first, mid, temp);
    	mergeSort(a, mid+1, last, temp);
    	merge(a, first, mid, last, temp);
    }
    
    //-------------------希尔排序-------------------
    void shellSort(int *a, int len)
    {
    	int gap = len;
    	int index, tem;
    	while (gap > 1)
    	{
    		gap = gap / 3 + 1;
    		// =======分组, 对每一组, 进行插入排序
    		for (int i = 0; i < gap; i++)
    		{
    			//----插入排序----------
    			for (int j = i + gap; j < len; j += gap)
    			{
    				index=j;  
    				tem=a[j];
    				for (int k = j; k > i; k -= gap)
    				{
    					if (tem < a[k - gap])
    					{
    						a[k] = a[k - gap];
    						index = k - gap;
    					}
    					else
    					{
    						break;
    					}
    				}
    				a[index] = tem;
    			}
    		}
    	}
    }
    
    
    //--------------------插入排序---------------------
    void insertSort(int *a, int len)
    {
    	int index;
    	int tem;
    	// 遍历无序序列
    	for (int i = 1; i < len; i++)
    	{
    		index = i;  //存储当前基准数位置
    		tem = a[i];
    		// 遍历有序序列
    		for (int j = i; j >0; j--)
    		{
    
    			if (tem < a[j - 1])  //找到比基准数大的位置,则将有序序列后移,并记录有序序列位置
    			{
    				a[j] = a[j - 1];
    				index = j - 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    		a[index] = tem; //将基准数填入
    	}
    }
    
    //--------------选择排序---------------
    
    void selectSort(int *a, int len)
    {
    	for (int i = 0; i < len; i++)
    	{
    		int min = i;//基准书位置
    		for (int j = i + 1; j < len; j++)
    		{
    			if (a[min] > a[j])
    				min = j; //没遍历一次,找到最小值的序号
    		}
    		
    		int tem = a[min];  //交换基准数和最小元素
    		a[min] = a[i];
    		a[i] = tem;
    	}
    }
    
    //----------------冒泡排序------------------
    void bubbleSort(int *a, int len)
    {
    	int flag = 0;//0表示没有排序好,1表示排序好了
    	for (int i = 0; i < len && flag == 0; i++)
    	{
    		//每进行一次冒泡,首先默认已经排好
    		flag = 1;
    		for (int j = 1; j < len - i; j++)
    		{
    			if (a[j] < a[j - 1])
    			{
    				int tem = a[j - 1];
    				a[j - 1] = a[j];
    				a[j] = tem;
    				flag = 0;
    			}
    
    		}
    	}
    }
    
    int main()
    {
    	long long timeStart, timeEnd, timeUse;
    	srand((unsigned)time(NULL));
    
    	int(*array)[NUMBER] = new int[7][NUMBER];
    	int *arrayHeap = new int[NUMBER+1];
    
    	//-----归并和桶排序额外的内存---
    	int *mergeArray = new int[NUMBER];
    	int *bucketArrayBook = new int[NUMBER]();
    	for (int i = 0; i < NUMBER; ++i)
    	{
    		//生成一个小于len的随机数
    		int number = rand() % NUMBER;
    		for (int j = 0; j < 7; ++j)
    		{
    			array[j][i] = number;
    		}
    		arrayHeap[i+1] = number;
    	}
    
    
    	cout << "对第" << NUMBER << "个数进行排序" << endl;
    	timeStart = getSystemTime();
    	bucketSort(array[0], bucketArrayBook, NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "bucketSort     耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	quick3WaySort(array[1], 0, NUMBER-1);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "quick3WaySort  耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	heapSort(arrayHeap, NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "heapSort       耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	mergeSort(array[2],0, NUMBER-1, mergeArray);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "mergeSort      耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	shellSort(array[3], NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "shellSort      耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	insertSort(array[4], NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "insertSort     耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	selectSort(array[5], NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "selectSort     耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	bubbleSort(array[6], NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "bubbleSort     耗时:" << timeUse << "ms" << endl;
    
    	delete []array;
    	delete arrayHeap;
    	delete mergeArray;
    	delete bucketArrayBook;
    }
    

    在这里插入图片描述
    在这里插入图片描述
    总结:
    1.在这8中排序算法当中,桶排序是最快的,冒泡排序最慢。
    但是,桶排序要求构建一个待排序最大元素的数组,往往排序的时候我们并不能确定最大元素的值,另一方面和并归排序一样,当数组很大的时候,也要考虑额外的内存分配问题。
    2.在数组非常长的排序,各种排序算法中,三向切分快速排序是最快的(较快速排序提升了20%到30%)。但是,需要考虑递归产生临时是否会导致栈溢出的问题。堆排序时间复杂度ONlogN,空间复杂度1,并且对已经排序好的数组插入一个元素的时候,堆是一种优先队列的时间,查找和插入的时间复杂度较优。
    3.对于小数组,快速排序比插入排序慢。因此在设计排序的时候可以考虑通过判断长度来切换排序算法。

    展开全文
  • 输入: 一最多包含n不重复的正整数的文件,其中每个数都小于n,每个数是一7位的整数, n=10^7。 条件: 最多有1MB的内存可用, 排序最多只允许执行几分钟,10s是比较理想的运行时间.有充足的磁盘存储空间可用. ...
  • 1000万整数中寻找最大的100个数,最优的算法是建一大小为100的小顶堆(堆排序需要建立完全二叉树),先取出前100个数并构建小顶堆,然后遍历数据与小顶堆的堆顶相比,比堆顶小直接丢弃,比堆顶大则替换堆顶,并...
  • 创建时间:2006年5月28属性:原创内容简介:快速排序,堆排序关键字:快速排序,堆排序排序前序从某网上看到google的面试题目,要求从1000000个数中选出10最大的,题目好像有些挑战性,想了半天,只知道用快速...
  • 1000万数据怎么同时需要排序和持续记录,用什么语句或者思路实现?既要实现实时的数据记录,也要能保持数据的排序顺序?
  • 海量大数据(大约1000万数据每天)要求按照时间排序后存入dat文件,用什么语句可以实现?怎么样做才能做到性能最高?
  • 无法运行到100万个数,到10有时候就会出错了;2. 想要在生成随机数之后将随机数保存在一TXT文件中,在将数据全部排序之后将排序后的数据也保存在同一TXT文件中,但是我写出来的代码总是有问题,TXT中保存的都...
  • 自己动手写排序算法,快速排序是比较不好写的了~ import java.util.*; class Test{ public void quickSort(int[] arr,int low,int high){ if(low){ int i=low; int j=high; int x=arr[low]; while(i...
  • C语言_数据结构:随机10000数字,进行所学的8(9)大排序 题目: 由计算机生成10000整数,使用所学几种排序算法进行排序,统计排序所用的时间,分析各种排序的性能。 创建数组 //创建数组 int *CreatArray() {...
  • 如何1千万整数进行快速排序

    千次阅读 2018-12-12 18:32:57
    公众号【编程珠玑】:专注但不限于分享计算机编程基础,...输入:一最多包含n正整数的文件,每个数都小于n,其中n=10^7。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。 输出...
  • 10亿个数中找出1000个最大的的算法思路: 1,先拿出前1000个数字...3, 如果tempMaxValue 比 minValue 大, 则将 theMaxValue 放入前1000个数中,再排序并找出minValue . 4 … 依此类推。 即可得到1000个最大的。...
  • 一千万个数高效求和

    千次阅读 2020-01-04 11:49:01
    然而,有一种任务,例如,超过1000万个元素的数组进行排序,这种任务本身可以并发执行,但如何拆解成小任务需要在任务执行的过程中动态拆分。这样,大任务可以拆成小任务,小任务还可以继续拆成更小的任务,最后把...
  • #这程序是把以下几个排序全部执行并输出各自的排序时间 import time import random class Sort: # 快速排序 def parttion(a, low, high): pivotkey = a[low] while (low < high): # 因为得把所有元素都按...
  • 产生第i随机数,逐个检查之前产生过的随机数(a[0]~a[i-1]) 是否有重复,无重复则放进数组a[i],若有则得新产生,直到没有重复为止。缺点是效率太低,在检测 重复性的问题 上耗费太多。时间复杂度为O(n^3),实测跑...
  • 本书第一章提出了一看似简单的问题,有最多1000万条不同的整型数据存在于硬盘的文件中,如何在1M内存的情况下其进行尽可能快的排序。 每数字用4byte,1M即可存储250 000数据,显然,只要每次250 000...
  • * 从最后一非叶子节点开始,递归到第0, index = n/2 -1 * */ public function buildMaxHeap() { $noLeafNodeIndex = floor(count($this->data)/2) - 1; for ($i = $noLeafNodeIndex; $i>=0; $i--) { ...
  • 据说:snowflake每秒能够产生26万个ID。 源码 本机实测:100万个ID 耗时5秒 /** * 描述: Twitter的分布式自增ID雪花算法snowflake (Java版) * https://github.com/souyunku/SnowFlake * * @author yanpenglei * @...
  • 有一已排好序的数组,要求输入一个数后,按原来排序的规律将它插入到数组中。假设数组长度为10,数组中前9个数(这9个数要求从键盘上输入,输入时要满足自小到大的输入顺序)已经按从小到大进行排序。然后再从键盘...
  • 从100万个数中找出最大的前100个数

    千次阅读 2018-09-18 15:38:24
    (1) 递归所有数据分成[a,b)b(b,d]两区间,(b,d]区间内的都是大于[a,b)区间内的 (2) (b,d]重复(1)操作,直到最右边的区间个数小于100。注意[a,b)区间不用划分 (3) 返回上一区间,并返回此区间的数字...
  • 100亿数据找出最大的1000个数字

    千次阅读 2017-05-18 22:04:58
    100亿数据找出最大的1000个数字
  • (2) (b,d]重复(1)操作,直到最右边的区间个数小于100。注意[a,b)区间不用划分  (3) 返回上一区间,并返回此区间的数字数目。接着方法仍然是上一区间的左边进行划分,分为[a2,b2)b2(b2,d2]两区间,取
  • 排序算法-桶排序的时间复杂度分析

    千次阅读 2019-08-26 14:05:36
    排序思想 桶排序,是一种基于非比较的排序方式,时间复杂度O(n),因此它是是属于一种“线性排序”。 思想:桶排序的思想是将一组数据分到几...假如排序数组的元素个数为n,均匀分布在个数为m的桶中,那么每...
  • 1000万条数据导入mysql

    千次阅读 2013-10-10 21:05:53
    今天需要将一含有1000万条数据的文本内容插入到数据库表中,最初自然想到的是使用Insertinto '表名'values(),(),()...这种插入方式,但是发现这种方式对1000万条数据量的情况,明显效率低下,于是选用了直接将...
  • 归并排序充分利用递归...//归并排序,两两递归的试一半一的分隔直接到只有一元素时返回,然后两两的有序数组进行归并排序,效率相当高 public class MergeSort { /** * @param sourceArray 要排序的源数据 ...
  • 100000随机数排序

    千次阅读 2012-11-20 22:06:55
    问题 时间要求:1000ms ...生成随机数使用基数排序:将整数部分相同的看作相等的,并记录下不同整数对应的随机数的个数和对应的索引起始位置 基数排序后:如下所示,按照整数部分是有序的1.65561
  • 这是《编程珠玑》中的一道题目。10亿整数,假设每整数需要四字节,如果使用排序的话,...二、从文件中读取前一百万个数,每读入一个数,调用函数,保持其最小堆的性质,堆的根永远是堆中最小的元素。 三、从一百

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,611
精华内容 20,244
关键字:

对1000万个数排序