黑马程序员技术交流社区

标题: 希尔排序 [打印本页]
作者: 恩恩    时间: 2013-12-18 15:16
标题: 希尔排序
我这里学习了一下希尔排序，所以最后把代码理解了一下，然后从新写了一遍，加了注释，希望大家可以看明白，谢谢。
  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. }
复制代码

作者: taxue0504    时间: 2013-12-18 15:36
  1. package com.fs.common.util;

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

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

  15.         public static void ShellSort(int index) {
  16.                 int temp; // 暂存变量 　
  17.                 int dataLength; // 分割集合的间隔长度 　
  18.                 int pointer; // 进行处理的位置 　
  19.                 dataLength = (int) index / 2; // 初始集合间隔长度 　
  20.                 while (dataLength != 0) {// 对各个集合进行处理 　　
  21.                         for (int i = dataLength; i < index; i++) {
  22.                                 temp = a[i]; // 暂存Data[j]的值,待交换值时用 　　
  23.                                 pointer = i - dataLength; // 计算进行处理的位置 　　
  24.                                 // 进行集合内数值的比较与交换值 　　
  25.                                 while (temp < a[pointer] && pointer >= 0 && pointer <= index) {
  26.                                         a[pointer + dataLength] = a[pointer]; // 计算下一个欲进行处理的位置 　
  27.                                         pointer = pointer - dataLength;
  28.                                         if (pointer < 0 || pointer > index)
  29.                                                 break;
  30.                                 }
  31.                                 a[pointer + dataLength] = temp;
  32.                         }
  33.                         dataLength = dataLength / 2;// 计算下次分割的间隔长度 　
  34.                 }
  35.         }
  36. }
复制代码
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
作者: 零敢    时间: 2013-12-18 16:03
基本思想:先取一个小于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]
作者: 荣海林    时间: 2013-12-18 16:07
        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();
        }
作者: 荣海林    时间: 2013-12-18 16:08
经典排序算法 - 希尔排序Shell sort
作者: 恩恩    时间: 2013-12-18 16:12
taxue0504 发表于 2013-12-18 15:36
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Sh ...

谢谢你的分享
作者: taxue0504    时间: 2013-12-18 16:37
恩恩 发表于 2013-12-18 16:12
谢谢你的分享

共同学习，共同进步一起进黑马
作者: taxue0504    时间: 2013-12-18 16:39
荣海林 发表于 2013-12-18 16:07
static void shell_sort(int[] unsorted, int len)
        {
            int group, i, j, temp; ...

貌似是c语言的结构    顶起
作者: 恩恩    时间: 2013-12-18 17:18
荣海林 发表于 2013-12-18 16:08
经典排序算法 - 希尔排序Shell sort

是的，一起加油
作者: 恩恩    时间: 2013-12-18 17:19
taxue0504 发表于 2013-12-18 16:37
共同学习，共同进步一起进黑马

一起加油
作者: 夕默    时间: 2014-9-15 15:01
谢谢分享！



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2