1. 冒泡排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 |
#include <stdio.h>#define LENGTH 8 void
main() { int
i, j, tmp, number[LENGTH] = {95, 45, 15, 78, 84, 51, 24, 12}; for
(i = 0; i < LENGTH; i++) { for
(j = LENGTH - 1; j > i; j--) { if
(number[j] < number[j-1]) { tmp = number[j-1]; number[j-1] = number[j]; number[j] = tmp; } } } for
(i = 0; i < LENGTH; i++) { printf("%d ", number[i]); } printf("\n");} |
2. 快速排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 |
#include <stdio.h>int a[] = { 1, 2, 8, 7, 9, 5, 6, 4, 3, 66, 77, 33, 22, 11 }; /* 输出数组前n各元素 */void
prt(int
n){ int
i; for
(i = 0; i < n; i++) { printf("%d\t", a[i]); } printf("\n");} void
quick_sort (int
data[], size_t
left, size_t
right) { size_t
p = (left + right) / 2; int
pivot = data[p]; size_t
i = left,j = right; for
( ; i < j;) { while
(! (i>= p || pivot < data[i])) ++i; if
(i < p) { data[p] = data[i]; p = i; } while
(! (j <= p || data[j] < pivot)) --j; if
(j > p) { data[p] = data[j]; p = j; } } data[p] = pivot; if
(p - left > 1) quickSort (data, left, p - 1); if
(right - p > 1) quickSort (data, p + 1, right);} int
main(void) { /* 排序与输出 */ quick_sort(a, 0, 13); prt(14); return
0;} |
3. 希尔排序
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 |
void
shellsort(int
*data, size_t
size){ for
(int gap = size / 2; gap > 0; gap /= 2) for
(int i = gap; i < size; ++i) { int
key = data[i]; int
j = 0; for( j = i -gap; j >= 0 && data[j] > key; j -=gap) { data[j+gap] = data[j]; } data[j+gap] = key; }} |
4. 基数排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73 |
#include<stdio.h>#define MAX 20#define SHOWPASS#define BASE 10 void
print(int
*a, int
n) { int
i; for
(i = 0; i < n; i++) { printf("%d\t", a[i]); }} void
radixsort(int
*a, int
n) { int
i, b[MAX], m = a[0], exp
= 1; for
(i = 1; i < n; i++) { if
(a[i] > m) { m = a[i]; } } while
(m / exp
> 0) { int
bucket[BASE] = { 0 }; for
(i = 0; i < n; i++) { bucket[(a[i] / exp) % BASE]++; } for
(i = 1; i < BASE; i++) { bucket[i] += bucket[i - 1]; } for
(i = n - 1; i >= 0; i--) { b[--bucket[(a[i] / exp) % BASE]] = a[i]; } for
(i = 0; i < n; i++) { a[i] = b[i]; } exp
*= BASE; #ifdef SHOWPASS printf("\nPASS : "); print(a, n);#endif }} int
main() { int
arr[MAX]; int
i, n; printf("Enter total elements (n <= %d) : ", MAX); scanf("%d", &n); n = n < MAX ? n : MAX; printf("Enter %d Elements : ", n); for
(i = 0; i < n; i++) { scanf("%d", &arr[i]); } printf("\nARRAY : "); print(&arr[0], n); radixsort(&arr[0], n); printf("\nSORTED : "); print(&arr[0], n); printf("\n"); return
0;} |
5. 堆排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71 |
#include <iostream>using
namespace std;/* #堆排序#% #数组实现#%*///#筛选算法#%void
sift(int
d[], int
ind, int
len){ //#置i为要筛选的节点#% int
i = ind; //#c中保存i节点的左孩子#% int
c = i * 2 + 1; //#+1的目的就是为了解决节点从0开始而他的左孩子一直为0的问题#% while(c < len)//#未筛选到叶子节点#% { //#如果要筛选的节点既有左孩子又有右孩子并且左孩子值小于右孩子#% //#从二者中选出较大的并记录#% if(c + 1 < len && d[c] < d[c + 1]) c++; //#如果要筛选的节点中的值大于左右孩子的较大者则退出#% if(d[i] > d[c]) break; else { //#交换#% int
t = d[c]; d[c] = d[i]; d[i] = t; // //#重置要筛选的节点和要筛选的左孩子#% i = c; c = 2 * i + 1; } } return;} void
heap_sort(int
d[], int
n){ //#初始化建堆, i从最后一个非叶子节点开始#% for(int
i = (n - 2) / 2; i >= 0; i--) sift(d, i, n); for(int
j = 0; j < n; j++) { //#交换#% int
t = d[0]; d[0] = d[n - j - 1]; d[n - j - 1] = t; //#筛选编号为0 #% sift(d, 0, n - j - 1); }} int
main(){ int
a[] = {3, 5, 3, 6, 4, 7, 5, 7, 4}; //#QQ#% heap_sort(a, sizeof(a) / sizeof(*a)); for(int
i = 0; i < sizeof(a) / sizeof(*a); i++) { cout << a[i] << ‘ ‘; } cout << endl; return
0;} |
原文：http://www.cnblogs.com/zhouzhuo/p/3632514.html