網上關于排序的講解大片大片的，在這里只是想做個筆記，沒有和大牛比肩的意思～
這節先講幾個比較簡單的排序，先說冒泡吧，這個簡直太簡單了，見下面的程序：
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 閱讀(304)
評論(0) 編輯 收藏 引用 所屬分類:
雜