今天老大提出的一算法问题求解

+1

布隆过滤器排序不能对有重复值的进行排序

定义一个10W的整数数组，数组初始化都为0。然后遍历一般需要排序的整数数列，将每个元素在原本定义的整数数组中下标相同的数组元素+1。这样再次遍历整数数组时，根据数组的下标和数组本身的个数就知道排序的结果了。
BTW：这个跟我面试别人时出的试题好像啊。

基于比较的排序算法有个下界 O(nlog(n)) ，但是你要进行排序的元素比较特殊，全都是正整数，这样的话你可以试一下 Histogram Sort (Average case performance:O(n + k)) Histogram Sort是桶排序的一个变种
参考代码：

/*
 * Copyright (c) 2004 by Richard Harter.
 * This software may be freely used and modified without
 * restriction provided that this notice is preserved unaltered.
 *
 */

/*
 * This function sorts an array of integers in place using a math
 * sort based histogram sort.  2*len locations of auxilliary space
 * are used, where len is the data length.
 */
 
#include <stdlib.h>

#define MIN_SORTABLE_LENGTH 128
#define PROCESSED -1

int
int_msort(int * data, int len)
{
   int      data_min;               /* Minimum value in data array */
   int      data_max;               /* Maximum value in data array */
   int      index_min;              /* Index of minimum value      */
   int      i;                      /* Major loop index            */
   int      j;                      /* Minor loop index            */
   int      ifac;                   /* Integer scaling factor      */
   int      temp;                   /* Temp loc for data moves     */

   int      *space;                 /* Ptr to allocated space      */
   int      *cmp_index;             /* Ptr to computed indices     */
   int      *cum;                   /* Ptr to cumulative distrib.  */
   int      *hist;                  /* Ptr to cumulative distrib.  */
   int      *sorted;                /* Ptr to almost sorted data   */

   if (len <= 1) return 1;
   if (len == 2) {
      if (data[0] > data[1]) {
         temp = data[0];
         data[0] = data[1];
         data[1] = temp;
      }
      return 1;
   }
   data_min  = data[0];
   data_max  = data[0];
   index_min = 0;
   for (i=len; --i>0;) {
      if (data[i] < data_min) {
         data_min  = data[i];
         index_min = i;
      }
   }

   if (index_min != 0) {
      data[index_min] = data[0];
      data[0]         = data_min;
   }
   if (len >= MIN_SORTABLE_LENGTH) {
      for (i=len; --i>0;) {
         if (data[i] > data_max) data_max  = data[i];
      }

      /* Compute interpolation function */

      ifac = (data_max - data_min)/(len -1);
      if (ifac<=0) ifac=1;	  
      else while (((data_max-data_min)/ifac)>(len-1)) ifac++;

      /* allocate index and histogram space */

      space = malloc((2*len+1)*sizeof(int));
      if (!space) return 0;
      cmp_index = space;
      cum       = space + len;
      hist      = cum + 1;
      sorted    = hist;
      memset(cum,0,(len+1)*sizeof(int));

      /* Compute raw interpolation indices */

      for (i=len; --i>=0;) {
         hist[cmp_index[i] = (data[i] - data_min)/ifac] += 1;
      }
      for (i=1;i<len;i++) cum[i] += cum[i-1];  
      for (i=0;i<len;i++) cmp_index[i] = cum[cmp_index[i]]++;

      /* Math sort proper */

      for (i=len; --i >= 0;) sorted[cmp_index[i]] = data[i];
      memcpy(data, sorted, len*sizeof(int));
      free (space);
   }

   /* End of math sort section, begin insertion sort section */

   {
      for (i=1; i<len; i++) {
         if (data[i] >= data[i-1]) continue;
         temp = data[i];
         data[i] = data[i-1];
         for (j = i-2; temp < data[j]; j--) data[j+1] = data[j];
         data[j+1] = temp;
      }
   }
   return 1;
}

很明显，LZ说的是没有重复值的情况。
重复值也是有办法解决的，我在博客中也提到这个问题的，给出现两次和两次以上的记录加上个计数器就行了，只是会多占用点内存，当时我也这么实现过的，不过这样做的话，排序算法就是不稳定的算法，也就是说相等的记录排序前和排序后的顺序可能会改变。

100w的数组 进行计数排序   然后用紧凑算法  进行紧凑操作

基于比较的排序的极限是nlog(n)

桶排序，基数排序，计数排序 等等 都不是 nlog(n)

array[10w + 1], i放在array[i]，如果这里已经有数字了，那么array[i] += i
节省空间不知道怎么去节省

兄弟考你这个不是排序问题,是大数据量的处理问题!
10W的数组你觉得你的系统会稳定么?
这东西需要写磁盘的!

比较同意这个