写了个快速排序算法……

elulis

写了个快速排序算法…… [复制链接]

写了个排序算法，思路是归并排序+冒泡排序（n=2即交换排序），

时间复杂度稳定为O(n*log2(n))，几乎是稳定排序算法中最快的，特别是在大数据量的情况下更明显（对比冒泡排序O(n*(n-1))）。缺点，需要一个buf，用空间换时间……

使用时注意适当修改buf的大小，一定要大于等于（>=）排序的数组长度。如果处理的是char类型数组记得该类型。

在Launchpad + G2553@1MHz下排序一个64长度随机数组，每秒50次左右，对比冒泡排序大约在每秒15次左右。

1. volatile unsigned int buf[64];
   volatile unsigned int i, j, t;
   void sort(volatile unsigned int *data, unsigned int from, unsigned int to){
       unsigned int mid;
       if(to - from > 2){
           // merge sort
           mid = (to + from) >> 1;
           sort(data, from, mid);
           sort(data, mid, to);
           i = from;
           j = mid;
           t = 0;
           while((i < mid) && (j < to)){
               if( *(data+i) < *(data+j) ){
                   buf[t++] = *(data+(i ++));
               }else{
                   buf[t++] = *(data+(j ++));
               }
           }
           while(i < mid){
               buf[t++] = *(data+(i ++));
           }
           while(j < to){
               buf[t++] = *(data+(j ++));
           }
           for(t = from; t < to; t ++){
               *(data+t) = buf[t-from];
           }
       }else if(to - from == 2){
           // bubble sort
           if(*(data + from) > *(data + to - 1)){
               t = *(data + from);
               *(data + from) = *(data + to - 1);
               *(data + to - 1) = t;
           }
       }
   }

复制代码

之所以i,j,t,buf作为全局变量，是因为他们不需要堆栈保护，但是局部变量mid移出来就挂了……

好吧，在做红外接收发射（电视空调都学习到一个设备上），空调的编码真长啊，必须要做压缩处理，霍夫曼树压缩要先排序

[ 本帖最后由 elulis 于 2012-7-16 02:00 编辑 ]

elulis

从时间复杂度可以算出理论上归并排序要比冒泡快10.5倍（n=64；64 / log2(64)  = 10.5），刚才用定时器得到归并排序需要368/32768秒，冒泡排序需要3223/32768秒，相差8.75倍，和理论数字有点接近

[ 本帖最后由 elulis 于 2012-7-16 02:19 编辑 ]

fish001

谢谢分享。

huo_hu

一定要先排序。。。不理解，对编码排序了怎么恢复呢？
空调编码是很长，不过不至于耗尽内存吧

elulis

排序之前统计频率，然后给高频的分配短的编码。统计频率需要排序……

huo_hu

统计频率需要排序?
计数就行了啊

zxdong

不错，看来楼主的数据结构和算法学的不错啊···

elulis

过奖，靠这个吃饭的……

huo_hu

路子不正。。。。
空调遥控编码有个特点就是一次发送包含所有控制信号，理解这一点就好分解编码了。
用程序分解是有难度的。