黑马程序员技术交流社区

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

---

作者: 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