排序/合并散列表

Question

对于我的项目，我有一个带有100万桶(有时更多)的哈希表。

每个桶包含许多值，并将它们存储在一个动态数组中。

我正在寻找一种足够简单的方法来存储一个文件中的所有值(printf也可以)，但要以排序的方式进行。

是否有办法在较低的N*N复杂度(例如合并所有1M数组/桶)中这样做？

Answer 1

我相信合并算法的下半部分就是你所要寻找的，因为前半部分是将数字分割成子区间，下半部分是合并这些子区间。Mergesort作为一个整体具有O(n log )的复杂性，我相信下半部分本身也将是O(n log )。

为了让您开始，这里有一个非常简短和可读的C ++合并实现，摘自http://www.cquestions.com/2011/07/merge-sort-program-in-c.html

#include<stdio.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main(){

    int merge[MAX],i,n;

    printf("Enter the total number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements which to be sort: ");
    for(i=0;i<n;i++){
         scanf("%d",&merge[i]);
    }

    partition(merge,0,n-1);

    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
         printf("%d ",merge[i]);
    }

   return 0;
}

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }

    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}

样本输出：

Enter the total number of elements: 5
Enter the elements which to be sort: 2 5 0 9 1
After merge sorting elements are: 0 1 2 5 9

请注意，棘轮怪胎的建议基本上是堆排序算法，这也是O(n log )，所以一个应该是好的。

Answer 2

您可以创建一个min堆，其中存储按第一个元素排序的所有桶。

然后，从第一个桶中弹出一个元素，并重新进行加热。

如果不允许更改桶，则保留每个桶的索引，其中的哪个元素仍然必须从其中弹出。

Answer 3

从您所写的文章中，我不知道为什么必须使用有关哈希表和桶的原始信息--它只是使事情变得过于复杂。

因此，将所有桶都压缩成一个列表(复杂性O(N))，并应用复杂度O(N * log(N))的任意排序算法，例如快速排序或合并排序。然后将结果写入文件中。