快速排序算法、计数排序算法
C++博客 Alex-Lee 2009-10-20
快速排序是分治算法，将数组分为几部分，在各部分内完成排序，递归排序。算法时间复杂度O(nlgn)。这是比较排序算法中速度最快的一个算法了。计数排序、基数排序、桶排序算法是非比较排序算法，他们的算法复杂度是O(n)。快速排序算法在选取支点上要有技巧，最好能达到随即要求。
1，快速排序算法：
普通快速排序
1
typedef 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秒。
排序算法代码
posted on 2009-10-20 22:18
Alex-Lee 阅读(1884)
评论(2) 编辑 收藏 引用