当前位置: 首页 > >

快速排序算法、计数排序算法

发布时间:

快速排序是分治算法,将数组分为几部分,在各部分内完成排序,递归排序。算法时间复杂度O(nlgn)。这是比较排序算法中速度最快的一个算法了。计数排序、基数排序、桶排序算法是非比较排序算法,他们的算法复杂度是O(n)。快速排序算法在选取支点上要有技巧,最好能达到随即要求。
1,快速排序算法:
普通快速排序
?1typedef struct int_array
?2{
?3??? int *pa;//数组,对于任意类型的数据,可以使用char *pc,int typelen实现。
?4??? int array_size;//数组元素数量
?5??? int capacity;//缓存大小
?6} INT_ARRAY;//有点类似于vector
?7
?8
?9int partition(INT_ARRAY *pia,int p,int r)
10{
11??? int x,i,j;
12??? x = pia->pa[p];
13??? i = p -1;
14??? j = r + 1;
15??? while (1)
16??? {
17??????? --j;
18??????? while(pia->pa[j] > x && j-- >= p)
19??????????? ;
20??????? ++i;
21??????? while(pia->pa[i] < x && i++ <= r)
22??????????? ;
23
24??????? if (i < j)
25??????? {
26??????????? swap(&pia->pa[i],&pia->pa[j]);
27??????? }
28??????? else
29??????? {
30??????????? return j;
31??????? }
32??? }
33}
34
35void quick_sort(INT_ARRAY *pia,int p,int r)
36{
37??? int q;
38??? if(p < r)
39??? {
40??????? q = partition(pia,p,r);
41??????? quick_sort(pia,p,q);
42??????? //p = q +1;
43??????? quick_sort(pia,q+1,r);
44??? }
45}
2,改进版本的快速排序(随机分布版本的快速排序)
随机分布快速排序
?1int random_partition(INT_ARRAY *pia,int p,int r)
?2{
?3??? int i = (mrand() %(r-p +1)) + p;
?4??? swap(&pia->pa[i],&pia->pa[p]);
?5??? return partition(pia,p,r);
?6}
?7void random_quick_sort(INT_ARRAY *pia,int p,int r)
?8{
?9??? int q;
10??? if (p < r)
11??? {
12??????? q = random_partition(pia,p,r);
13??????? random_quick_sort(pia,p,q);
14??????? random_quick_sort(pia,q + 1,r);
15??? }
16}
3,计数排序算法
?? 计数排序算法是需要知道数组元素的上下限,并且最好是对整数元素排序,计数每个元素的个数,需要占用比较多的空间。
计数排序
?1void counting_sort(INT_ARRAY *pia, int max)
?2{
?3??? int i,c;
?4??? int *pb,*pc;
?5???
?6??? //malloc 最多UNIT_MAX字节,因此c 最多到UINT_MAX/sizeof(int) ;
?7??? pb = (int*)malloc(sizeof(int) * pia->array_size);
?8??? if (!pb)
?9??? {
10??????? return;
11??? }
12??? c = max + 1;
13??? pc = (int*)malloc(sizeof(int)*c);
14??? if (!pc)
15??? {
16??????? free(pb);
17??????? return;
18??? }
19??? memset((char*)pb,0xCC,sizeof(int)*pia->array_size);
20??? memset((char*)pc,0xCC,sizeof(int)*c);
21??? for (i = 0; i < pia->array_size; ++i)
22??? {
23??????? pb[i] = pia->pa[i];
24??? }
25??? for (i = 0 ; i < c ; ++i)
26??? {
27??????? pc[i] = 0;
28??? }
29??? for (i = 0; i < pia->array_size; ++i)
30??? {
31??????? pc[pb[i]] ++;
32??? }
33??? for (i = 1; i < c; ++i)
34??? {
35??????? pc[i] += pc[i-1];
36??? }
37??? for (i = pia->array_size - 1; i >= 0; --i)
38??? {
39??????? pia->pa[pc[pb[i]] -1] = pb[i];
40??????? pc[pb[i]] --;
41??? }
42??? free(pb);
43??? free(pc);
44}4,测试代码
?? 在测试整数时,1kw整数,快速排序5秒,堆排序20秒,计数排序是0.43秒。



友情链接: