不改变原数组，也不借助于另一个数组，只对数组的下标进行排序。

我的当前工作是单片机开发，在项目实践中需要对采集的数据进行处理，数据长度达到了4个字节32位。对于单片机来说若申请15*4个字节的内容空间还能够承受。但是，我所处理的这15个32位的数据来说不可以修改，但又对它排序。起初解决的办法是另外再开辟一15个32位的数据。这样一来15*4*2=120个字节，加上整个操作中还定义了多个这样的变量以及浮点型变量，对数据采集的频率也是有要求的，这样的32位复制移位排序效率实在是底，对于51已完全没办法接受。对于52也只能勉强。为此就产生了能不能省掉这另外开辟的15个变量，并起到不改变原数据下进行排序。

起初的想法就是对这15个数组进行下标的排序。对下标的索引也就知道了原数的顺序。

对于排序来说大家都很熟悉，但是书上不管哪个排序都将是改变原数据的。如何不改变数据下排序呢，有点困难了，因为不改变原数据的位置，也因此不确定哪些数我排序过了，哪些我没排序过，

下面是我在VC中测试的程序，其中FilterArray1为我要处理的15个数据。Posit是我要存入的数组下标。在数据小于256个时，它只需要定义成8位的。

我们在排序时需要判断我正在排序的这个数有没有被排序过，在此过程中我只需要查询Posit中有没有该数据的下标，如果有则说明此数据被排序过。但此时还不够，困为数组的排序次数是固定的，我们还要在数组中找一个没有被排序过的数组进行排序。

那么整个排序思想和正常排序是一样的，只是多了判断，判断此数是否被排序过，排序过再找到一个未排序的数据进行排序。代码好下：

        #include 

        #include 

        #include 

        #include 

         int Posit[15]; //记录数组从小到大值的下标 可以定义成unsigned char型

        int FilterArray1[15]; //已乱的数据 

         //检查已经比较过的下标。因为原值无法移动或修改。

        int test_use(int TestBit) 

        { int i; 

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

         if(Posit[i]==TestBit)return 1; //如果Posit中有所要测试的下标则返回1 

         return 0; //否则返回0 

        } 

        

         //返回最小(最近)没有记录过的下标值 

        int test_nouse(void)

         { 

         int i,j;

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

         {

                for(j=0;j<15;j++) 

                 {

                         if(i==Posit[j])break; //将Posit中的值逐一和i比较，如果没有找到则返回i

                 }  

                 if(j==15)return i;//即在Posit中找不到i时将i返回。 

          } 

                 return 0xff; 

        } 

         void sub_sort(void) 

        { int i,j,temp,l; for(i=0;i<15;i++)Posit[i]=255; //初使化，使其值大于要比较的个数                          for(i=0;i<15;i++) 

                 {

                         if(test_use(i))

                        {temp=FilterArray1[l=test_nouse()];} //测试如果当前的数据已被记录在了Posi

                         else 

                        {temp=FilterArray1[i];l=i;} //否则取值,l用来记录当前所选的元素下标。 

                         for(j=0;j<15;j++) 

                         { if(test_use(j))continue; //如果此值已出现在了Posi中，则跳过                 if(temp>=FilterArray1[j]){Posit[i]=j;temp=FilterArray1[j];}//比较

                         } 

                 } 

         } 

         int main(void) 

        { int i; srand((unsigned)time(NULL)); 

printf("博客：浪迹神淘 Youner\r\n\n");

         for(i=0;i<15;i++) //随机获得15个数 

         {          FilterArray1[i]=rand(); 

                 printf("%d\t %d\n",i,FilterArray1[i]); 

         }

         puts("\n"); 

         sub_sort(); //对下标进行排序 

         for(i=0;i<15;i++)printf("%d ",Posit[i]); //输出排序好的下标 

        puts("\n");                            

        for(i=0;i<15;i++)printf("%d ",FilterArray1[Posit[i]]); 

         puts("\n");

         return 0; 

}

请猜为什么将Posit全部清除成0XFF。当然你也可以清除成15以上的数。

http://s8/mw690/79fbacedgdbedf0845f37&690

结果如上图。这样原数据的值不会被改变，但是最终顺序我们是可以知道的，但是你看懂为什么要在数据中判断排序过的数和找出最近未排序过的数么。如果判断又会如何呢？

这样的代码看上去内存是减少了不少，在我写的项目中Posit定义成了8位，这样15*4+15=75个字节，少了45个字节的RAM，对于51的128个字节来说简直是如鱼得水啊。

可这样的代码效率怎么样？对于8位控制器来说它比之前复制一份排序效率也高了。至少它移动的只是Posit的8位数据。

不过这样的代码看上去又臭又长。请看以下代码：

它比排序效率更高，没有任何移位操作，只是简单的判断。

节省内存和之前一样，但它的速度远远超过了前面的程序并且它也超过了借用其它数据进行排序。

如果有不明白的可以留言。