快速排序算法、計數排序算法
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 閱讀(1895)
評論(2) 編輯 收藏 引用