希尔排序(Shell Sort)
插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。
希尔排序基本思想:
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序
;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
给定实例的shell排序的排序过程
假设待排序文件有10个记录,其关键字分别是:
49,38,65,97,76,13,27,49,55,04。
增量序列的取值依次为:
5,3,1
缩小增量法
属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序
排序过程:先取一个正整数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
算法分析:
不需要大量的辅助空间,和归并排序一样容易实现。希尔排序是基于插入排序的一种算法,
在此算法基础之上增加了一个新的特性,提高了效率。希尔排序的时间复杂度为 O(N*(logN)2), 没有快速排序算法快
O(N*(logN)),因此中等大小规模表现良好,对规模非常大的数据排序不是
最优选择。但是比O(N2)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。
此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏 的情况下执行的效率会非常差。
专家们提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快, 再改成快速排序这样更高级的排序算法.
本质上讲,希尔排序算法的一种改进,减少了其复制的次数,速度要快很多。 原因是,当N值很大时数据项每一趟排序需要的个数很少,但数据项的距离很长。
当N值减小时每一趟需要和动的数据增多,此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。
稳定性:
稳定性
:
排序前一个序列中,如果出现N个与关键字相同的数据,那么排序后仍然按照原先序列的排列顺序排列,就说这个算法是稳定的,反之就是不稳定的。通俗地讲就是
能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,
Ai原来在位置前,排序后Ai还是要在Aj位置前。
希尔分析
:
希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,
插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元
素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。
Java 代码实现:
package test.suanfa;
/**
* 插入排序----希尔排序:我们选择步长为:15,7,3,1 我们选择步长公式为:2^k-1,2^(k-1)-1,……,15,7,3,1
* (2^4-1,2^3-1,2^2-1,2^1-1) 注意所有排序都是从小到大排。
*
* @author TSW
*/
public class ShellSort {
/**
* 测试
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 8, 2, 6, 3, 7, 0 };
ShellSort shellSort = new ShellSort();
shellSort.sort(intgArr, 0, intgArr.length - 1);
for (Integer intObj : intgArr) {
System.out.print(intObj + " ");
}
}
/**
* 排序算法的实现,对数组中指定的元素进行排序
* @param array 待排序的数组
* @param from 从哪里开始排序
* @param end 排到哪里
*/
public void sort(Integer[] array, int from, int end) {
// 初始步长,实质为每轮的分组数
int step = initialStep(end - from + 1);
// 第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值
for (; step >= 1; step = (step + 1) / 2 - 1) {
// 对每轮里的每个分组进行循环
for (int groupIndex = 0; groupIndex < step; groupIndex++) {
// 对每组进行直接插入排序
insertSort(array, groupIndex, step, end);
}
}
}
/**
* 直接插入排序实现
* @param array 待排序数组
* @param groupIndex 对每轮的哪一组进行排序
* @param step 步长
* @param end 整个数组要排哪个元素止
*/
public void insertSort(Integer[] array, int groupIndex, int step, int end) {
int startIndex = groupIndex;// 从哪里开始排序
int endIndex = startIndex;// 排到哪里
/*
*
* 排到哪里需要计算得到,从开始排序元素开始,以step步长,可求得下元素是否在数组范围内,
*
* 如果在数组范围内,则继续循环,直到索引超现数组范围
*/
while ((endIndex + step) <= end) {
endIndex += step;
}
// i为每小组里的第二个元素开始
for (int i = groupIndex + step; i <= end; i += step) {
for (int j = groupIndex; j < i; j += step) {
Integer insertedElem = array[i];
// 从有序数组中最一个元素开始查找第一个大于待插入的元素
if ((array[j].compareTo(insertedElem)) >= 0) {
// 找到插入点后,从插入点开始向后所有元素后移一位
move(array, j, i - step, step);
array[j] = insertedElem;
break;
}
}
}
}
/**
* 根据数组长度求初始步长
*
* 我们选择步长的公式为:2^k-1,2^(k-1)-1,...,15,7,3,1 ,其中2^k 减一即为该步长序列,k 为排序轮次
*
* 初始步长:step = 2^k-1
* 初始步长约束条件:step < len - 1 初始步长的值要小于数组长度还要减一的值
* (因 为第一轮分组时尽量不要分为一组,除非数组本身的长度就小于等于4)
*
* 由上面两个关系试可以得知:2^k - 1 < len - 1 关系式,其中k为轮次,如果把2^k 表 达式
* 转换成step 表达式,则2^k-1 可使用(step + 1)*2-1 替换(因为step+1 相当于第k-1
* 轮的步长,所以在step+1 基础上乘以2 就相当于2^k 了),即步长与数组长度的关系不等式为
* (step + 1)*2 - 1 < len -1
*
* @param len 数组长度
* @return
*/
public static int initialStep(int len) {
/*
*
* 初始值设置为步长公式中的最小步长,从最小步长推导出最长初始步长值,即按照以下公式来推:
*
* 1,3,7,15,...,2^(k-1)-1,2^k-1
*
* 如果数组长度小于等于4时,步长为1,即长度小于等于4的数组不用分组,此时直接退化为直接插入排序
*/
int step = 1;
// 试探下一个步长是否满足条件,如果满足条件,则步长置为下一步长
while ((step + 1) * 2 - 1 < len - 1) {
step = (step + 1) * 2 - 1;
}
System.out.println("初始步长: " + step);
return step;
}
/**
* 以指定的步长将数组元素后移,步长指定每个元素间的间隔
* @param array 待排序数组
* @param startIndex 从哪里开始移
* @param endIndex 到哪个元素止
* @param step 步长
*/
protected final void move(Integer[] array, int startIndex, int endIndex, int step) {
for (int i = endIndex; i >= startIndex; i -= step) {
array[i + step] = array[i];
}
}
}
分享到:
相关推荐
经典排序算法 - 希尔排序Shell sort 经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳排序Comb sort 经典排序算法 - 耐心排序...
基于python的排序算法-希尔排序Shell Sort
# sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() #计数排序 # sort.quickSort() #快速排序 该排序算法把...
shellsort希尔排序算法增加最佳组合1
此希尔排序算法采用增量减半的方法来进行数据的排序,内有部分注释
java十大排序算法实现 1. 冒泡排序(Bubble Sort) 2. 选择排序(Selection Sort) 3. 插入排序(Insertion Sort) 4. 快速排序(Quick Sort) 5. 归并排序(Merge Sort) 6. 堆排序(Heap Sort) 7. 计数排序...
希尔排序(Shell Sort)是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列(由相隔...
希尔排序(Shell Sort) 归并排序(Merge Sort) 快速排序(Quick Sort) 堆排序(Heap Sort) 计数排序(Counting Sort) 基数排序(Radix Sort) 桶排序(Bucket Sort) 深度优先搜索(Depth-First Search, DFS) ...
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort...插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序mergesort
void paixucaidan() { int i; SeqList R; input_int(R); ... case 7:ShellSort(R); break; //值为7,希尔排序 } printf("Sort reult:"); output_int(R); printf("\n"); } 以上为菜单及功能
- 希尔排序(Shell Sort) - 冒泡排序(Bubble Sort) - 快速排序(Quick Sort) - 选择排序(Selection Sort) - 堆排序(Heap Sort) - 归并排序(Merge Sort) - 箱排序(Bin Sort) - 基数排序(Radix Sort)
本文实例讲述了PHP排序算法之希尔排序(Shell Sort)。分享给大家供大家参考,具体如下: 基本思想: 希尔排序是指记录按下标的一定增量分组,对每一组使用 直接插入排序 ,随着增量逐渐减少,每组包含的关键字越来越...
java写的八大经典排序算法(win7 jdk 1.6 下运行) 冒泡排序 BubbleSort 堆排序 HeapSort 插入排序 InsSort 快速排序 QuickSort 归并排序 MergeSort 基数排序 BucketSort 简单选择排序 Select...希尔排序 ShellSort
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,...
希尔排序(Shell's Sort)是插入排序的一种,又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而...
常见经典排序算法 1.希尔排序 2.二分插入法 3.直接插入法 4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序 一.希尔(Shell)排序法(又称宿小增量排序,是1959年由D.L.Shell提出来的) /* ...
使用MATLAB实现一个简单的希尔排序的例子
希尔排序-ShellSort | 自顶向下归并排序-MergeSort | 自底向上归并排序-MergeBUSort | 快速排序-QuickSort | 堆排序-HeapSort :lion:搜索算法-搜索 与搜索相关的数据结构:二叉查找树,平衡查找树,散列表 线性查找...
int array[10]={10,3,5,2,4,1,8,7,9,6}; cout; print_array(array,10); //cout<<"select_sort"; //select_sort(array,10); //cout<<"bubble_sort"; //bubble_sort(array,10); //cout<<"insert_sort"; /...
]希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组...