網(wǎng)上關(guān)于排序的講解大片大片的，在這里只是想做個(gè)筆記，沒(méi)有和大牛比肩的意思～
這節(jié)先講幾個(gè)比較簡(jiǎn)單的排序，先說(shuō)冒泡吧，這個(gè)簡(jiǎn)直太簡(jiǎn)單了，見(jiàn)下面的程序：
1 #define LT(a, b) ((a) < (b) ? 1 : 0)
2
3 /*******************************
4 * 冒泡排序，每次依次比較相鄰的兩個(gè)元素，將最小的元素沉底
5 * 下次對(duì)剩余前N-1個(gè)元素相鄰兩個(gè)依次比較，再沉底
6 * 
7 * 時(shí)間復(fù)雜度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īng)解釋的比較清楚了，每次比較j~n - i的所有元素中的兩兩相鄰的元素，每次比較成功后都讓最大的沉底，這樣每次比較都讓一個(gè)最大元素沉底，時(shí)間復(fù)雜度當(dāng)然是O(n2)。
下面看一下插入排序，首先還是看一下最原始的插入排序
1 /********************************
2 * 插入排序，對(duì)于每一個(gè)元素，假定它之前的所有元素都是有序的，
3 * 則把這個(gè)元素插入到前面有序表中的某個(gè)位置，遍歷數(shù)組，
4 * 且插入時(shí)也要遍歷，時(shí)間復(fù)雜度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 }
簡(jiǎn)單插入排序也比較直觀，就是針對(duì)每個(gè)元素ai的時(shí)候，已經(jīng)假定所有它前面的元素都排好序了，這樣，對(duì)這個(gè)元素ai插入前面i-1個(gè)元素中去。
再來(lái)看看一個(gè)簡(jiǎn)單的修改，因?yàn)閍i元素前面所有i-1個(gè)元素都是有序的，因此可以進(jìn)行二分比較插入，這樣就有了下面這個(gè)算法：
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 }
最后看看希爾排序，它不是對(duì)這個(gè)數(shù)組一次排序，而是把整個(gè)數(shù)組分成k組，k可以自己選定，然后對(duì)每個(gè)分組進(jìn)行插入排序
關(guān)鍵是分組的策略，選定一個(gè)步長(zhǎng)，假定為d[k]，則選定a[1], a[1 + k], a[1 + 2k]...的元素為一組，這個(gè)d[k]數(shù)組可以自己任意指定，但是最后一個(gè)一定要為1，而且盡量不要讓相鄰的兩個(gè)比如d[i]和d[i + 1]成倍數(shù)關(guān)系。
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 }
這幾個(gè)算法平均時(shí)間復(fù)雜度都不是最優(yōu)的，下節(jié)再寫快排等幾個(gè)比較優(yōu)秀的排序。
posted on 2011-04-20 01:09
myjfm 閱讀(309)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
雜