今天开了博客园的博客,纪念一下。我是大二的学生,下半年就大三了,很快。这学期的数据库上的真是难受,不过数据结构这门课我很喜欢,学了C,练了些程序,上这课感觉轻松些,学了许多算法,都是牛人想出来的啊,第一个是高德纳的KMP,后来有哈夫曼,Prim,Kruskal,还有荷兰的那位计算机科学家,他的最短路径算法出的还挺晚的。站在巨人的肩膀上学个不停,挺爽,我总是在想,我能不能想出这些算法,像哈夫曼树,感觉道理挺简洁的啊,我还想过,如果把二分查找、哈夫曼树的算法跟我做农的父母亲讲,我想他们一定都能听懂大概的做法,是个人都会二分。上排序那章时,我总是在想,我一定要设计一个O(log(n!))的算法,因为人们在打牌时,就是那么插入的,我花了一个下午把我的想法写出来了,不幸的是,还是有不可避免的“移动元素“,失败。p.s.即使搞出来了,也是和快排一样的时间复杂度,可参见:http://blog.csdn.net/justme0/article/details/7584108。最后把我的想法贴出来吧:
1 // 哈希+静态链表+折半 2 #define _CRT_SECURE_NO_WARNINGS 3 #include <iostream> 4 using namespace std; 5 6 #define LEN 9 7 8 struct Node { 9 int data; 10 int next; 11 }; 12 13 int main(void) 14 { 15 freopen("cin.txt", "r", stdin); 16 Node arr[LEN]; 17 arr[0].data = 0; 18 arr[0].next = 1; 19 for (int i = 1; i < LEN; ++i) { 20 cin >> arr[i].data; 21 arr[i].next = 0; 22 } 23 int h[LEN] = {0}; 24 25 for (int i = 1; i < LEN; ++i) { 26 arr[0].data = arr[i].data; // 将arr[i]暂存到arr[0] 27 int low = 1; 28 int high = i - 1; 29 while (low <= high) { // 在r[low..high]中折半查找有序插入的位置 30 int m = (low + high) / 2; // 折半 31 if (arr[0].data < arr[h[m]].data) 32 high = m - 1; // 插入点在低半区 33 else 34 low = m + 1; // 插入点在高半区 35 } 36 if (low != high + 1) 37 cout << "Error!" << endl; 38 39 arr[i].next = arr[h[high]].next; 40 arr[h[high]].next = i; 41 42 for (int j = i; j > high + 1; j--) // failed 43 h[j] = h[j - 1]; 44 h[high + 1] = i; 45 } 46 47 for (int i = 1; i < LEN; i++) 48 cout << arr[h[i]].data << endl; 49 50 return 0; 51 } 52 53 /* 54 cin.txt 55 49 56 38 57 65 58 97 59 76 60 13 61 27 62 49 63 */
要去吃饭了,IT民工伤不起啊。。。话说今天搞了一天的百度之星题目,生物钟紊乱了,唉o(︶︿︶)o ==!