A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 恩恩 中级黑马   /  2013-12-18 15:16  /  1878 人查看  /  10 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

我这里学习了一下希尔排序,所以最后把代码理解了一下,然后从新写了一遍,加了注释,希望大家可以看明白,谢谢。
  1. public class shellSort {
  2.         public shellSort() {
  3.                 int a[] = { 2, 54, 3, 24, 87, 345, 12, 68, 342, 82 };
  4.                 double d1 = a.length;
  5.                 int temp = 0;
  6.                 while (true) {
  7.                         d1 = Math.ceil(d1 / 2);    //定义一个增量,增量向上取整,而且这个增量每次都在变化。
  8.                         int d = (int) d1;         
  9.                         for (int x = 0; x < d; x++) {     //这一层循环是把当前这个增量里面的每一组数据比较一边
  10.                                 for (int i = x + d; i < a.length; i += d) {   //这一等循环式比较已经确定了的那几个数
  11.                                         int j = i - d;                            //让j等于每一组里面的第一个数
  12.                                         temp = a[i];                              //当前要比较的数的后面一个数放到临时变量里面
  13.                                         for (; j >= 0 && temp < a[j]; j -= d) {   //比较当前的数和后面的数据
  14.                                                 a[j + d] = a[j];
  15.                                         }
  16.                                         a[j + d] = temp;                          
  17.                                 }
  18.                         }
  19.                         if (d == 1)              //如果最后增量变为以就结束了
  20.                                 break;
  21.                 }
  22.                 for (int i = 0; i < a.length; i++)
  23.                         System.out.println(a[i]);
  24.         }
  25. }
复制代码

评分

参与人数 1技术分 +1 收起 理由
乔兵 + 1

查看全部评分

10 个回复

倒序浏览
  1. package com.fs.common.util;

  2. public class shellSort {
  3.         public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4 };

  4.         public static void main(String args[]) {
  5.                 int i;
  6.                 int index = a.length;
  7.                 ShellSort(index - 1);
  8.                 System.out.print("排序后: ");
  9.                 for (i = 0; i < index - 1; i++)
  10.                         System.out.printf("%3s ", a[i]);
  11.         }

  12.         public static void ShellSort(int index) {
  13.                 int temp; // 暂存变量  
  14.                 int dataLength; // 分割集合的间隔长度  
  15.                 int pointer; // 进行处理的位置  
  16.                 dataLength = (int) index / 2; // 初始集合间隔长度  
  17.                 while (dataLength != 0) {// 对各个集合进行处理   
  18.                         for (int i = dataLength; i < index; i++) {
  19.                                 temp = a[i]; // 暂存Data[j]的值,待交换值时用   
  20.                                 pointer = i - dataLength; // 计算进行处理的位置   
  21.                                 // 进行集合内数值的比较与交换值   
  22.                                 while (temp < a[pointer] && pointer >= 0 && pointer <= index) {
  23.                                         a[pointer + dataLength] = a[pointer]; // 计算下一个欲进行处理的位置  
  24.                                         pointer = pointer - dataLength;
  25.                                         if (pointer < 0 || pointer > index)
  26.                                                 break;
  27.                                 }
  28.                                 a[pointer + dataLength] = temp;
  29.                         }
  30.                         dataLength = dataLength / 2;// 计算下次分割的间隔长度  
  31.                 }
  32.         }
  33. }
复制代码
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。

评分

参与人数 1技术分 +1 收起 理由
乔兵 + 1

查看全部评分

回复 使用道具 举报
基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法引

比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比[1]较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。
一般的初次取序列的一半为增量,以后每次减半,直到增量为1。
给定实例的shell排序的排序过程

假设待排序文件有10个记录,其关键字分别是:
四九,三八,六五,九七,七六,一三,二七,四九,五五,零四。
增量序列的取值依次为:
五,三,一[2]
回复 使用道具 举报
        static void shell_sort(int[] unsorted, int len)
        {
            int group, i, j, temp;
            for (group = len / 2; group > 0; group /= 2)
            {
                for (i = group; i < len; i++)
                {
                    for (j = i - group; j >= 0; j -= group)
                    {
                        if (unsorted[j] > unsorted[j + group])
                        {
                            temp = unsorted[j];
                            unsorted[j] = unsorted[j + group];
                            unsorted[j + group] = temp;
                        }
                    }
                }
            }
        }


        static void Main(string[] args)
        {
            int[] x = { 6, 2, 4, 1, 5, 9 };
            shell_sort(x, x.Length);
            foreach (var item in x)
            {
                Console.WriteLine(item);
            }
            Console.ReadLine();
        }
回复 使用道具 举报
经典排序算法 - 希尔排序Shell sort
回复 使用道具 举报
taxue0504 发表于 2013-12-18 15:36
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Sh ...

谢谢你的分享
回复 使用道具 举报

共同学习,共同进步一起进黑马
回复 使用道具 举报
荣海林 发表于 2013-12-18 16:07
static void shell_sort(int[] unsorted, int len)
        {
            int group, i, j, temp; ...

貌似是c语言的结构    顶起
回复 使用道具 举报
恩恩 中级黑马 2013-12-18 17:18:38
9#
荣海林 发表于 2013-12-18 16:08
经典排序算法 - 希尔排序Shell sort

是的,一起加油
回复 使用道具 举报
恩恩 中级黑马 2013-12-18 17:19:52
10#
taxue0504 发表于 2013-12-18 16:37
共同学习,共同进步一起进黑马

一起加油
回复 使用道具 举报
谢谢分享!
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马