那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

常见排序算法的实现(二)-shell排序

shell排序是对插入排序的一个改装,它每次排序把序列的元素按照某个增量分成几个子序列,对这几个子序列进行插入排序,然后不断的缩小增量扩大每个子序列的元素数量,直到增量为一的时候子序列就和原先的待排列序列一样了,此时只需要做少量的比较和移动就可以完成对序列的排序了.

// shell排序
void ShellSort(int array[], int length)
{
    int temp;

    // 增量从数组长度的一半开始,每次减小一倍
    for (int increment = length / 2; increment > 0; increment /= 2)
        for (int i = increment; i < length; ++i)
        {
            temp = array[i];
            // 对一组增量为increment的元素进行插入排序
            for (int j = i; j >= increment; j -= increment)
            {
                // 把i之前大于array[i]的数据向后移动
                if (temp < array[j - increment])
                {
                    array[j] = array[j - increment];
                }
                else
                {
                    break;
                }
            }
            // 在合适位置安放当前元素
            array[j] = temp;
        }
}

动画演示:
http://202.113.89.254/DataStructure/DS/web/flashhtml/shell.htm

posted on 2006-07-03 16:07 那谁 阅读(1093) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理