Shellsort is a simple extension of insertion sort that gains speed by allowing exchanges of array entries that are far apart, to produce partially sorted arrays that can be efficiently sorted, eventually by insertion sort.
The idea is to rearrange the array to give it the property that taking every hth entry (starting anywhere) yields a sorted subsequence. Such an array is said to be h-sorted. Put another way, an h-sorted array is h independent sorted subsequences, interleaved together. By h-sorting for some large values of h, we can move items in the array long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any sequence of values of h that ends in 1 will produce a sorted array: that is shellsort. Another alternative is to store an increment sequence in an array.
One way to implement shellsort would be, for each h, to use insertion sort independently on each of the h sub sequences. Because the subsequences are independent, we can use an even simpler approach: when h-sorting the array, we insert each item among the previous items in its h-subsequence by exchanging it with those that have larger keys (moving them each one position to the right in the subsequence). We accomplish this task by using the insertion-sort code, but modified to decrement by h instead of 1 when moving through the array. This observation reduces the shellsort implementation to an insertion-sort-like pass through the array for each increment.
Shellsort gains efficiency by making a tradeoff between size and partial order in the subsequences. At the beginning, the subsequences are short; later in the sort, the subsequences are partially sorted. In both cases, insertion sort is the method of choice. The extent to which the subsequences are partially sorted is a variable factor that depends strongly on the increment sequence. Understanding shellsort’s performance is a challenge. Indeed, it is the only sorting method we consider whose performance on randomly ordered arrays has not been precisely characterized.
public class Shell { // sort the array a[] in ascending order using Shellsort public static void sort(Comparable[] a) { int N = a.length; // 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ... int h = 1; while (h < N/3) h = 3*h + 1; while (h >= 1) { // h-sort the array for (int i = h; i < N; i++) { for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) { exch(a, j, j-h); } } assert isHsorted(a, h); h /= 3; } assert isSorted(a); } /*********************************************************************** * Helper sorting functions ***********************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { return (v.compareTo(w) < 0); } // exchange a[i] and a[j] private static void exch(Object[] a, int i, int j) { Object swap = a[i]; a[i] = a[j]; a[j] = swap; } /*********************************************************************** * Check if array is sorted - useful for debugging ***********************************************************************/ private static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) if (less(a[i], a[i-1])) return false; return true; } // is the array h-sorted? private static boolean isHsorted(Comparable[] a, int h) { for (int i = h; i < a.length; i++) if (less(a[i], a[i-h])) return false; return true; } // print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { System.out.println(a[i]); } } }
相关推荐
数据结构课程排序算法中的经典shell排序
∷相关函数:ShellSort函数 1.5.7 冒泡排序 243 范例1-83 冒泡排序 243 ∷相关函数:bubble_sort函数 1.5.8 一趟快速排序 246 范例1-84 一趟快速排序 246 ∷相关函数:QSort函数 1.5.9 一趟快速排序的改进算法 248 ...
本文件包含shell排序的基本思路,代码实现,时间复杂度的分析。对数据结构与算法中shell排序算法的实现,附件以python实现。
学习的大部分基础数据结构和相关的算法 实现语言主要是C/C++ BST: 二分搜索树 BubbleSort: 冒泡排序 CircleLinkList: 循环链表 Expression: 表达式求值 Fibonacci: 斐波那契数列 Floyd: 弗洛伊德算法 Graphic: 图...
希尔排序(Shellsort)、快速排序(Quicksortt)、堆排序(Heapsort)和归并排序(Mergesort)的数据结构与算法实现
数据结构算法实现(严蔚敏版配套实现程序) 1.1 数组和字符串 2 1.1.1 一维数组的倒置 2 范例1-1 一维数组的倒置 2 ∷相关函数:fun函数 1.1.2 一维数组应用 3 范例1-2 一维数组应用 3 1.1.3 一维数组的高级应用 5 ...
这个项目是关于Pythonic数据结构和算法的。 在Python 3中只有很少且干净的示例性数据结构和算法实现。 로젝트의기여자가되었습니다。 我们的活动 自述文件翻译 贡献文件翻译 算法实现 数学 组合 阶乘 斐波那契 ...
1-初始化顺序表得到随机数 2-冒泡排序 3-直接插入排序 4-选择排序 5-快速排序 6-希尔排序 7-堆排序 8-进行性能比较 比较包括比较(排序时间,比较次数,移动次数)
算法和数据结构 目录 └─Outline ├─algorithms │ ├─search │ │ ├─binarysearch │ │ └─linearsearch │ └─sort │ ├─bubblesort │ ├─countingsort │ ├─insertionsort │ ├─...
此希尔排序算法采用增量减半的方法来进行数据的排序,内有部分注释
严蔚敏数据结构与算法 课本算法实现
严蔚敏数据结构与算法 课本算法实现
这是一门经典的数据结构与算法课,免费,分上下两部分,上部分内容包括Union-Find, basic data structures(Array, LinkedList, Queue, Stack, prioprity queue, symbol table...), sorting algorithms (selection ...
目 录 摘 要 1 前 言 2 正 文 3 1. 采用类C语言定义相关的数据类型 4 2. 各模块的伪码算法 5 3. 函数的调用关系图 11 4. 调试分析 11 5. 测试结果 13 6. 源程序(带注释) 16 ...各种部排序算法的时间...}//shellsort
使用 Golang 学习数据结构和算法 分拣机 转到排序器文件夹并运行./Build在bin文件夹中构建排序器程序。 运行./sorter -a赋值 AndAlgorithm -i分配输入文件 -o分配输出文件 样本: cd bin ./sorter -i unsorted....
计算机专业所需,C语言编写,富含例题一、...(五)希尔排序(shell sort) (六)快速排序 (七)堆排序 (八)二路归并排序(merge sort) (九)基数排序 (十)各种内部排序算法的比较 (十一)内部排序算法的应用
∷相关函数:ShellSort函数 1.5.7 冒泡排序 243 范例1-83 冒泡排序 243 ∷相关函数:bubble_sort函数 1.5.8 一趟快速排序 246 范例1-84 一趟快速排序 246 ∷相关函数:QSort函数 1.5.9 一趟快速排序的改进算法 248 ...
def shell_sort(arr_list): ''' 交换法,用希尔排序方法对列表进行排序 参数: 待排序的列表 执行结果: 输出排好序后的列表 ''' i = (int)(len(arr_list) / 2) # i表示分组的个数,也即是步长 while i
算法和数据结构。 算法库,数据结构库,常见CS问题的各种解决方案。 安装 将此行作为托管依赖项添加到您的应用程序中: py-algorithms > =0, < 1 或使用pip软件包管理器在全球/本地安装它: $ pip install py...
面试准备-Java-算法-数据结构 排序 Bubble Sort Selection Sort Insertion Sort Shell Sort Heap Sort Merge Sort Quick Sort Counting Sort Radix Sort MSD Vs LSD Bucket Sort ####快速排序 QuickSort...