ChenGen

一切归零,重新开始
随笔 - 13, 文章 - 10, 评论 - 21, 引用 - 0
数据加载中……

复习排序算法

   学院的保送研究生复试马上就要开始了,复试中最能拉开距离的就是笔试,这也是我发挥个人能力的地方。为了万无一失,我准备这几天复习一下数据结构,今天复习的内容是排序算法。

   一般的排序算法大体上分为三类——插入排序、交换排序和选择排序。

   插入排序的基本思想是将第N个记录插入到前面(N-1)个有序的记录当中。直接插入排序、折半插入排序和系尔排序都是属于插入排序。

   直接插入排序:

 1 void  InsertSort(RcdType r[], int  n)
 2 {
 3      int  i,j;
 4      for (i = 2 ;i <= n;i ++ ) {
 5         r[ 0 ] = r[i];
 6         j = i - 1 ;
 7          while (r[ 0 ].key < r[j].key) {
 8             r[j + 1 ] = r[j];
 9             j -- ;
10         }

11         r[j + 1 ] = r[ 0 ];
12     }
    
13 }

   折半插入排序:

 1 void  BinSort(RcdType r[], int  n)
 2 {
 3      int  i,j,mid,low,high;
 4      for (i = 2 ;i <= n;i ++ ) {
 5         r[ 0 ] = r[i];
 6         low = 1 ;
 7         high = i - 1 ;
 8          while (low <= high) {
 9             mid = (low + high) / 2 ;
10              if (r[ 0 ].key < r[mid].key) high = mid - 1 ;
11              else  low = mid + 1 ;
12         }

13          for (j = i - 1 ;j >= low;j --
14             r[j + 1 ] = r[j];
15         r[low] = r[ 0 ];
16     }

17 }

   交换排序算法的基本思想是按照某种顺序比较两个记录的关键字大小,然后根据需要交换两个记录的位置。冒泡排序和快速排序都是属于交换排序。

   冒泡排序:

 1 void  BubbleSort(RcdType r[], int  n)
 2 {
 3      int  i,j,flag;
 4      for (i = 1 ;i < n;i ++ ) {
 5         flag = 1 ;
 6          for (j = 1 ;j <= n - i;j ++ ) {
 7              if (r[j + 1 ].key < r[j].key) {
 8                 falg = 0 ;
 9                 r[ 0 ] = r[j];
10                 r[j] = r[j + 1 ];
11                 r[j + 1 ] = r[ 0 ];
12             }

13         }

14          if (flag)  break ;
15     }

16 }

   快速排序:

 1 void  QuickSort(RcdType r[], int  low, int  high)
 2 {
 3      int  i,j;
 4     i = low;
 5     j = high;
 6     r[ 0 ] = r[i];
 7      while (i < j) {
 8          while (i < &&  r[j].key >= r[ 0 ].key) j -- ;
 9          if (i < j) r[i ++ ] = r[j];
10          while (i < &&  r[i].key <= r[ 0 ].key) i ++ ;
11          if (i < j) r[j -- ] = r[ 0 ];
12     }

13     r[i] = r[ 0 ];
14      if (low < i - 1 ) QuickSort(r,low,i - 1 );
15      if (high > i + 1 ) QuickSort(r,i + 1 ,high);
16 }

   选择排序算法的思想是根据某中方法选择一个关键字最大的记录或者关键字最小的记录,放到适当的位置。简单选择排序和堆排序都是属于选择排序算法。

   简单选择排序:

 1 void  SelectSort(RcdType r[], int  n)
 2 {
 3      int  i,j,p;
 4      for (i = 1 ;i < n;i ++ ) {
 5         p = i;
 6          for (j = i + 1 ;j <= n;j ++ ) {
 7              if (r[j].key < r[p].key) p = j;
 8         }

 9          if (p != i) {
10             r[ 0 ] = r[p];
11             r[p] = r[i];
12             r[i] = r[ 0 ];
13         }

14     }

15 }

   堆排序:

 1 void  Heap(RcdType r[], int  i, int  m)
 2 {
 3      int  j;
 4     j = 2 * i;
 5     r[ 0 ] = r[i];
 6      while (j <= m) {
 7          if (j < &&  r[j + 1 ].key < r[j].key) j ++ ;
 8          if (r[j].key < r[ 0 ].key) {
 9             r[i] = r[j];
10             i = j;
11             j = i * 2 ;
12         }
else {
13             j = m + 1 ;
14         }

15     }

16     r[i] = r[ 0 ];
17 }

18
19 void  HeapSort(RcdType r[], int  n)
20 {
21      int  i,j;
22      // 初始化堆
23      for (i = n / 2 ;i >= 1 ;i -- ) {
24         Heap(r,i,n);
25     }

26      // 输出
27      for (i = n;i >= 1 ;i -- ) {
28         printf( " %d\t " ,r[ 1 ].key);
29         r[ 1 ] = r[i];
30         Heap(r, 1 ,i - 1 );
31     }

32 }



 

posted on 2006-09-25 16:01 ChenGen 阅读(1375) 评论(5)  编辑  收藏 所属分类: 数据结构复习

评论

# re: 复习排序算法  回复  更多评论   

给blogjava提一个建议:

发到首页的文章做如下限制:
1. 如果blog主已经在blogjava攒了几篇文章,而且写得还不错,如“江南白衣”之流,可以直接发到首页上。
2. 否则,管理员先大概的审核一下。

大家觉得?
2006-09-25 16:13 | 深蓝色心情

# re: 复习排序算法  回复  更多评论   

这是真的好东西,多放些上来。
2006-09-25 16:14 | 坏男孩

# re: 复习排序算法  回复  更多评论   

管理员本来就是会做审核的啊
2006-09-25 19:08 | 小小凉粉

# re: 复习排序算法  回复  更多评论   

BlogJava采用的是发表后审核,发现不合适的文章会从首页移走。
2006-09-26 10:16 | dudu

# re: 复习排序算法  回复  更多评论   

那是,首页还是要以JAVA技术为主,这是原则。
只是dudu是否能考虑允许数据库语言SQL的进入呢?
毕竟SQL是项目的基础,与JAVA技术而言也是必须的啊
我不是太了解这个网站的目标是什么?但我希望它能成为
一个一站式的项目帮助网站。
2006-09-27 08:38 | 冰川

只有注册用户登录后才能发表评论。


网站导航: