黑马程序员技术交流社区

标题: 希尔排序 [打印本页]

作者: wangzhiyong515    时间: 2014-5-9 18:59
标题: 希尔排序
package cn.itcast;

/*
* 希尔排序:先取一个小于n的整数d1作为第一个增量,
* 把文件的全部记录分成(n除以d1)个组。所有距离为d1的倍数的记录放在同一个组中。
* 先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,
* 直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
*/
public class ShellSort {
        public static void sort(int[] data) {
                for (int i = data.length / 2; i > 2; i /= 2) {
                        for (int j = 0; j < i; j++) {
                                insertSort(data, j, i);
                        }
                }
                insertSort(data, 0, 1);
        }

        /**
         * @param data
         * @param j
         * @param i
         */
        private static void insertSort(int[] data, int start, int inc) {
                for (int i = start + inc; i < data.length; i += inc) {
                        for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
                                SortTest.swap(data, j, j - inc);
                        }
                }
        }
}
/*
* 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序   
* 排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,
* 组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1, 即所有记录放进一个组中排序为止   
* 初始:d=5   49 38 65 97 76 13 27 49 55 04   
* 49 13   |-------------------|   
* 38 27     |-------------------|   
* 65 49   |-------------------|   
* 97 55     |-------------------|   
* 76 04   |-------------------|   
* 一趟结果   13 27 49 55 04 49 38 65 97 76   
* d=3    13 27 49  55 04 49 38 65 97 76   
* 13 55 38 76 |------------|------------|------------|   
* 27 04 65 |------------|------------|   
* 49 49 97 |------------|------------|   
* 二趟结果  13 04 49* 38 27 49 55 65 97 76   
* d=1   13 04 49 38 27 49 55 65 97 76
*    |----|----|----|----|----|----|----|----|----|    三趟结果   
* 04 13 27 38 49 49 55 65 76 97
*/

作者: 志ぁ才☆博ぁ成    时间: 2014-5-9 19:28
这种排序方法视频中没讲,不懂啊。
作者: wangzhiyong515    时间: 2014-5-10 12:08
志ぁ才☆博ぁ成 发表于 2014-5-9 19:28
这种排序方法视频中没讲,不懂啊。

是的,这种排序是属于扩展性的,看不懂也没关系,把选择和冒泡弄懂就行了:)
作者: serioustd    时间: 2014-5-10 12:31
赞赞赞赞赞赞




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