快速排序的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 快速排序是一种不稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 该方法的基本思想是: 1.先从数列中取出一个数作为基准数。 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。 3.再对左右区间重复第二步,直到各区间只有一个数。 以一个数组作为示例,取区间第一个数为基准数。
初始时,i = 0; 由于已经将a[0]中的数保存到X中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。 从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8];i++; 数组变为:
再重复上面的步骤,先从后向前找,再从前向后找。 从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++; 从i开始向后找,当i=5时,由于i==j退出。 此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。 数组变为:
可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。 对挖坑填数进行总结 1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。 2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。 3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。 4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。 使用递归调用实现的qsort(). void myQSort(int a[], int l, int r){ if(l<r) { int i=l, j=r, x=a[l]; while(i<j) { while(i<j && a[j]>=x) j--; if(i<j) a[i++] = a[j]; while(i<j && a[i]<x) i++; if(i<j) a[j--] = a[i]; } a[i] = x; myQSort(a, l, i-1); myQSort(a, i+1, r); } } 鉴于以上实现需要多次递归调用, 而在嵌入式环境中, 函数调用栈的尺寸有限, 故还需要用栈来替换递归; 同样由于内存空间有限, 首先需要实现可循环使用的固定空间的队列; //An implement of FIFO queue with finite memory space. // by QuakeZh <2014.12.15> struct myFiniteQueue_t { void *pbuf; //pointer to ext-memory buffer. unsigned short cap; //total memory capacity in Bytes. unsigned short usz; //unit size in Bytes. unsigned short ucap; //total unit counts of the queue. unsigned short top; //position of pop-out. unsigned short tail; //postion of the next-push-in. unsigned short cnt; //unit counts in queue. }; typedef struct myFiniteQueue_t MyFiniQue; MyFiniQue *finiq_Init(MyFiniQue *pFiniq, void *pGlobalMem, unsigned short cap, unsigned short uSize) { pFiniq->pbuf = pGlobalMem; pFiniq->cap = cap; pFiniq->usz = uSize; pFiniq->ucap = cap / uSize; pFiniq->top = pFiniq->tail = 0; pFiniq->cnt = 0; return pFiniq; } unsigned char finiq_IsEmpty(MyFiniQue *pFiniq) { return pFiniq->cnt==0 ? 1 : 0; } void finiq_Empty(MyFiniQue *pFiniq) { pFiniq->top = pFiniq->tail = 0; pFiniq->cnt = 0; } /**push into queue*/ void *finiq_Push(MyFiniQue *pFiniq, void *pDat) { if(pFiniq->cnt < pFiniq->ucap) { memcpy(pFiniq->pbuf+pFiniq->tail*pFiniq->usz, pDat, pFiniq->usz); pFiniq->tail = ++pFiniq->tail % pFiniq->ucap; pFiniq->cnt++; return pDat; } return 0; //queue is overflowed. } /**pop from queue*/ void *finiq_Pop(MyFiniQue *pFiniq) { void *p = 0; if(pFiniq->cnt > 0) { p = pFiniq->pbuf + pFiniq->top * pFiniq->usz; pFiniq->top = ++pFiniq->top % pFiniq->ucap; pFiniq->cnt--; } return p; } /**return the top unit of the queue (not popping)*/ void *finiq_Top(MyFiniQue *pFiniq) { if(pFiniq->cnt > 0) { return pFiniq->pbuf + pFiniq->top * pFiniq->usz; } return 0; } 再来一组针对int类型的特例. MyFiniQue *fqInt_Init(MyFiniQue *pFiniq, void *pGlobalMem, unsigned short cap) { pFiniq->pbuf = pGlobalMem; pFiniq->cap = cap; pFiniq->usz = sizeof(int); pFiniq->ucap = cap / sizeof(int); pFiniq->top = pFiniq->tail = 0; pFiniq->cnt = 0; return pFiniq; } /**push into queue*/ void fqInt_Push(MyFiniQue *pFiniq, int n) { if(pFiniq->cnt < pFiniq->ucap) { memcpy(pFiniq->pbuf+pFiniq->tail*pFiniq->usz, &n, pFiniq->usz); pFiniq->tail = ++pFiniq->tail % pFiniq->ucap; pFiniq->cnt++; } } /**pop from queue*/ int fqInt_Pop(MyFiniQue *pFiniq) { if(pFiniq->cnt > 0) { void *p = pFiniq->pbuf + pFiniq->top * pFiniq->usz; pFiniq->top = ++pFiniq->top % pFiniq->ucap; pFiniq->cnt--; return *((int *)p); } return 0; } int fqInt_Top(MyFiniQue *pFiniq) { if(pFiniq->cnt > 0) { void *p = pFiniq->pbuf + pFiniq->top * pFiniq->usz; return *((int *)p); } return 0; } 现在可以实现基于栈(队列)的qsort了. static void myQSort_it(int a[], int l, int r, MyFiniQue *pfq) { if(l<r) { int i=l, j=r, x=a[l]; while(i<j) { while(i<j && a[j]>=x) j--; if(i<j) a[i++] = a[j]; while(i<j && a[i]<x) i++; if(i<j) a[j--] = a[i]; } a[i] = x; fqInt_Push(pfq, l); fqInt_Push(pfq, i-1); fqInt_Push(pfq, i+1); fqInt_Push(pfq, r); } } /**QSort implements for the integer array. * @param a Integer array to be sorted; * @param sz Counts of integers in array; * @param pbuf Ext-memory buffer will be used while sorting; * @param cap Capacity of ext-memory buffer (in Bytes); */ void myQSort(int a[], int sz, void *pbuf, int cap) { int lf, rt; MyFiniQue fq; fqInt_Init(&fq, pbuf, cap); myQSort_it(a, 0, sz-1, &fq); while(!finiq_IsEmpty(&fq)) { lf = fqInt_Pop(&fq); rt = fqInt_Pop(&fq); myQSort_it(a, lf, rt, &fq); lf = fqInt_Pop(&fq); rt = fqInt_Pop(&fq); myQSort_it(a, lf, rt, &fq); } } 测试一下: int main(int argc, char** argv) { int ps[] = {342,105,258,51,876,705,1452,150,32,657,918,414,189,64,536,131,870,426,99,155,202,798}; int nlen = sizeof(ps)/sizeof(int); int lf, rt; //qsort(ps, nlen, sizeof(int), myComp); myQSort(ps, nlen, (void *)__Buf, sizeof(__Buf)); for(int i=0; i<nlen; i++) printf("%d < ", ps[i]); printf("\nOver(%d)\n", nlen); return 0; } |
|