JUST DO IT

我之所以在这里，只是因为我想要在这里

希尔排序（Windows+VC6.0环境编译）

希尔排序基本思想是：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
 1#include <stdio.h>
 2#include <cstdlib>
 3
 4#define TOTAL_NUM 100
 5#define MAX_NUM 200
 6
 7int shell_sort(int sort[],int increment)
 8{    
 9    for (int i=0;i<increment;i++)
10    {
11        for (int j=i+increment;j<TOTAL_NUM;j+=increment)
12        {
13            int iNum = sort[j];
14            if (iNum>=sort[j-increment])continue;
15            int k = 0;
16              for (k=j-increment;k>=0;k-=increment)
17              {
18                  if (sort[k]>iNum)
19                {
20                    sort[k+increment] = sort[k];                    
21                }else 
22                {
23                    sort[k] = iNum;
24                    break;
25                }
26              }              
27        }
28    }    
29    return 0;
30}
31
32void SORT(int sort[])
33{
34    int incre = TOTAL_NUM;
35    do{
36        incre = incre/4+1;
37        shell_sort(sort,incre);
38    }while (incre>1);    
39}
40
41int main(int argc,char* argv[])
42{
43    int Sort[TOTAL_NUM];
44    
45    int iPrintCount = 0;
46    int i = 0;
47    printf("::: old order ::: \n");    
48    for (i=0;i<TOTAL_NUM;i++)
49    {
50        Sort[i] = (rand()+MAX_NUM)%MAX_NUM;
51        printf("%5ld ",Sort[i]);    
52        if(++iPrintCount==10)
53        {
54            iPrintCount = 0;
55            printf("\n");
56        }
57    }
58    
59    //shell sort
60    SORT(Sort);
61    
62    iPrintCount = 0;
63    printf("\n::: new order ::: \n");    
64    for (i=0;i<TOTAL_NUM;i++)
65    {        
66        printf("%5ld ",Sort[i]);    
67        if(++iPrintCount==10)
68        {
69            iPrintCount = 0;
70            printf("\n");
71        }
72    }
73    
74    getchar();
75    return 0;
76}

posted on 2009-07-29 23:06 xmoss 阅读(1610) 评论(0)  编辑 收藏 引用 所属分类: 结构和算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理