• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

希尔排序的C语言实现(1)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

 

代码
#include <stdio.h>
#include 
<stdlib.h>

int initialStep(int size);
void sort(int array[], int from, int end);
void insertSort(int array[], int groupIndex, int step, int end);
void move(int array[], int startIndex, int endIndex, int step);
void PrintArray(const char* strMsg,int array[],int nLength);

int main(int argc, char *argv[])
{
  
int data[13]={8,5,4,6,13,7,1,9,12,11,3,10,2};
  sort(data,
0,12);
  PrintArray(
"Shell Sort:",data,13);
  
  system(
"PAUSE");    
  
return 0;
}

/**  
 * 根据数组长度求初始步长  
 *   
 * 我们选择步长的公式为:2^k-1,2^(k-1)-1,...,15,7,3,1 ,其中2^k 减一即为该步长序列,k  
 * 为排序轮次  
 *   
 * 初始步长:step = 2^k-1   
 * 初始步长约束条件:step < len - 1 初始步长的值要小于数组长度还要减一的值(因  
 * 为第一轮分组时尽量不要分为一组,除非数组本身的长度就小于等于4)  
 *   
 * 由上面两个关系试可以得知:2^k - 1 < len - 1 关系式,其中k为轮次,如果把 2^k 表 达式  
 * 转换成 step 表达式,则 2^k-1 可使用 (step + 1)*2-1 替换(因为 step+1 相当于第k-1  
 * 轮的步长,所以在 step+1 基础上乘以 2 就相当于 2^k 了),即步长与数组长度的关系不等式为  
 * (step + 1)*2 - 1 < len -1  
 *   
 * @param len 数组长度  
 * @return  
 
*/  
int initialStep(int size) {   
    
/*  
     * 初始值设置为步长公式中的最小步长,从最小步长推导出最长初始步长值,即按照以下公式来推:  
     * 1,3,7,15,...,2^(k-1)-1,2^k-1  
     * 如果数组长度小于等于4时,步长为1,即长度小于等于4的数组不且分组,此时直接退化为直接插  
     * 入排序  
     
*/  
    
int step = 1;   

    
//试探下一个步长是否满足条件,如果满足条件,则步长置为下一步长   
    while ((step + 1* 2 - 1 < size - 1
    {   
       step 
= (step + 1* 2 - 1;   
    }   

    printf(
"初始步长 - %d\n",step);   
    
return step;   
}

/**  
  * 排序算法的实现,对数组中指定的元素进行排序  
  * @param array 待排序的数组  
  * @param from 从哪里开始排序  
  * @param end 排到哪里  
  * @param c 比较器  
  
*/  
void sort(int array[], int from, int end) {
    
int groupIndex;  
    
//初始步长,实质为每轮的分组数   
    int step = initialStep(end - from + 1);   

    
//第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值   
    for (; step >= 1; step = (step + 1/ 2 - 1) {   
        
//对每轮里的每个分组进行循环   
        for (groupIndex = 0; groupIndex < step; groupIndex++) {   

            
//对每组进行直接插入排序   
            insertSort(array, groupIndex, step, end);   
        }   
    }   
}   

/**  
 * 直接插入排序实现  
 * @param array 待排序数组  
 * @param groupIndex 对每轮的哪一组进行排序  
 * @param step 步长
 * @param end 整个数组要排哪个元素止  
 * @param c 比较器  
 
*/  
void insertSort(int array[], int groupIndex, int step, int end) {
    
int i,j;   
    
int startIndex = groupIndex;//从哪里开始排序   
    int endIndex = startIndex;  //排到哪里   
    /*  
     * 排到哪里需要计算得到,从开始排序元素开始,以step步长,可求得下一元素是否在数组范围内,  
     * 如果在数组范围内,则继续循环,直到索引超现数组范围  
     
*/  
    
while ((endIndex + step) <= end) {   
        endIndex 
+= step;   
    }   

    
// i为每小组里的第二个元素开始   
    for (i = groupIndex + step; i <= end; i += step) {   
        
for (j = groupIndex; j < i; j += step) {   
            
int insertedElem = array[i];   
            
//从有序数组中最一个元素开始查找第一个大于待插入的元素   
            if (array[j]>= insertedElem) {   
                
//找到插入点后,从插入点开始向后所有元素后移一位   
                move(array, j, i - step, step);                   
                array[j] 
= insertedElem;   
                
break;   
            }   
        }   
    }   
}
 

/**  
* 以指定的步长将数组元素后移,步长指定每个元素间的间隔  
* @param array 待排序数组  
* @param startIndex 从哪里开始移  
* @param endIndex 到哪个元素止  
* @param step 步长  
*/ 
void move(int array[], int startIndex, int endIndex, int step) {
     
int i;   
     
for (i = endIndex; i >= startIndex; i -= step) {   
        array[i 
+ step] = array[i];   
     }   
}

void PrintArray(const char* strMsg,int array[],int nLength)
{
     
int i;
     printf(
"%s",strMsg);
     
for(i=0;i<nLength;i++)
     {
        printf(
"%d ",array[i]);
     }
     printf(
"\n");
}

 

以上代码主要修改自:http://www.javaeye.com/topic/547734 
                            http://www.javaeye.com/topic/547735
其它参考资料:
http://www.cnblogs.com/ziyifly/archive/2008/09/10/1288499.html
http://www.java2000.net/p11750
http://mintelong.javaeye.com/blog/467833
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.2.2.1.htm
http://www.cnblogs.com/hualei/archive/2010/08/17/1801850.html


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
c#客显发布时间:2022-07-14
下一篇:
牌型总数——第六届蓝桥杯C语言B组(省赛)第七题发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap