网上关于排序的讲解大片大片的，在这里只是想做个笔记，没有和大牛比肩的意思～
这节先讲几个比较简单的排序，先说冒泡吧，这个简直太简单了，见下面的程序：
1 #define LT(a, b) ((a) < (b) ? 1 : 0)
2
3 /*******************************
4 * 冒泡排序，每次依次比较相邻的两个元素，将最小的元素沉底
5 * 下次对剩余前N-1个元素相邻两个依次比较，再沉底
6 * 
7 * 时间复杂度0(n2)
8 ******************************/
9 void BubbleSort(int *a, int n)
10 {
11 int i, j;
12
13 for (i = 1; i < n; ++i)
14 {
15 for (j = 1; j < n - i; ++j)
16 {
17 if (!LT(a[j], a[j + 1]))
18 {
19 a[j] = a[j] ^ a[j + 1];
20 a[j + 1] = a[j] ^ a[j + 1];
21 a[j] = a[j] ^ a[j + 1];
22 }
23 }
24 }
25 }
注释已经解释的比较清楚了，每次比较j~n - i的所有元素中的两两相邻的元素，每次比较成功后都让最大的沉底，这样每次比较都让一个最大元素沉底，时间复杂度当然是O(n2)。
下面看一下插入排序，首先还是看一下最原始的插入排序
1 /********************************
2 * 插入排序，对于每一个元素，假定它之前的所有元素都是有序的，
3 * 则把这个元素插入到前面有序表中的某个位置，遍历数组，
4 * 且插入时也要遍历，时间复杂度O(n2)
5 *******************************/
6 void InsertSort(int *a, int n)
7 {
8 int i, j;
9
10 for (i = 2; i < n; ++i)
11 {
12 if (LT(a[i], a[i - 1]))
13 {
14 a[0] = a[i];
15 a[i] = a[i - 1];
16
17 for (j = i - 2; LT(a[0], a[j]); --j)
18 {
19 a[j + 1] = a[j];
20 }
21
22 a[j + 1] = a[0];
23 }
24 }
25 }
简单插入排序也比较直观，就是针对每个元素ai的时候，已经假定所有它前面的元素都排好序了，这样，对这个元素ai插入前面i-1个元素中去。
再来看看一个简单的修改，因为ai元素前面所有i-1个元素都是有序的，因此可以进行二分比较插入，这样就有了下面这个算法：
1 void BiInsertSort(int *a, int n)
2 {
3 int i, j, low, high, mid;
4
5 for (i = 2; i < n; ++i)
6 {
7 a[0] = a[i];
8 low = 1; high = i - 1;
9
10 while (low <= high)
11 {
12 mid = (low + high) >> 1;
13
14 if (LT(a[i], a[mid]))
15 {
16 high = mid - 1;
17 }
18 else
19 {
20 low = mid + 1;
21 }
22 }
23
24 for (j = i - 1; j >= high + 1; --j)
25 {
26 a[j + 1] = a[j];
27 }
28
29 a[high + 1] = a[0];
30 }
31 }
最后看看希尔排序，它不是对这个数组一次排序，而是把整个数组分成k组，k可以自己选定，然后对每个分组进行插入排序
关键是分组的策略，选定一个步长，假定为d[k]，则选定a[1], a[1 + k], a[1 + 2k]...的元素为一组，这个d[k]数组可以自己任意指定，但是最后一个一定要为1，而且尽量不要让相邻的两个比如d[i]和d[i + 1]成倍数关系。
1 void ShellSort(int *a, int n)
2 {
3 int increment = n;
4
5 do {
6 increment = increment / 3 + 1;
7 ShellPass(a, n, increment);
8 } while (increment > 1);
9 }
10
11 void ShellPass(int *a, int n, int d)
12 {
13 int i, j;
14
15 for (i = d + 1; i <= n; ++i)
16 {
17 if (LT(a[i], a[i - d]))
18 {
19 a[0] = a[i];
20
21 for (j = i - d; j > 0 && LT(a[0], a[j]); j -=d)
22 {
23 a[j + d] = a[j];
24 }
25
26 a[j + d] = a[0];
27 }
28 }
29 }
这几个算法平均时间复杂度都不是最优的，下节再写快排等几个比较优秀的排序。
posted on 2011-04-20 01:09
myjfm 阅读(277)
评论(0) 编辑 收藏 引用 所属分类:
杂