排序算法
排序算法
算法导论中对排序问题的描述
输入 ：n个数的序列<a 1 ,a 2 ,...,a n >。
输出 ：输入序列的一个重排<a' 1 ,a' 2 ,...a' n >，使a' 1 <=a' 2 <=...<=a' n。
（首先声明下，下面的代码中伪代码是算法导论上抄的，c代码是自己写的。所以c语言的代码如果有问题请指教。）
1.插入排序
伪代码：
1 INSERSION- SORT(A) 2 for j <- 2 to length[A] 3 do key <- A[j] 4 i <- j- 1 5 while i> 0 and A[i]> key 6 do A[i+ 1 ] <- A[i] 7 i <- i- 1 8 A[i+ 1 ] <- key
c实现
1 void InsertionSort( int A[], int n)
2 {
3 int key;
4 int i,j;
5 for (i= 1 ;i<n;i++ )
6 {
7 key = A[i];
8 j = i- 1 ;
9 while (key >= A[j] && j>= 0 )
10 {
11 A[j+ 1 ] = A[j];
12 j-- ;
13 }
14 A[j+ 1 ] = key;
15 }
16 }
2.冒泡排序
伪代码：
BUBBLESORT(A)
for i <- 1 to length[A]
do for j <- length[A] downto i+ 1
do if A[j]<A[j- 1 ]
then exchange A[j] <-> A[j- 1 ]
c实现：
1 void BubbleSort( int A[], int n)
2 {
3 int i,j;
4 int tmp;
5 for (i= 0 ;i<n;i++ )
6 {
7 for (j = n- 1 ;j>=i+ 1 ;j-- )
8 {
9 if (A[j]>A[j- 1 ])
10 {
11 tmp = A[j];
12 A[j] = A[j- 1 ];
13 A[j- 1 ] = tmp;
14 }
15 }
16 }
17 }
在冒泡排序中如果做一个判断，在一趟起泡的过程中如果没有任何一次交换就终止循环。这样可以节省一些时间的开销。
3.归并排序
1 MERGE(A,p,q,r) 2 n1 <- q-p+ 1 3 n2 <- r- q 4 creat arrays L[ 1 ...n1+ 1 ]andR[ 1 ...n2+ 1 ] 5 for i <- 1 to n1 6 do L[i] <- A[p+i- 1 ] 7 for j <- 1 to n2 8 do R[j] <- A[p+ j] 9 L[n1+ 1 ] <- ∞ 10 R[n2+ 1 ] <- ∞ 11 i <- 1 12 j <- 1 13 for k <- p to r 14 do if L[i]<= R[j] 15 then A[k] <- L[i] 16 i <- i+ 1 17 else A[k] <- R[j] 18 j <- j+ 1 19 20 MERGE- SORT(A,p,r) 21 if p< r 22 then q <- └(p+q)/ 2 ┘ 23 MERGE- SORT(A,p,q) 24 MERGE-SORT(A,q+ 1 ,r) 25 MERGE(A,p,q,r)
c实现：
1 void Merge( int A[], int p, int q, int r)
2 {
3 int n1,n2;
4 n1 = q-p+ 1 ;
5 n2 = r- q;
6 int *L = ( int *)malloc( sizeof ( int )*(n1+ 1 ));
7 int *R = ( int *)malloc( sizeof ( int )*(n2+ 1 ));
8 int i,j;
9 for (i= 0 ;i<n1;i++ )
10 {
11 L[i] = A[p+ i];
12 }
13 for (j= 0 ;j<n2;j++ )
14 {
15 R[j] = A[q+j+ 1 ];
16 }
17 L[n1] = INT_MAX;
18 R[n2] = INT_MAX;
19 i = 0 ;
20 j = 0 ;
21 int k;
22 for (k=p;k<=r;k++ )
23 {
24 if (L[i]<= R[j])
25 {
26 A[k] = L[i];
27 i++ ;
28 }
29 else
30 {
31 A[k] = R[j];
32 j++ ;
33 }
34 }
35 free(L);
36 free(R);
37 }
38 void MergeSort( int A[], int p, int r)
39 {
40 int q;
41 if (p< r)
42 {
43 q = p + (r-p)/ 2 ;
44 MergeSort(A,p,q);
45 MergeSort(A,q+ 1 ,r);
46 Merge(A,p,q,r);
47 }
48 }
4.堆排序
伪代码：
1 PARENT(i) 2 return i* 2 3 LEFT(i) 4 return 2i 5 RIGHT(i) 6 return 2 *i+ 1 7 MAX- HEAPIFY(A,i) 8 l <- LEFT(i) 9 r <- RIGHT(i) 10 if l<=heap-size[A] and A[l]> A[i] 11 then largest <- l; 12 else largest <- i; 13 if r<=heap-size(A) and A[r]> A[largest] 14 then largest <- r 15 if largest != i 16 then exchange A[i] <-> A[largest] 17 MAX- HEAPIFY(A,largest) 18 BUILD-MAX- HEAP(A) 19 heap-size[A] = length[A] 20 for i <- └length[A]/ 2 ┘ downto 1 21 do MAX- HEAPIFY(A,i) 22 HEAP- SORT(A) 23 BUILD-MAX- HEAP(A) 24 for i <-length[A] downto 2 25 do exchange A[ 1 ] <-> A[i] 26 heap-size[A] <- heap-size[A]- 1 27 MAX-HEAPIFY(A, 1 )
c实现：
1 #define PARENT(i)(((i)-1)/2)
2 #define LEFT(i)(2*((i)+1)-1)
3 #define RIGHT(i)(2*((i)+1))
4 void MaxHeapify( int A[], int i, int size)
5 {
6 int l = LEFT(i);
7 int r = RIGHT(i);
8 int largest = i;
9 int tmp;
10 if (l<size && A[i]< A[l])
11 {
12 largest = l;
13 }
14 if (r<size && A[r]> A[largest])
15 {
16 largest = r;
17 }
18 if (largest != i)
19 {
20 tmp = A[i];
21 A[i] = A[largest];
22 A[largest] = tmp;
23 MaxHeapify(A,largest,size);
24 }
25 }
26 void BuildMaxHeap( int A[], int size)
27 {
28 int i;
29 for (i=size/ 2 ;i>= 0 ;i-- )
30 {
31 MaxHeapify(A,i,size);
32 }
33 }
34 void HeapSort( int A[], int size)
35 {
36 BuildMaxHeap(A,size);
37 int i;
38 int j;
39 int tmp;
40 for (i=size- 1 ;i> 0 ;i-- )
41 {
42 tmp = A[i];
43 A[i] = A[ 0 ];
44 A[ 0 ] = tmp;
45 MaxHeapify(A, 0 ,i);
46 }
47 }
5.基数加桶排序 （用了两个桶，分别装0，1）
基数排序伪代码：
1 RADIX- SORT(A,D) 2 for i <- 1 to d 3 do use a stable sort to sort array A on digit i
桶排序伪代码：
1 BUCKET- SORT(A) 2 n <- length[A] 3 for i <- 1 to n 4 do insert A[i] into list B[└nA[i]┘] 5 for i <- 0 to n- 1 6 do sort list B[i] with insertion sort 7 concatenate the lists B[ 0 ],B[ 1 ],...,B[n- 1 ] together in order
c实现
1 #define GET(X,N)(((X>>(N-1))&0x1))/*获取第n bit*/
2 void RadixBucketSort( int A[], int n)
3 {
4 int * Bucket = malloc( sizeof ( int )*n); /* 一个数组当两个桶用的 */
5 int i,j,z,num,pos1,pos2;
6 for (num= 1 ;num< 32 ;num++ )
7 {
8 i = 0 ;
9 j=n- 1 ;
10 for (z= 0 ;z<n;z++ )
11 {
12 if (GET(A[z],num)== 1 )
13 {
14 Bucket[i]= A[z];
15 i++ ;
16 }
17 else
18 {
19 Bucket[j]= A[z];
20 j-- ;
21 }
22 }
23 pos1 = 0 ;
24 pos2 = n- 1 ;
25 for (z= 0 ;z<n;z++ )
26 {
27 if ( pos1!= i )
28 {
29 A[z]= Bucket[pos1];
30 pos1++ ;
31 }
32 else
33 {
34 A[z]= Bucket[pos2];
35 pos2-- ;
36 }
37 }
38
39 }
40 free(Bucket);
41 }
上面的算法中，算是基数排序加桶排序吧。我把一个数字从低到高每一个二进制位作为基数排序中的每一趟。也就是说我把一个int类型分成31个位。而每个二进制位只有1或0两种可能。所以将数据放入两个桶中时就自然的排好了序。所以我认为自己用了桶排序，呵呵。因为以上的原因，所以算法中只能对正数进行处理。如果要对负数或其他类型的数据进行排序的话，就要重新改进算法了。所以这些算法是有适用范围的。但比起比较排序，这些排序算法确实要快些。在数量很大的时候经过测试确实上面的算法比快排要快，呵呵。
分类: algorithm
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did47170